Geometric Constraint Solver

Overview & Synopsis

A geometric constraint system consists of a finite set of geometric elements, such as points, lines, and circles, along with relationships of different types such as distance, angle, incidence and parallelism. This problem is central to many applications, such as computer-aided design, molecular modelling and recently localization in wireless sensor networks. Solving a geometric constraint system consists of finding real co-ordinates of geometric elements in the Euclidean space. In 2-dimensional geometric constraint solving, graph-based techniques are a dominant approach, particularly in the computer-aided design context. To speed up the resolution process, these methods transform the geometric problem into a graph, which is decomposed into small subgraphs. Each one is solved, separately, and the final solution is obtained by recomposing the solved subgraphs. However, most of the previous research on graph-based approaches has only focused on the decomposition without any atten- tion on what will be decomposed: the geometric constraint graph. Major proposed algorithms are discussed or compared theoretically, without presenting any tests on graphs instances with different structural properties, representing several cases of difficulties. Why? because as far as we know, there is no known algorithm for the creation of non-decomposable graphs or graphs with interesting structural properties that best highlight the efficiency of any algorithm. Our contribution is the design of a simple, but efficient random 2D geometric constraint graph generator. It can be used to make benchmarks for consistent tests, or to observe the behaviour of geometric constraints solving algorithms. It produces problem instances with various sizes and structural properties, covering different cases of complexity. Our design is based on the problem classification reported in the literature. We proved that our proposed generator is complete, customizable, simple and efficient. It has been validated experimentally and some of its properties have been theoretically Gproved.