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));
  a.add();
  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.

Advertisements

3 thoughts on “A triangular space-filling curve

  1. 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.

    1. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s