I have been reading for some time about L-Systems, and specifically the Hilbert Space filling curve. I am interested in writing a function to convert upper-triangular matrix coordinates into an 1-dimensional space filling curve coordinates.

The usual Hilbert curve is derived with a first-order curve:

First order Hilbert Curve

Then a series of production rules are iteratively applied to obtain a 1-dimensional coordinate system that is invertible.

Hilbert Curve production rules 2nd order Hilbert Curve 3rd order Hilbert Curve

I have successfully implemented the mapping algorithm listed on Wikipedia,

//rotate/flip a quadrant appropriately
void rot(int n, int *x, int *y, int rx, int ry) {
    if (ry == 0) {
        if (rx == 1) {
            *x = n-1 - *x;
            *y = n-1 - *y;

        //Swap x and y
        int t  = *x;
        *x = *y;
        *y = t;
//convert (x,y) to d
int xy2d (int n, int x, int y) {
    int rx, ry, s, d=0;
    for (s=n/2; s>0; s/=2) {
        rx = (x & s) > 0;
        ry = (y & s) > 0;
        d += s * s * ((3 * rx) ^ ry);
        rot(n, &x, &y, rx, ry);
    return d;
//convert d to (x,y)
void d2xy(int n, int d, int *x, int *y) {
    int rx, ry, s, t=d;
    *x = *y = 0;
    for (s=1; s<n; s*=2) {
        rx = 1 & (t/2);
        ry = 1 & (t ^ rx);
        rot(s, x, y, rx, ry);
        *x += s * rx;
        *y += s * ry;
        t /= 4;

However, I need to add two more first0order curves to this process: one that is a right angle and the other which is a wedge. These two new curves do not need rotations or reflection, and in combination with the usual Hilbert 1st-order curve (with rotation and reflection), one can fill an upper triangular matrix (see my sketch below):

enter image description here

That is, the upper left of the red right-angle again becomes a right angle, the upper right becomes a Hilbert curve, and the lower right part of the right-angle becomes a wedge, and so on.

I would like to implement the above proposed L-System conversion, but every single tutorial on L-Systems is about STARTING AT ZERO and then DRAWING A LINE that fills the space without crossing itself (i.e. writing a string of steps to trace the whole space, instead of converting a subset of coordinates in the space to there 1-D counterpart).

Can anyone offer any intuition on how I might incorporate these new fundamental curves into the existing code? Are there any resources that explain L-System conversions (as opposed to drawing systems), and how to construct them in code??


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.