Efficiency Considerations
An important goal of our constraint solver is to achieve interactive speed.
The system as developed has two components, a graphical user interface (GUI),
and the constraint solver itself. These two components communicate with each
other via the textual Erep solid modeling scheme.
Figure 1 indicates the information flow of the system.
Figure 1: Architecture of the constraint solver system
The textual problem specification is handed to the constraint solver
which translates the constraints into a graph, and, as described
elsewhere,
solves them by graph reductions.
The solver capabilities are the consequence of certain
construction steps
that have been implemented.
If a particular constraint problem can be solved using these
steps, then our solver will find a solution.
Where the construction steps involve ruler-and-compass constructions, only
quadratic equations need to be solved.
But some construction steps are permitted that are not
ruler-and-compass, and in those situations the roots of a univariate
polynomial are found numerically.
This polynomial has been precomputed except for
the coefficients which are functions of specific constraint
values.
A well-constrained geometric problem can have exponentially
many solutions in the number of constraints.
This is because the solutions correspond to the algebraic set of a
zero-dimensional ideal whose
generating polynomials are nonlinear.
Our solver can determine all possible solutions.
But doing so every time would waste time and overwhelm the user.
So, certain heuristics
narrow down the solutions to a
final configuration that corresponds to the intended solution with
high probability.
In case a different solution is wanted, the
solver can be redirected
to the intended solution interactively.
