A Graph-Based Two-Dimensional Constraint Solver (continuation)

The first phase of our graph based constraint solver analyses the constraint system by forming clusters which are rigid, and then merging the clusters until a decision can be made about whether the constraint system is well-constrained or not. That phase also provides a sequence of constructions for placing the geometric elements when the problem is well-constrained. In this section we discuss how these placements are performed.

Basic Construction Steps

The placement of one geometric element relative to two others is accomplished by solving small systems of algebraic equations. Because of the restriction on geometries and constraints, these equations have degree at most two. We use the following notation throughout the discussion. The Euclidean distance norm of a vector v = (vx, vy) is denoted || v || = sqrt(vx^2 + vy^2). Let p1 and p2 be two points and l1(n1, r1) and l2(n2, r2) be two lines, where ni is the unit normal of li, and ri is the signed distance from li to the origin. We then can write algebraic equations for the geometric constraints between two entities in the following manner:

The distance between the two points p1 and p2 is d12:
```
        || p1 - p2 || = d12
```

The signed distance between the point p1 and the line l2 is d12:

        p1 * n2 = r2 + d12, where * is the vector dot product

The signed angle between the two lines l1 and l2 is A12

        n2 = (nx cos(A12) - ny sin(A12), ny cos(A12) + nx sin(A12))

where n1 = (nx, ny).

The sign of the distance and angle measures are determined from the way in which the user inputs the data. For example, a line segment has an orientation in the direction from the first end point to the second. When a point is input and a distance to the line segment assigned as a constraint, the sign is determined from the side of the line on which the point is initially placed by the user. Again for angle constraints, the orientations of the two line segments are used to determine which region between the segments should be affected by the constraint. Having this algebraic understanding of the geometry of the constraints allows us to evaluate the following cases:

Case 1: (p1, p2) => p3

        
      Figure 3: Placing a point relative to two known points

The point p3 is to be constructed from two given points p1and p2, where pi has distance di3 from p3. The coordinates of point p3 must satisfy two quadratic equations arising from the two distance constraints. Geometrically this corresponds to intersecting two circles, one centered at p1 of radius d13, the other centered at p2 with radius d23, as shown in Figure 3. The circles either intersect transversally, resulting in two solutions, tangentially, resulting in one solution, or not at all, resulting in no real solutions. In the figure, a situation with two solutions is shown, with both possible solutions labeled p3. Notice that we can assume point p1 is at the origin and that p2 lies on the positive x-axis a distance d12 from p1, since any other valid configuration could be obtained as a rigid motion of this configuration.

Case 2: (p1, l2) => p3

        
      Figure 4: Placing a point relative to a known point and line

The point p3 is to be constructed from the given point p1 and the given line l2, where p3 has distance d13 from p1 and signed distance d23 from l2. Without loss of generality, assume that l2 coincides with the x-axis and that p1 lies distance d12 from the origin along the positive y-axis, as shown in Figure 4. Then the point p3 must lie on a circle centered at p1 of radius d13 and must lie on a line parallel to l2 and distance d23 away from l2. Since the distance between p3 and l2 is signed, there is exactly one line satisfying these conditions. The intersection of the circle and the line provide the possible locations for p3. As before, there can be two, one, or no solutions depending on the type of intersection. Algebraically, the coordinates of p3 can be found by solving a pair of equations, one of which is linear and one of which is quadratic.

Case 3: (l1, l2) => p3

        
      Figure 5: Placing a point relative to two known lines

The point p3 is to be constructed from the given lines l1 and l2, where p3 has signed distance di3 from li. Assume that l1 coincides with the x-axis and that the angle between l1 and l2 is A12, as shown in Figure 5. Since the distances between p3 and the lines are signed, p3 must be the intersection of two lines, one offset parallel to l1 by d13 and the other offset parallel to l2 by d23. If we ignore the case of parallel lines, there is exactly one solution in this case. Algebraically, this is equivalent to solving a pair of linear equations in the coordinates of p3.

Case 4: (p1, p2) => l3

Case 5: (p1, l2) => l3

These two cases are identical to cases 2 and 3, respectively, since pairwise constraints exist between all three entities. We can therefore easily transform these cases to the previous cases by changing the roles of the geometric entities from fixed to unfixed, and vice versa, as necessary.

Case 6: (l1, l2) => l3

In this case, the angle between each pair of lines must be given as constraints. Since the three lines must define a triangle, the three angles will be either consistent, and determine an infinite family of triangles, or redundant, and have no solutions. We consider this case to be overconstrained because the constraints are not independent.

Graph Transformations

What we have presented above are the basic elements of a two-dimensional constraint solver. There are many extensions possible, some of which we have already considered, and others which remain to be explored. One extension which has proved useful is graph transformations which may increase the constraint information available, thus allowing alternative clusters, possibly with easier constructions. For example, if two angle constraints A and B are given between three lines, a third angle constraint of 180 - A - B degrees can be imposed between the pair of lines not involved together in the first two constraints.

        
      Figure 6: A graph transformation in this case would limit the
                solutions to the problem.

Graph transformations must be applied judiciously, however, as some transformations may limit the generality of the solution. Consider the example from [33] shown in Figure 6. If the incidences shown are required, and in addition point A is constrained to lie on line a, and point C on line c, the constraint graph is as shown on the right in the figure. This implies that either a and c are coincident, or A and C are. However, adding either of these incidence relationships to the constraint graph would eliminate the other possibility, and therewith some of the solutions to the original problem.