Constraint based geometry is a core technology at Saltire. This technology base has been developed under two National Science Foundation SBIR grants. We have over 8 years of experience developing algorithms to build additional functionality on top of geometric constraints. Functionality includes kinematics, rigid body dynamics, tolerance analysis, carpet laying and symbolic geometry.

There are two common approaches to geometry, constructions and constraints.

Constructions

The current terminology has its roots in the ancient part of geometry concerned with the creation of geometrical entities using only a ruler and compass. If one could actually give a sequence of steps (using only a ruler and compass) which would create the required geometrical figure, then this sequence of steps, or instructions, was called a "construction" sequence for the required piece of geometry. Many of these constructions have appeared for hundreds of years, and continue to appear, in elementary texts on plane geometry - the kind of texts which high school students still study.

Constraints

The importance of being able to clearly describe a piece of geometry in a clear and unequivocal way has been realized for thousands of years. For the very simple geometries, for example, triangles, the work of Euclid showed us precisely what information was needed to completely define triangles. However, the difficulties in describing more complex geometries remained for many years. It was not until the 18th century that Gaspard Monge, working at a military academy in the Burgundy region of France, set out a systematic way of describing more practical (real-world) geometries. He pioneered what came to be known as Descriptive Geometry, a subject which was an important part of the engineering curriculum until the use of computers became common. When Computer-Aided Design and Drafting became common it was soon realized that the increased ease of entering more and more complex geometries further stressed the techniques of defining these geometries in a simple way. This, in turn, sparked a new research interest in the development of simple ways of defining complex geometries.

The goal was to be able to define a geometry of arbitrary complexity by using only the simplest of concepts so that people could concentrate on the practical problem at hand and not have to deal with unnecessarily complex mathematical sophistications which were only a means to the end. By examining the way that people actually work in real-world situations it was realized that the natural way of defining geometry was by a sketch together with the definition of certain lengths, angles, parallels, distances, tangencies and similar, very simple, concepts.

It was then noticed that each of these pieces of information can be expressed as one or more mathematical equations. For example, specifying a length is, via the use of Pythagoras’ theorem, equivalent to requiring that a certain quadratic equation be satisfied; giving the lengths of two sides of a triangle is equivalent to prescribing two quadratic equations.

When we use the terminology "Constraints" we are referring to the simple information (lengths, angles, tangency etc.) used to define the geometry. It would certainly be possible to incorporate complex constraints but this would completely defeat the purpose. The entire evolution of this technology has been based on the premise that the constraints used should only be the simple and natural ones which people have used for centuries and the realization that, in fact, these are the only ones needed. Hence it is that using constraints is the natural way to define geometry.

The differences between construction- and constraint-based systems

Although the use of constraints is clearly desirable, there are some difficult technological problems to be overcome. For example, how many, and which, constraints would be needed to define a particular piece of geometry? This is not a difficult problem for a triangle and Euclid had given us the answer a long time ago (two sides and included angle, three sides, etc.) but it was an open question for many years to know how to answer this question for more general geometries. This problem has been solved and there are clever algorithms which run in the constraint-based systems.

These algorithms tell the user if the geometry has been uniquely defined, whether the user has, by mistake, made something inconsistent (for example, how could there be a triangle where two of the sides have unit length and the third side has a length of four!), redundant, or needs more constraints. Further, when the definition is complete, these algorithms can then draw the accurately defined geometry.

The implication of this last statement is critically important for it tells us that via the simple, natural use of constraints, the constraint resolution algorithms have actually produced a construction sequence. Hence a constraint-based system must have all the constructions as well. It is not the case that a construction system uses constructions and a constraint system does not. A constraint-based system also uses constructions. The distinction is that, in a construction-based system the user must define the geometry by explicitly giving the construction sequence. In a constraint-based system, the user has a choice. For simple geometries the user can use any of the constructions (all of which must be there anyway!) but for more complex geometries or for a more natural interface, the user could use constraints - and the system will deduce the construction sequence.

Hence, a constraint-based system can do everything that a construction-based one can do, as well as providing a more natural user interface and the ability to deal with more complex problems.