Geometric Constraint Solving and Japanese Sangaku

Sangaku are wooden tablets which were inscribed with Euclidian geometry puzzles and displayed near temples or shrines. Here’s an example of one from over 200 years ago:

 

A statement of the problem is as follows:

The largest circle (shown in red) has diameter AB. The medium circle (shown in green) has a diameter AC where C lies on the line AB. CDB is an isosceles triangle where the lengths of CD and DB are the same. The smallest circle (shown in blue) is tangent to the triangle and both other circles, and has point E at its center.

Prove that the lines AB and CE are perpendicular.

An interesting challenge, but what has this got to do with the D-Cubed constraint solvers? Bear with me – I’ll come back to this.

In my previous post Ian Morrison said that the feature he had implemented in the D-Cubed Components that has the biggest impact on users is the “… automatic solving of over-constrained but consistent configurations …”. In this post, I’d like to explain more about this feature as it is fundamental to the ease of use of a practical constraint solver.

“Over-constrained but consistent” is how we refer to models which include constraints that are redundant but are always satisfied. A simple example is this rectangle:

Clearly, in two dimensions you only need three perpendicular constraints to define a rectangle. Adding the fourth perpendicular isn’t necessary, but it does not conflict with the other three. In a similar way, the opposite sides of the rectangle are geometrically parallel and it isn’t necessary to constrain them.

There are many other examples like this – you might have learnt about some of them at school. For the common cases, the D-Cubed constraint solvers have special-purpose code which will recognise and allow for the configuration. However, there are thought to be an infinite number of cases and it isn’t possible to search for all of them explicitly. So, the project which Ian referred to gives us a general method of handling them.

What this means for users of applications which incorporate the D-Cubed constraint solvers is that they can concentrate on building their models without having to be concerned about the details of exactly which constraints to apply. Any combination of consistent constraints can be applied.

This is even more important in 3 dimensions. Going back to what Ian said: “In 3 dimensions it is almost impossible to constrain a model in a non-redundant way”. We can see this by extending the rectangle example above. Can you say how many perpendicular constraints are needed to make a rectangular box from a collection of points, lines and planes? I think 9 are sufficient if they are put in the right places, but the advantage of the D-Cubed 3D DCM is that you don’t need to know or care.

Coming back to the Sangaku puzzle, it was straightforward to build this model in the D-Cubed 2D DCM test harness, applying constraints as necessary. Once this had been done, the software immediately deduced that the two lines are always perpendicular. Incidentally, there is another place where a redundant constraint can be added – a tangency between the red circle and the green circle.

Finding the solution to this kind of geometric puzzle can be interesting, but it’s not something that you want to force end users to do. Fortunately, the DCM technology takes care of this, and allows engineers to focus on what they are trying to achieve in their designs. Like a lot of powerful, easy to use software, it’s often the things you don’t notice that are the most important.

Mike