The Hilbert Curve in Java, Lua and C++

I wrote a program a little while ago that draws a Hilbert Curve. Really all I did was adapt the Java source code that’s on the Wikipedia page talking about the curve. That Java source used a class called SimpleGraphics that I’m not familiar with. I wanted to use SDL in C++ for my program. It was easy enough to convert the Java code to C++ but to do the drawing I decided to just implement a SimpleGraphics class in C++ that uses SDL to perform the actions that the program needs.

Since then I revived my interest in integrating scripting with C++ and pulled a Lua interpreter in to that project. Now my program loads a Lua script and executes it. The Lua script has access to the SimpleGraphics class that I wrote. Now that the script interpreter works and can call the drawing methods I decided to take the algorithm for drawing the Hilbert curve and implement that as a Lua script. It was actually pretty easy. The resulting source code works as a sort of Rosetta stone for the three languages.

Here’s the Java version (courtesy of Wikipedia)

import java.awt.*;
import java.applet.*;

public class HilbertCurve extends Applet {
    private SimpleGraphics sg=null;
    private int dist0=512, dist=dist0;

    public void init() {
        dist0 = 512;
        resize ( dist0, dist0 );
        sg = new SimpleGraphics(getGraphics());
    }

    public void paint(Graphics g) {
        int level=4;
        dist=dist0;
        for (int i=level;i>0;i--) dist /= 2;
        sg.goToXY ( dist/2, dist/2 );
        HilbertA(level); // start recursion
    }

    private void HilbertA (int level) {
        if (level > 0) {
            HilbertB(level-1);    sg.lineRel(0,dist);
            HilbertA(level-1);    sg.lineRel(dist,0);
            HilbertA(level-1);    sg.lineRel(0,-dist);
            HilbertC(level-1);
        }
    }

    private void HilbertB (int level) {
        if (level > 0) {
            HilbertA(level-1);    sg.lineRel(dist,0);
            HilbertB(level-1);    sg.lineRel(0,dist);
            HilbertB(level-1);    sg.lineRel(-dist,0);
            HilbertD(level-1);
        }
    }

    private void HilbertC (int level) {
        if (level > 0) {
            HilbertD(level-1);    sg.lineRel(-dist,0);
            HilbertC(level-1);    sg.lineRel(0,-dist);
            HilbertC(level-1);    sg.lineRel(dist,0);
            HilbertA(level-1);
        }
    }

    private void HilbertD (int level) {
        if (level > 0) {
            HilbertC(level-1);    sg.lineRel(0,-dist);
            HilbertD(level-1);    sg.lineRel(-dist,0);
            HilbertD(level-1);    sg.lineRel(0,dist);
            HilbertB(level-1);
        }
    }
}

class SimpleGraphics {
    private Graphics g = null;
    private int x = 0, y = 0;

    public SimpleGraphics(Graphics g) { this.g = g; }
    public void goToXY(int x, int y) { this.x = x;   this.y = y; }

    public void lineRel(int deltaX, int deltaY) {
        g.drawLine ( x, y, x+deltaX, y+deltaY );
        x += deltaX;    y += deltaY;
    }
}

Here’s the C++ version
HilbertCurve::HilbertCurve(SimpleGraphics *graphics)
{
  sg = graphics;
  dist0  = 4096;
  dist = dist0;
}

HilbertCurve::~HilbertCurve()
{
}

void HilbertCurve::paint() {
  int level=10;
  dist=dist0;
  sg->setColour(200, 127, 127);
  for (int i=level;i>0;i--) dist /= 2;
  sg->goToXY ( dist/2, dist/2 );
  HilbertA(level); // start recursion
}

void HilbertCurve::HilbertA (int level) {
  if (level > 0) {
    HilbertB(level-1);    sg->lineRel(0,dist);
    HilbertA(level-1);    sg->lineRel(dist,0);
    HilbertA(level-1);    sg->lineRel(0,-dist);
    HilbertC(level-1);
  }
}

void HilbertCurve::HilbertB (int level) {
  if (level > 0) {
    HilbertA(level-1);    sg->lineRel(dist,0);
    HilbertB(level-1);    sg->lineRel(0,dist);
    HilbertB(level-1);    sg->lineRel(-dist,0);
    HilbertD(level-1);
  }
}

void HilbertCurve::HilbertC (int level) {
  if (level > 0) {
    HilbertD(level-1);    sg->lineRel(-dist,0);
    HilbertC(level-1);    sg->lineRel(0,-dist);
    HilbertC(level-1);    sg->lineRel(dist,0);
    HilbertA(level-1);
  }
}

void HilbertCurve::HilbertD (int level) {
  if (level > 0) {
    HilbertC(level-1);    sg->lineRel(0,-dist);
    HilbertD(level-1);    sg->lineRel(-dist,0);
    HilbertD(level-1);    sg->lineRel(0,dist);
    HilbertB(level-1);
  }
}

Here’s the Lua version

function HilbertA(level, g, d)
  if level > 0 then
    HilbertB(level-1,g,d);
    g:lineRel(0,d);
    HilbertA(level-1,g,d);
    g:lineRel(d,0);
    HilbertA(level-1,g,d);
    g:lineRel(0,-d);
    HilbertC(level-1,g,d);
  end
end

function HilbertB(level, g, d)
  if level > 0 then
    HilbertA(level-1,g,d);
    g:lineRel(d,0);
    HilbertB(level-1,g,d);
    g:lineRel(0,d);
    HilbertB(level-1,g,d);
    g:lineRel(-d,0);
    HilbertD(level-1,g,d);
  end
end

function HilbertC(level, g, d)
  if level > 0 then
    HilbertD(level-1,g,d);
    g:lineRel(-d,0);
    HilbertC(level-1,g,d);
    g:lineRel(0,-d);
    HilbertC(level-1,g,d);
    g:lineRel(d,0);
    HilbertA(level-1,g,d);
  end
end

function HilbertD(level, g, d)
  if level > 0 then
    HilbertC(level-1,g,d);
    g:lineRel(0,-d);
    HilbertD(level-1,g,d);
    g:lineRel(-d,0);
    HilbertD(level-1,g,d);
    g:lineRel(0,d);
    HilbertB(level-1,g,d);
  end
end

level = 9
dist0 = 4096
dist = dist0
sg = simple.SimpleGraphics()
sg:setColour(200, 127, 127)
for i=0,level do
  dist = dist / 2;
  print(dist)
end
sg:goToXY ( dist/2, dist/2 );
print("three")
HilbertA(level, sg, dist); -- start recursion

The funny thing is that I never really analyzed what the code is doing. The Hilbert curve is a space-filling fractal. I find fractals interesting and they have some interesting properties. The Hilbert curve – in the perfect mathematical sense, not just the lines we can draw – actually has a dimension greater than 1 and less than 2 depending on how you define dimensions. You could kind of think of it as the line being so long it just doesn’t fit in one dimension. The same is true of the Sierpinski Gasket and a bunch of other mathematical fractals. I say mathematical fractals to distinguish from real-world fractals which occur frequently in nature and don’t have the perfect regularity that our simple mathematical models do. Even so, there is a fractal dimension that can represent the surface area of our lungs, our brains and heads of broccoli. In nature it’s all about optimization. Our lungs want to have the greatest possible surface area to exchange oxygen with the least possible mass. Broccoli presumably has some similar mission for its little tree bits.

2.6875
Your rating: None Average: 2.7 (16 votes)