"Do you have a family crest?". Depending on where you live the answer probably ranges from "A what?" to "Of course!". I happen to have one, or more exactly to know the one of my ancestors: "De gueule à la croix d'argent, cantonné de quatres merlettes du même". As a French it's rather unusual I believe, but where I live now, Japan, it seems to be much more common. Maybe the result of the "guillotine", maybe my personal experience bias, I don't know. In any case, japanese family crests are called "kamon" (家紋) and traditionally drawn using a calligraphy brush, ink, a straightedge and a compass only. Some beautfiful examples made by a professional are visible here and a list is available on wikipedia.
The construction of shapes using only a straightedge and compass interests mathematicians since the antiquity and is called straightedge-and-compass construction. It's also known as Euclidean construction, because the possible shapes are those allowed by the first three postulates of Euclid's "Elements". Developping a little tool to generate such constructions was waiting on my todo list. It's now done and I'll go through what's needed to complete it in this article.
Everything starts with two points. They define the position, orientation and size of the result shape, and are the only one freely choosen. Everything else is constructed from them.
From two points A and B, there are only three options: create a line passing through the points, create a circle centered on A and passing through B, or a circle centered on B and passing through A.
As we've exhausted the available points, we need to generate new ones to move forward. The straightedge has no graduation, so there is no way to get directly a point on the line at a given distance. The only options left are the intersections between already constructed geometries. The obvious ones are the circles intersection, giving two points C and D. But we also assume that segments extend to infinity, so we have also two other points E and F from the intersection between AB and the two circles.
From these new points, 9 new segments become possible...
...and 16 new circles can be created. Note here that in strict straightedge-and-compass geometry the compass can't be used to transfer distances: it's possible to create the new circle centered on C with radius CD, but not the circle centered on C with radius EF. However, it is proven that it is always possible to construct a point at a given distance from a given point, with that distance defined by two other points. Hence it doesn't break the rule of straightedge-and-compass geometry to allow (C,EF), it just simplifies things a lot!
As you've probably already guessed, it explodes quite quickly, both in number of geometries and in size. The game is to tame that beast and find one's way in that maze to generate the geometries one wants, draw the relevant pieces and discard the intermediate ones, to get a beautiful kamon or whatever you're drawing.
To navigate that maze, one can identify small "tools" that gives points or geometries of particular interest, and reuse them wherever necessary. The most simple example is how to get the midpoint C of a segment AB. It is the intersection of AB and the segment passing through the intersections of the two circles that can be created from AB. Then if you take the midpoint of AC you get the quarter point of AB, and so on, building up little by little your toolbox.
Now, how can we implement all this? First we need to solve the math problems: how to calculate intersection points between geometries. I like to define segments using parametric equations: \(S(t)=(1-t)A+tB\). No special cases, \(t\) tells you if you're inside the segment (\(t\in[0,1]\)), or on "which" outside, it's neat, easy to code and understand. Finding the intersection between two segments then becomes solving a system of two linear equations with two variables \(S(t)=S'(t')\). For our purpose here it's fine to consider that two overlapping segments have no intersection.
Circles are less easy to work with, but the general equation is fine for now: \(||X-O||^2=r^2\). Finding the intersection between a segment and a circle becomes solving a quadratic equation with one variable \(||S(t)-O||^2=r^2\). And here we have to be a bit careful because there can be two intersecting points. That's not a problem per se, however without a way to deterministically identify which one is which one it becomes completely unusable. A convenient convention is to use the intrinsic parameter of the segment \(t\) and to order intersections accordingly.
Last case, the intersection of two circles. We are back to a system of equations with two variables, quadratic this time. $$ \left\lbrace \begin{array}{l} ||X-O||^2=r^2\\ ||X-O'||^2=r'^2\\ \end{array}\right. $$ Here the problem of identifying the two intersecting points is more difficult. The solution I've settled on is to order them accordingly to their angle relative to the vector from the origin of the first circle to the origin of the second circle. Here again, for our purpose it's fine to consider that two overlapping circles have no intersection.
We have now all the pseudocode necessary to calculate the geometries. All that last is 1) a way to define them and 2) a way to draw them.
To define the geometries, I've used simple text files as input of my tool. Each line contains one command. Eventual indentation and optional commenting out helps keep things clean. The 4 fundamental commands are:
- setRoot x1 y1 x2 y2 which sets the coordinates of the two initial points (always named 'A' and 'B')
- segment S A B which creates a segment named 'S' from point 'A' to point 'B'
- circle C O A B which creates a circle named 'C' with center at point 'O' and radius length equal to the distance between point 'A' and point 'B'
- intersect A B C D which gets the intersection between segments/circles 'A' and 'B' and creates two new points 'C' and 'D' (accordingly to the actual number of intersections). Here I'm using '_' to note a missing or discarded interserction.
For example, to create the first geometries from the two initial points and their intersecting points described earlier:
Note the usage of '_' to ignore irrelevant intersections between S, C1 and C2.
Drawing segments is done efficiently using the Bresenham algorithm. The equivalent for circles is the Midpoint circle algorithm. However, we'll need also to draw arc of circles which need to be approximated with Bezier cubic curve. Given that my tool will *probably* not be used for life and death critical realtime application I think it's justified to prioritize simplicity over efficiency. Obviously, segments and full circles can be represented with Bezier cubic splines. Then we can sacrifice a bit of efficiency to simplify the implementation of geometries drawing. I will convert all geometries to cubic bezier splines and use one single spline drawing routine for all.
Also, defining circle arcs takes three things: the circle and two points on its circumference. But I'll take a shortcut here. For the points I'll consider the projection of any given points on the circle and not restrict to points on the circumference. It's like the restriction about collapsing compass, it doesn't break the rules (getting the projection is immediate: it's the intersection of the circle and the segment from the center to the point) but makes our life much easier. Finally, to define an arc from two points we need to agree on a rotation direction (clockwise or counter-clockwise) but that's a completely arbitrary decision.
I've introduced in a previous article how one can iterate over a spline and you can also refer to this previous article if you need a refresher about Bezier curves. The exact details of the drawing is irrelevant here so I'll simply assume you have a way to turn on/off a pixel at a given location. In the end it becomes one more possible command in our input file: draw G draws the segment/circle 'G'. I've also added a few extra commands to set the color/width/... but won't go into these details.
This is now enough for a complete tool processing description of straightedge-and-compass constructive geometry and outputing an image, but as it is you need to specify all the commands one by one. It's an awfully tedious task. You remember what I've wrote about a 'toolbox'? That's it, lets add a subroutine system to define these little tools. For their definition, three commands:
- subroutine F n m: mark the beginning of a subroutine called 'F' taking 'n' points as input and return 'm' points as output
- return A B ...: return the points 'A', 'B', etc... defined inside the subroutine
- end: mark the end of the subroutine, the lines between 'subroutine' and 'end' are memorised as the body of the subroutine
And one more command to use these subroutines: call F In1 In2 ... Out1 ... which executes the subroutine 'F' with input points 'In1', 'In2', etc... and create new points 'Out1', 'Out2', etc... with the returned points. The tool takes care of checking that the number of arguments matches the subroutine definition. And the execution of subroutine is contextual: each subroutine is executed in its own context to avoid interference between geometries' name.
For the curious programmers, the whole implemetation in C using LibCapy is less than 900 lines of code (with comments) and took me only one day.
Finally I needed a concrete example to test my tool. As I'm writing these lines cherry trees start blossoming here in Kyoto. A cherry flower seems a perfectly appropriate test, so I've designed one and created the corresponding geometry file. The subroutine system works like a charm, allowing to describe the whole geometry in 121 lines only (including comments)! (For the construction of the regular pentagon I've referred to this paper)
The result image:
With all the 240 points, 155 segments and 155 circles used as a background:
And the impressive 1594 lines long log of the whole drawing process.
And that's all for that matter. Happy Spring folks!