A Graph-Based Two-Dimensional Constraint Solver

Our approach to geometric constraint solving is a recursive analysis, graph-based method. This approach is favored for two reasons. First, it allows determination of whether the problem is well-constrained or not in essentially quadratic time. Second, it decouples the constraint solving problem into groups of smaller systems of equations which can be solved independently and then merged, rather than framing the problem as a single, large algebraic system to be solved.

Allowable Geometries and Constraints

The geometric elements considered in the two-dimensional constraint solver are points, lines and circles of fixed radius. A point is represented by two coordinates (px, py). A line is represented by a signed, unit normal and the distance of the line from the origin, (nx, ny, d). Equationally, the line can be represented as the set of points (x,y) satisfying nx x + ny y - d = 0 and nx^2 + ny^2 = 1. A circle is represented by its center (cx, cy) and its radius cr. For simplification purposes, we require that the radius of a circle be fixed, that is, the radius cannot be varied to satisfy constraints.

The constraints between these geometric entities are incidence of two entities, distance between two points, distance between a point and a line, distance between two parallel lines, angle between two lines, tangency between a circle and a line, and concentricity of circles. However, because the circles are restricted to having fixed radius, they can be treated as points by transforming the constraints in which they are involved into distance and incidence constraints of their center points only. In fact, all constraints can be transformed into distance and angle constraints only, which greatly simplifies the placement problem.

Since the problem is reduced to placing points and lines, any geometric element is fixed (up to finitely many positions) by knowing its relationship to two other previously fixed objects. This fact plays an important role in the analysis phase of the algorithm, which we describe in the next section.

Initial Cluster Formation

The first phase of the graph-based method for constraint solving involves analysis of the constraint graph. This analysis determines if the problem is well-constrained or not, and it determines a sequence of steps for placing the geometric elements if the problem is well-constrained. The basic idea, as described above, is to build up collections, or clusters of geometric elements which can be placed relative to one another, and then to merge these clusters into larger collections using rigid body transformations.

Cluster formation begins by selecting any two nodes of the graph which are connected by a constraint edge. These two entities can be placed in some generic position, depending on the type of geometries and the type of constraint between them. These two entities are then considered known. The cluster is then made as large as possible by adding to the cluster any node which is connected by a constraint edge to exactly two nodes already in the cluster. There must be at least two known nodes to which the unknown node is related because each of the geometric elements has two degrees of freedom. There cannot be more than two, because otherwise the problem is overconstrained.

When no more nodes in the graph can be added to the cluster, the cluster is considered complete. All constraint edges used in forming the cluster are deleted from original graph, and a search for a new cluster is carried out in the subgraph. This process continues until there are no more constraints from which to make any clusters.

           
      Figure 1: A well-constrained sketch and its constraint graph

For example, consider the sketch on the left in Figure 1. Its constraint graph is shown on the right of the figure, where incidence is shown by unlabeled edges. If we start the first cluster with p1 and l1, we can add p2 to the cluster, and then can go no further, since no other node in the graph is connected to two nodes of the cluster. We delete the three constraint edges used to form this cluster, and look for a new cluster, perhaps beginning this time with p2 and l2. To this new cluster we can add p3, and subsequently l3, since it is connected to l2 and p3. This cluster is now complete. We begin our third cluster with p4 and l3, and add l4, p5, and p1, in that order. All constraint edges have now been used, so cluster formation is complete. The constraint graph is shown again in Figure 2, with the three clusters indicated.

        
      Figure 2: The constraint graph forms three clusters.

Note that clusters may have nodes in common; in fact, that property is essential for the next step of the analysis phase. In order for the problem to be well-constrained, the clusters must be able to be merged together in some way so that a single structure results. Geometrically, this amounts to using rigid body transformations to bring the clusters into correct relationship with respect to one another.

Cluster Merging

Three clusters, each of which share exactly one node with each of the other two clusters, can be brought into alignment with one another using the shared elements. In the example of Figure 1, the points p1 and p2 and the line l3 are shared in this way between the clusters. We can compute the distance from p1 to l3 within cluster V and the distance from p2 to l3 within cluster W. The distance between p1 and p2 is already known, so these three elements can be placed relative to one another, thus merging the three clusters into one larger cluster. If other clusters have two elements in common with the new cluster, they can be merged into it as well. When the merged cluster can be grown no longer, the clusters are searched for another set of three clusters which can be merged.

This process continues until all the clusters have been merged into a single cluster, or until no more clusters can be merged. If there are multiple clusters at the end of the merging stage, the problem is not well-constrained. If there is a single cluster, then the steps for constructing the configuration are detailed by the order of the cluster formation.

An important point about the cluster formation and merging process is that it is not unique. Any two nodes with a constraint between them can be chosen to begin a cluster, and if more than one node could be added to a cluster at a given step, any of them can be selected and added. However, for a well-constrained problem, it has been shown that no matter what clusters are formed, the final geometric solutions determined by the order of construction from the clusters are congruent[32].

The cluster formation phase of the solution does not do any actual placement of geometric elements. Rather, its function is to analyze the structure of the relationships between the geometric elements based on the constraints between them. The placement of the elements itself is done in the second phase of the solution. In the next section, we describe geometrically how to find the position of an unknown geometric element, given its relationship to two known elements.