I’ve been working through some of the exercises posted by @1HaskellADay in an attempt to, if not improve my meager Haskell skills, at least keep them from atrophying too much between those occasions where I get to use them1. For those so inclined my solutions are posted over at github, but please keep in mind that I normally only have around 15 minutes to spend on any given exercise so there are a lot of incomplete solutions, and those that are complete were written with more of an eye towards getting it done quick than getting an optimal solution. So don’t judge me too harshly.
Last week there was an exercise involving the golden and Harriss spirals. The golden spiral part of the exercise was easy while the Harriss was not, mainly due to the hand-wavey nature of the instructions for constructing the spiral in the referenced Guardian article. It seemed like an interesting problem though, so I skipped the next few @1HaskellADay exercises to spend some more time on it (in the process I got to play with gtk2hs and lens as well). In the end, in addition to the routines for generating the Harriss spiral, I had a GUI for viewing it (see here if you can’t wait for the punchline). Given the state of the instructions for generating the spiral in the aforementioned article I though it might be a good idea to record how I generated it here.
To start with we need a rectangle where the ratio of the lengths of its sides is equal to the plastic number, also known as ρ. For now let’s make the rectangle wider than it is tall, once we see how to construct the spiral for a wide rectangle it’s easy to generalize to tall rectangles.
Now we put a square into one of the corners of the rectangle, but which one? The answer to this question decides which way the spiral will spiral: lower left or upper right and we get a clockwise spiral, either of the other two and we get counter-clockwise. For the purposes of this post I’m just going to arbirtrarily pick the lower right corner (this also matches up with that was done in the Guardian article). It doesn’t really matter, as you’ll see in a bit choosing the upper left will give us the same curve except that we skipped a few generations. The other two corners can be acheived using the same code but applying a parity inversion2 (e.g. x -> -x) when we render the curve. Once we’ve picked a corner for the square we need to decide how big to make it, that decision being made by our wanting the two rectangles that we are left with after embedding the square to both have the same ratio of edge lengths as our original rectangle (and this is only possible if our original rectangle has the ratio equal to ρ).
Lets call the construction so far the first generation which has yeilded us a square and two rectangles. The start of the curve goes from the square’s lower left corner to its upper left. We also need to start a second spiral off the endpoint of the first curve segment so it will run from the upper left corner of the square to a spot on the top edge of the square, but we have to do the next generation of splits to figure out where. First we split the smaller rectangle in the same way we split the original by putting a square in the lower right corner. The lower left corner of this new square is the end-point of the second curve segment we started above.
We still need to split the larger rectangle that was leftover from the first generation in order to complete the second generation. Notice that if we put the square in the upper right corner of this rectangle then the square from the first generation and this new square share a corner, the upper left for the original square is the same as the lower right for the new square. This is good since our curve in the first square ends in the upper left corner and in order for it to be continous as it enters the new square it has to enter that square in the lower right corner. Also note the layout of the larger rectangle left over from the split: it’s the same as the first generation only rotated 90 degress counter-clockwise and scaled down be a factor of ρ. The smaller rectangle that we already split is just the original rectangle scaled down 1 + ρ.
To continue note that each time we embed a square in a rectangle we create two new rectangles: a small one that in turn gets split in the same way that the original rectangle but scaled down by 1 + ρ and a large one that is the same as the original rectangle but rotated counter-clockwie 90 degrees and scaled down by ρ. This is the fractal nature of the Harriss spiral. We could take the spiral contained in either of the new rectangles and by doing scaling and maybe a rotation we get back the whole spiral, which is a longwinded way of saying that spiral is self-similar (a hallmark of fractals). This of course raises the question of what the dimension of the spiral is. I haven’t had time to do the work to rigorously show it, but I’d guess that it’s probably ρ by appealing to the physicist’s argument: what else could it be? ρ is the only dimensionless number in the construction of the curve and it’s between one and two as we would expect.
So now we know how to generate the endpoints of the curve segments, but how do we connect them? Originally I just drew circular arcs between the points with a radius that was the distance between the points scaled by some fixed factor. This looked horible due to the curve having kinks at the points where the segments were joined. Using cubic Bézier splines worked much better. To eliminate any kinks at the junctions of the curve segments you just have to require that the first derivative is continuous at the junction which will be satisfied if the vector from P1 to P2 in the second segment is equal to the vector from P3 to P4 in the first segment. This fixes the second control point (P3) of the first segment for us if we also require that the curve always enters a square with its tangent making the same angle with the side linking the curve endpoints and that the distance between P1 and P2 is the distance between the end-points scaled by some constant factor.
The angle and scale factor are adjustable parameters in the Harriss curve program so you can play with them, but the default values seem to produce the nicest looking spiral. I didn’t go to the trouble of working out how requiring continuity of the second and third derivatives at the junctions affects things, but it might remove the angle and scale factor degrees of freedom leaving us with some kind of optimal curve3.
As I mentioned above, I’ve created a program that renders the spiral. It does so generation by generation so that you can watch how the construction plays out. It will also draw the rectangles and squares of the construction as it goes along and will color the squares based on which corner the curves enters the square from (this really shows off the fractal-ness of the construction). You can also control the angle and scale factor that are used to determine the control points for the bezier curve segments. The source code is available over at github.
It does start slowing down if you go much past 12 generations. I haven’t had a chance to do any profiling4 so I don’t know if it’s my code that’s the culprit or if 2^12 bezier curve segments is too much to ask of the Cairo renderer. Either way, unless you’re using a large screen with high resolution, you probably won’t need to go much past 12 generations before the changes are happening at the sub-pixel level and you won’t be able to see them.
Is this all that useful? Not really, it’s more of a “hey, that’s kind of interesting” exercise. Mathematically the interest is less in this spiral itself and more in there being a class of spirals of this sort. Anyways, it was a fun little exercise that allowed me to play with GUI programming in Haskell a bit (and now using MFC at work just seems that much worse).
- Usually this takes the form of small one off utilities, the kind of thing that you’d normally use Python or another scripting language for. Once you get your head wrapped around Haskell I find the terse syntax and composability of the language tend to make writing small utilities really quick, Hoogle makes finding the library you need really easy, the combination of Emacs and ghci makes a good REPL, and if you need to parse something it’s hard to beat Parsec. Of course getting your head wrapped around Haskell can take a while. ↩
- I knew taking quantum field theory back in grad school would pay off some day. It didn’t pay off in the way that I expected, but I’ll take what I can get. ↩
- I’ve put about as much time as I can afford into this for now, so both making the curve infinitely differentiable and figuring out the dimension of the curve will have to be left as exercises for the reader. For now I need to get back to other stuff. ↩
- Update: I’ve now had a chance to do some profiling and the program is spending the vast majority of its time in the Cairo rendering code. ↩