Encoding Relative Orientation and Mereotopology Relations with Geometric Constraints in CLP(QS)

摘要: One approach for encoding the semantics of spatial relations within a declarative programming framework is by systems polynomial constraints. However, solving such constraints computationally intractable in general (i.e. theory realclosed fields), and thus far proposed symbolic algebraic methods do not scale to real world problems. In this paper we address intractability investigating use constructive geometric constraint (in combination with numerical optimisation) context logic over qualitative spaces, CLP(QS). We present novel encodings relative orientation mereotopology show that our are significantly more robust than other approaches directly inequalities, due being based on standard, well known set encoded as quadratic equations. Our implementation specific) can be employed all standard solvers, particularly solvers prominent Computer Aided Design Manufacturing communities. empirically evaluate range benchmark problems from Qualitative Spatial Reasoning community, method outperforms reasoning orders magnitude those (such Cylindrical Algebraic Decomposition).