Graph Based Constraint Solving

Graph-based algorithms for solving geometric constraint problems have two phases, the first an analysis phase and the second a construction phase. The graph-based approach begins by first constructing a graph representation of the problem. Each node in the graph represents a single geometric element, so that a line segment a of length d delimited by two points A and B would have three nodes. An edge between two geometric entities indicates a constraint between the elements. The type of constraint is indicated by a label on the edge. This simple example is shown in Figure 1, where edges which assert incidence are unlabeled in the graph. 
           
      Figure 1: A set of geometric elements with constraints, and the
                corresponding constraint graph; d denotes a 
                distance constraint.

Once a constraint graph has been obtained from the given geometric entities and the constraints, the graph is analyzed to determine whether the problem is well-constrained. If the graph is well-constrained, this phase also determines a sequence of steps for solving the problem. The second phase of the graph method takes the construction sequence determined from the first phase and performs the necessary construction steps to actually place the geometric elements. Since the first phase does not depend on the values of the constraint but only on the number and type of constraints between the geometric elements, this is a generic method of constraint solving. The actual values of the constraints only come into play in the second phase when the construction steps are carried out.

There are a variety of ways to handle the analysis phase of the graph-based method. One approach is to look for a sequence of construction steps such that the next construction step depends only on previously placed elements. Not all configurations can be handled in this way, however. A different approach looks for collections of geometric elements whose members can be placed with respect to one another based on constraints between them. These collections are then placed relative to one another, thus forming new, larger collections of elements, until all constraints have been processed and the locations of all the elements are known.

The approach to constraint solving which we have implemented in two dimensions is a graph-based technique which uses the recursive analysis phase just sketched. This is detailed in the next section of the theoretical foundations tour.

References

Overview

Theory

Implementation