A GRAPH-CONSTRUCTIVE APPROACH TO SOLVING SYSTEMS OF GEOMETRIC CONSTRAINTS

A graph-constructive approach to solving systems of geometric constrai nts capable of efficiently handling well-constrained, overconstrained, and underconstrained configurations is presented. The geometric const raint solver works in two phases: in the analysis phase the constraint graph is analyzed and a sequence of elementary construction steps is derived, and then in the construction phase the sequence of constructi on steps is actually carried out. The analysis phase of the algorithm is described in detail, its correctness is proved, and an efficient al gorithm to realize it is presented. The scope of the graph analysis is then extended by utilizing semantic information in the form of angle derivations, and by extending the repertoire of the construction steps . Finally, the construction phase is briefly discussed.