# A triangular space-filling curve

Yesterday, I showed you a snowflake.  Today, I’m going to try to explain it. [EDIT: There’s a couple of animations at the end, if you’re not interested in the explanation.]

I was inspired by a space-filling curve called the Hilbert curve.  I wondered how to define a space-filling curve where the successive approximations were based on a triangular grid, rather than a square grid.  So, given a grid like this: we want a path from the bottom-left dot to the bottom right dot (as indicated), passing exactly once through all the other dots in the grid.

The grid above has 12 dots on each side of the triangle.  Supposing we’ve already solved the problem for triangular grids with 5 or 6 dots on each side, we can patch them together into a solution like this: The red segments indicate the places where the components are joined together.  Notice that the left and middle triangles are filled in backwards.  This is so that the solutions for grids of sizes 5 and 6 can be rotated into position, rather than using a reflection; this is just a matter of taste, really.

If we have a grid with an odd number of dots on each side, we have to divide it up into sub-triangles very slightly differently: The top and middle sub-triangles are bigger, and consequently, the join between the bottom and right triangles is now horizontal.

Then, to solve the problem for the grids of sizes 5, 6, and now 7, we can divide them up further, into grids of sizes 2, 3, and 4.  Eventually, we get down to grids that can’t be divided up further, and we have to solve those problems directly, but fortunately, they’re easy: a triangular grid with one dot along each side is just a dot, so there’s nothing to do, and there’s really only one way to deal with a grid of size 2; grids with more dots can be divided up as described above.

So what does it look like?  This: I used Asymptote to draw this, and here’s my code, if you’re interested:

```pair sixty = (Cos(60), Sin(60));
transform rotd120 = rotate(-120), rotw60 = rotate(60);

path tricurve(int n)
{
if (n <= 0) {return nullpath;}
if (n == 1) {return (0,0);}
if (n == 2) {return (0,0)--sixty--(1,0);}
int q = quotient(n, 2);
if (n%2 == 0) {
path l = tricurve(q), s = tricurve(q - 1);
return (reverse(shift((q-1)*sixty)*rotd120*l))
--(shift(q*sixty)*l)
--(reverse(shift((q-1,0)+sixty)*rotw60*s))
--(shift(q,0)*l);
}
path l = tricurve(q + 1), s = tricurve(q);
return (reverse(shift((q-1)*sixty)*rotd120*s))
--(shift(q*sixty)*l)
--(reverse(shift(q,0)*rotw60*s))
--(shift(q+1,0)*s);
}
```

This results in sub-sub-triangles being dealt with multiple times; if I was motivated to make this code more efficient, I might try a dynamic programming approach, caching smaller sub-triangles and later looking them up instead of repeating the computation.

I’m reasonably sure (but haven’t tried writing down a proof) that as the number of dots along the side of the triangle approaches infinity, the curve (which has corners, I admit it) approaches a space-filling curve, continuous, but passing through every point of the two-dimensional triangle (some of them more than once).

An interesting thing about this construction is that it works for any number of dots along the triangle’s sides; the approximations to the Hilbert curve are (as far as I know) only well-defined when the number of dots along a side of the square is a power of 2.

Enough of plain triangles. If we put six of them together in a hexagonal shape, and fill the space outside the now closed curve, we get a familiar-looking snowflake: Here’s some more relevant code:

```import tricurve;

path triflake(int n) {
path sixth = shift(-n * sixty) * tricurve(n);
path half = (rotate(-60)*sixth)--sixth--(rotate(60)*sixth);
return half--(rotate(180)*half)--cycle;
}
```

Because we can use any natural number of dots along the sides of the triangle, we can make animations (you may need to click on them to watch them) showing the snowflake becoming more detailed: or growing: Here’s the code for the first animation:

```import animation;
import triflake;
size(24cm);

int n = 24;
animation a;
draw(scale(n)*triflake(1), invisible);
for (int i = 2; i <= n; i = i+2) {
save();
filloutside(scale(n/i)*triflake(i));
restore();
}
filloutside(triflake(n));
int pause=10000, delay=100;
for (int i = 0; i <= pause; i = i+delay) a.add();

a.movie(delay=delay);
```

I wonder if there’s a better way of making a gif animation pause before repeating; there ought to be.

## 8 thoughts on “A triangular space-filling curve”

1. Ruggero says:

Cool!
Just a comment. Hilbert’s curve has at most two adjacent segments with the same direction. Here there seems to be sections with three.

2. Ruggero says:

Actually no, also Hilbert’s curve has such sections. Please ignore my comment above.

1. Tim Makarios says:

It’s an interesting feature you note, though. Consulting my notebook, I see that when I was first playing with this idea, some of my triangles had four adjacent segments in the same direction. It appears I was using reflections for sub-triangles then, rather than rotations. I also used quite different approaches for triangles with odd or even numbers of dots along the side, which probably interferes with the idea of taking the limit as the number of dots approaches infinity, unless you again restrict yourself to powers of 2.

3. richard lewis says:

I’m not sure this triflake is really a fractal since the nifty shape doesn’t persist for more than two or three iterations, even in your example.

1. Tim Makarios says:

Thanks to your comment, I reviewed the definition of fractal, which appears to be somewhat imprecise, and not universally agreed-upon. Some definitions require that fractals have differing topological and fractal dimensions, which rules out all space-filling curves, including this one.

On the other hand, if you take this construction to its limit (as the number of dots approaches infinity), I’m pretty sure the result does exhibit self-similarity, which is the key point of some other definitions of fractal. In the limit, the top sub-triangle, for example, will be a curve folded up in exactly the same way as the whole triangle is folded up, only smaller.

I concede that the first iteration of the triflake is a pretty poor approximation of the limit, though.

1. Richard Lewis says:

Thanks for your reply. I’ve tried to run the triflake beyond two or three iterations. It always falls apart. Too bad, because it’s such an interesting image. The fractal of mine that you asked about is called a “dense fibonacci word.” You can find a description under “fibonacci word” in Wikipedia and elsewhere. I have several on my fractal page, http://www.richard-lewis.net.

1. Tim Makarios says:

Are you using my Asymptote code to generate the triflake? What goes wrong?

Thanks for the link to your other fractals (which I edited to remove a spurious space). I’m particularly intrigued by numbers 9 to 11. They look like they’re related to the fractals associated with balanced base 2+i, but you seem to have arrived at them by a different, space-filling route. I’d be interested to know more about the constructions of those ones.

1. Richard Lewis says:

I moved my stuff to a new WordPress site, thisfractalworld.com. I will post my version of your triflake there. If it fits… R.