Constraint satisfaction problems related to geometry mostly arise in CAD. But even though they are designed for geometry, none of the methods proposed to solve these problems fully meets the requirements needed by the educational domain. In this paper, we adapt CAD methods to education and show that results must be construction programs in order to take into account particular cases. We present then a framework implemented in Prolog as a knowledge-based system called Progé.

Abstract For more than a decade, the trend in geometric constraint systems solving has been to use a geometric decomposition/recombination approach. These methods are generally grounded on the invariance of systems under rigid motions. In order to decompose further, other invariance groups (e.g., scalings) have recently been considered. Geometric decomposition is grounded on the possibility to replace a solved subsystem with a smaller system called boundary . This article shows the central property that justifies decomposition, without assuming specific types of constraints or invariance groups. The exact nature of the boundary system is given. This formalization brings out the elements of a general and modular implementation.