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 ordered, 1-dimensional space filling curve.
The usual Hilbert space filling curve is derived with a single, first-order curve:
Then
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 first order curves to this process: one that is a right angle and the other which is a wedge. These two new curves do not need to be rotated or flipped, and in combination with the usual Hilbert 1st order curve, one can fill an upper triangular matrix (see my sketch below):
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 restriction 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??