Introduction
Geometric constraint solving is a problem with applications in many
arenas, such as mechanical engineering, chemical molecular
modeling, and surveying. In each of these communities the problem has
been approached in a variety of ways and with differing levels of
success. The problem consists of a given set of
geometric elements and a description of geometric constraints between
the elements. The goal is to find all placements of the geometric
entities which satisfy the given constraints.
Figure 1: There are infinitely many positions for the blue line
which satisfy the stated constraints.
For example, the set of elements might be a set of three lines,
with the constraints that the first two lines must be perpendicular
and the third must make a specified angle with the first line.
As can be seen from Figure 1, this
particular problem has infinitely many solutions.
An additional constraint such as the length of one segment
between the intersections
of two pairs of lines would tie down a particular solution.
A problem can be
well-constrained,
overconstrained, or
underconstrained,
depending on the relationship between the geometric elements and the number
of constraints. In the example of the three lines in
Figure 1, if
the angle that the third line must
make with the second line were given as an additional constraint,
the problem would be overconstrained,
since that angle is already determined by the first two angle
constraints. An overconstrained problem may have a solution when the
additional constraints are consistent with previous constraints, but
often overconstrained problems have no solution.
