Geometric constraint solving in a dynamic geometry framework.

Abstract

Geometric constraint solving is a central topic in many fields such as parametric solid modeling, computer-aided design or chemical molecular docking. A geometric constraint problem consists of a set geometric objects on which a set of constraints is defined. Solving the geometric constraint problem means finding a placement for the geometric elements with respect to each other such that the set of constraints holds. Clearly, the primary goal of geometric constraint solving is to define rigid shapes. However an interesting problem arises when we ask whether allowing parameter constraint values to change with time makes sense. The answer is in the positive. Assuming a continuous change in the variant parameters, the result of the geometric constraint solving with variant parameters would result in the generation of families of different shapes built on top of the same geometric elements but governed by a fixed set of constraints. Considering the problem where several parameters change simultaneously would be a great accomplishment. However the potential combinatorial complexity make us to consider problems with just one variant parameter. Elaborating on work from other authors, we develop a new algorithm based on a new tool we have called h-graphs that properly solves the geometric constraint solving problem with one variant parameter. We offer a complete proof for the soundness of the approach which was missing in the original work. Dynamic geometry is a computer-based technology developed to teach geometry at secondary school, which provides the users with tools to define geometric constructions along with interaction tools such as drag-and-drop. The goal of the system is to show in the user's screen how the geometry changes in real time as the user interacts with the system. It is argued that this kind of interaction fosters students interest in experimenting and checking their ideas. The most important drawback of dynamic geometry is that it is the user who must know how the geometric problem is actually solved. Based on the fact that current user-computer interaction technology basically allows the user to drag just one geometric element at a time, we have developed a new dynamic geometry approach based on two ideas: 1) the underlying problem is just a geometric constraint problem with one variant parameter, which can be different for each drag-and-drop operation, and, 2) the burden of solving the geometric problem is left to the geometric constraint solver. Two classic and interesting problems in many computational models are the reachability and the tracing problems. Reachability consists in deciding whether a certain state of the system can be reached from a given initial state following a set of allowed transformations. This problem is paramount in many fields such as robotics, path finding, path planing, Petri Nets, etc. When translated to dynamic geometry two specific problems arise: 1) when intersecting geometric elements were at least one of them has degree two or higher, the solution is not unique and, 2) for given values assigned to constraint parameters, it may well be the case that the geometric problem is not realizable. For example computing the intersection of two parallel lines. Within our geometric constraint-based dynamic geometry system we have developed an specific approach that solves both the reachability and the tracing problems by properly applying tools from dynamic systems theory. Finally we consider Henneberg graphs, Laman graphs and tree-decomposable graphs which are fundamental tools in geometric constraint solving and its applications. We study which relationships can be established between them and show the conditions under which Henneberg constructions preserve graph tree-decomposability. Then we develop an algorithm to automatically generate tree-decomposable Laman graphs of a given order using Henneberg construction steps.