0
$\begingroup$

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??

$\endgroup$

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.