A 2D geometric constraint solver using a graph reduction method

Modeling by constraints enables users to describe shapes by specifying relationships between geometric elements. These relationships are called constraints. A constraint solver derives then automatically the design intended by exploiting these constraints. The constraints solvers can be classified in four categories: symbolic, numerical, rule-oriented and graph-constructive solvers. The graph constructive approach is widely used in recent Computer Aided Design (CAD) systems. In this paper, we present a decomposition–recombination (DR) planning algorithm, called S-DR, that uses a graph reduction method to solve systems of 2D geometric constraints. Based on the key concept of skeletons, S-DR planner figures out a plan for decomposing a well constrained system into small sub-systems and recombines the solutions of these sub-systems to derive the solution of the entire system.