Logical Inference and Term Rewriting
This approach applies general logical reasoning techniques to the
geometric problem of constraint solving. This approach has been
taken by Aldefeld [1]
and Bruderlin [10],
among others. As an example of this method, consider the system
described by Bruderlin. Geometric entities are restricted
to points, lines, vectors, and triangles, and the
constraints allowed are distances between points, angles
between lines, or two angles of a triangle. These
geometries and constraints are incorporated into a
set of predicates for the system. A
set of allowable congruence relationships for the
geometries used are established, and then rules of Euclidean
geometry for ruler and compass constructions are applied. These rules
are set up in Prolog, and Prolog rewrite-rules are
used to solve the system. The result is a
construction technique for solving the input
constraint system. All possible physical solutions
can be found using the Prolog backtracking mechanism.
While this
approach has the potential to be a generic solver, as implemented the
system of Bruderlin is an instance solver, since the predicates and
rules use the actual constraint values throughout the deductive
process.
The major advantage of this method is that it avoids
translation of the system into complex algebraic equations. The
limitations are that only constructive geometries
can be handled, and that the method is not
very efficient for large systems of constraints. These disadvantages
are common among this type of solver, and hence they are not often
applied in commercial constraint solvers.
References
- A. Aldefeld [1]
- A. Borning, M. Maher, A. Martindale, and M. Wilson [4]
- B. Bruderlin [10], [11]
- A. Bundy and B. Welham [13]
- J. Cohen [24]
- W. Sohrt [97]
- H. Suzuki, H. Ando, and F. Kimura [106]
- Y. Yamaguchi and F. Kimura [122]
