Geometric constraints solver

What are geometric constraints?

Geometric constraints are in it’s simplest form relative relations between entities in (2D/3D/…) space. For example defining

distance between \(P_1\) and \(P_2\) is \(d=3\) meters

is a simple distance relation between point \(P_1\) and point \(P_2\).

Figure 1: Relative distance between two points

As already hinted by the blue lines in figure 1 the orientation and position of this two points is not fixed in space.

In contrast a relation can also be expressed in absolute coordinates

\(P_1\) has coordinate (1, 1) and \(P_2\) has coordinate (4, 1)

this statement also tells us that the distance between point \(P_1\) and point \(P_2\) is 3 meters, but additional information is contained therein.

Figure 2: Absolute distance between two points

This additional information fixes the orientation and position in space, as seen in figure 2.

But very often we humans describe geometric entities in relation to each other, for example describing the dimensions of a piece of paper is done by defining the side lengths and the angle on each corner as seen in figure 3.

Figure 3: Dimensions of a piece of paper

The Orientation and position in space is not relevant for describing this piece of paper.

Machines (computers) on the other hand can deal a lot better with absolute coordinates. But it is a difficult problem to go from relative relations to absolute coordinates. This blog post presents an idea to achieve this.

Simple constraints

For the moment we only consider two types of constraints

distance constraints
angle constraints

Additional types of constraints like parallel constraints will be handled at a later moment in this article.

Distance constraint

This constraint consists of a distance between two points.

A distance constraint is defined by a (symbolic) distance and labels for two points (\(P_1\) and \(P_2\) in figure 4) which have to be distance \(d\) apart.

Angle constraint

This constraint consists of an angle defined by three points.

An angle constraint is defined by a (symbolic) angle and labels for three points (\(P_1\), \(P_2\) and \(P_3\) in figure 5) which encircle an angle \(\alpha\). Convention is that the angle is centered at the second label and rotates clockwise around the second label from the first label till the third label.

From constraints to simplexes

Now imagine a set of constraints and labels (from now on called points). How can we deduce that all the points are fixed relative to each other given the constraints? Are there some points which have conflicting constraints?

This is the hard question we try to solve here.

The main idea is to work with simplexes instead of individual constraints. A simplex is the simplest possible polytope in a given dimension (see figure 6). Polytope meaning a geometric object with faces. E.g. in two dimensions the lowest number of sides we need to form an object in this dimension is three (three lines form a triangle, two lines cannot form a 2D object) and in three dimensions it is four (four triangles form a tetrahedron). It is always \(k+1\) elements from dimension \(k-1\) form an object from dimension \(k\). This faces from the lower dimension \(k-1\) are simplexes themselves.

Figure 6: Simplexes in different dimensions

Now there is one additional hurdle to overcome: how do we get from individual constraints to simplexes?

Looking at it in 2D space

2D Space is quite easy to visualize and does not present a limitation as all the ideas can be generalized to ND space.

Each simplex (triangle) in 2D space needs at least 3 constraints (distance and/or angle) to be sufficiently defined. Therefor we have to find at least three constraints which encompass the same three labels.

For example the set of constraints

distance p1 p2 d1
distance p2 p3 d2
angle p1 p2 p3 a1

encompasses the three labels p1, p2 and p3 which makes the triangle formed by these three labels defined (see figure 7).

Figure 7: A triangle defined by three constraints

While

angle p1 p2 p4 a1
distance p2 p3 d2
angle p2 p3 p1 a2

does encompass four labels p1, p2, p3 and p4 which makes the triangle undefined (see figure 8).

Figure 8: An undefined triangle with three constraints

Neither of the four possible triangles (p1, p2 and p3 or p1, p2 and p4 or p2, p3 and p4 or p1, p3 and p4) encompasses at least three constraints.

But there is also the possibility that there are too many constraints (which may or may not contradict each other). See figure 9 for an example. But contrary to an under-constrained system, an over-constrained system can have viable solutions. The pitfall is that there are dependencies between constraints which are a priori not known.

Figure 9: An over-constrained triangle with four constraints

To recap from our visit to the 2D space:

Systems of constraints can be under, over and correctly constrained
which situation is present can be determined by looking at the simplexes

therefore we have to find a way to go from constraints to simplexes.

Towards a general formula

Let’s look at combination of triangles

asdasd