Graph-based approach for solving geometric constraint problems

This dissertation presents a new graph representation for constraint problems based on the notion of degrees of freedom and valencies. Any geometric primitive (point, line, circle, plane, etc.) possesses an intrinsic degree of freedom in its embedding space. Constraints reduce the degrees of freedom of an object (or a set of objects).;The second algorithm is based on analysis of degrees of freedom. The algorithm analyzes the relative degrees of freedom and dependencies between objects, extracts a connected subgraph, and builds an annotated dependency graph as the result. The dependency graph can then be solved by an extended version of the hybrid solver. This integrated solver can support interactive manipulation of objects or work as an incremental constraint solver. Since changes only occur to the connected subgraph, the effect of the solver is local, and hence lengthy global reevaluation of the solution can be avoided.;In this dissertation, we will present the theoretical background of these approaches, and demonstrate how they can be applied within an interactive design environment.;Two algorithms are developed based on the graph representation. The first is a hybrid approach for geometric constraint solving. The hybrid solver derives a solution from the graph in the form of direct constructions and iterative constructions. A direct construction is applied whenever there is a closed form algebraic or geometric solution. An iterative construction is an adaption of the secant method, to the geometric nature of the problem. The approach combines the advantages of exact symbolic solutions with the universality of iterative numerical methods.