Space filling H-curve and reconstructing the L-system rules

There exists an interesting, yet relatively obscure, space-filling curve known as the H-curve. It was introduced by Rolf Niedermeier, Klaus Reinhardt, and Peter Sanders in their 1997 paper titled "Towards Optimal Locality in Mesh-Indexings". The authors argue that the H-curve holds superior locality properties compared to the well-known Hilbert curve: the difference being 2 versus sqrt(6). They further claim that H-indexings optimally preserve locality among all cyclic indexings. Though I've not reviewed their proofs personally, I proceeded with the assumption that they're error-free.

Unfortunately, the reference Java implementation is far from being straightforward to comprehend and replicate. However, in 2021, Job van der Zwan made a contribution to the development of the H-curve and came up with a new algorithm. His work inspired me to dedicate some time and try a different approach.

In this article, I introduce a different algorithm that generates the H-curve using a Lindermayer system. Additionally, I provide a brief outline of my thought process as I reconstructed the L-system rules.

I began by creating a mental model of the H-curve and manually writing Logo-like instructions up to the third order using the following notation:

F: move and draw line in the current direction
-/+: rotate around Y axis (clockwise/counter-clockwise)

Order 1:

F-F-FFF-F-F+F+F-F-FFF-F-F

FFF-F-F+F+F-F-FFF-F-F+F+FFF+F+F-F-FFF-F-F+F+F-F-FFF+F+FFF-F-
F+F+F-F-FFF-F-F+F+FFF+F+F-F-FFF-F-F+F+F-F-FFF

FFF-F-F+F+FFF+F+F-F-FFF-F-F+F+F-F-FFF+F+FFF-F-F+F+F-F-FFF-F-
F+F+FFF+F+F-F-FFF-F-F+F+F-F-FFF+F+FFF-F-F+F+FFF+F+F-F-FFF+F+
FFF-F-F+F+F-F-FFF-F-F+F+FFF+F+F-F-FFF-F-F+F+F-F-FFF+F+FFF-F-
F+F+F-F-FFF-F-F+F+FFF+F+F-F-FFF+F+FFF-F-F+F+FFF+F+F-F-FFF-F-
F+F+F-F-FFF+F+FFF-F-F+F+F-F-FFF-F-F+F+FFF+F+F-F-FFF-F-F+F+F-
F-FFF+F+FFF-F-F+F+FFF+F+F-F-FFF+F+FFF-F-F+F+F-F-FFF-F-F+F+
FFF+F+F-F-FFF-F-F+F+F-F-FFF+F+FFF-F-F+F+F-F-FFF-F-F+F+FFF+F+
F-F-FFF

I noticed that these sequences were highly symmetrical and bidirectional up to the mid-point, which I will call the "bridge" (or corpus callosum on a fancy day):

F-F-FFF-F-F   +F+   F-F-FFF-F-F
->            ___            <-

To streamline the pattern, I decided to discard mirrored segments, splitting these sequences in half:

1/2 (bridge: +F+):

1: F-F-FFF-F-F

2: FFF-F-F+F+F-F-FFF-F-F+F+FFF+F+F-F-FFF-F-F+F+F-F-FFF

3: FFF-F-F+F+FFF+F+F-F-FFF-F-F+F+F-F-FFF+F+FFF-F-F+F+F-
   F-FFF-F-F+F+FFF+F+F-F-FFF-F-F+F+F-F-FFF+F+FFF-F-F+F+
   FFF+F+F-F-FFF+F+FFF-F-F+F+F-F-FFF-F-F+F+FFF+F+F-F-FFF-
   F-F+F+F-F-FFF+F+FFF-F-F+F+F-F-FFF-F-F+F+FFF+F+F-F-FFF

The mirrored structure remained intact–unsurprisingly so, as this curve fills space in four directions. But this time, the bridge became FFF.

Continuing my "surgical" approach:

1/4 (bridge: FFF)

1: F-F-

2: FFF-F-F+F+F-F-FFF-F-F+F+

3: FFF-F-F+F+FFF+F+F-F-FFF-F-F+F+F-F-FFF+F+FFF-F-F+F+F-F-
   FFF-F-F+F+FFF+F+F-F-FFF-F-F+F+F-F-FFF+F+FFF-F-F+F+

This time the bridge is F-F-.

1/8 (bridge: F-F-):

1: N/A

2: FFF-F-F+F+

3: FFF-F-F+F+FFF+F+F-F-FFF-F-F+F+F-F-FFF+F+FFF-F-F+F+

Unable to break the sequence into smaller segments, I assumed that the remaining part must be the "kernel" (a term, I believe, I have just made up.)

For a sanity check, I compared these sequences to the Hilbert curve–this was the "a-ha" moment.

Hilbert Curve:
A => +BF−AFA−FB+
B => −AF+BFB+FA−

Assuming that FFF-F-F+F+ is the kernel, I could take it and substitute patterns in the higher order sequence, like this:

3: FFF-F-F+F+FFF+F+F-F-FFF-F-F+F+F-F-FFF+F+FFF-F-F+F+
A': FFF-F-F+F+
3': AFFF+F+F-F-AF-F-FFF+F+A

Using the structure of the Hilbert curve as a guide (it follows the same patterns to some extent), I also came up with a mirrored pattern B' and replaced the remaining subsequences:

3: FFF-F-F+F+FFF+F+F-F-FFF-F-F+F+F-F-FFF+F+FFF-F-F+F+
A': FFF-F-F+F+
B': +F+F-F-FFF
3': AFFFB-F-FB+F+A

With "3'" as one of the final rules, I could then mirror it to generate its twin counterpart:

A: AFFFB-F-FB+F+A
B: B+F+AF-F-AFFFB

As the next step, I travelled back from the partial 1/8th sequence to the complete set of rules one order at a time.

1/8 -> 1/4 (bridge: F-F-):

This curve looks like the original H-curve I began with. The difference is it starts from a corner, not from the center of the space. However, this could be already enough for some applications.

A: BF-F-B
B: BFFFC-F-FC+F+B
C: C+F+BF-F-BFFFC

1/4 -> 1/2 (bridge: FFF)

A: BF-F-BFFFC-F-FC
B: BFFFC-F-FC+F+B
C: C+F+BF-F-BFFFC

1/2 -> 1 (bridge: +F+). The final H-curve:

H-curve:
A: BF-F-BFFFC-F-FC+F+BF-F-BFFFC-F-FC
B: BFFFC-F-FC+F+B
C: C+F+BF-F-BFFFC

I entered these rules into an L-system playground, and they generated the same curve I had started with. It took me about two days and a bunch of unsuccessful attempts as I never reconstructed L-rules before. But I am happy now and can continue with my other research topics.

P.S. H-curve implemented in Javascript:

const axiom = "A";
const rules = ["A => BF-F-BFFFC-F-FC+F+BF-F-BFFFC-F-FC",
	       "B => BFFFC-F-FC+F+B",
	       "C => C+F+BF-F-BFFFC"].map(el => el.split(" => "));

function* lindenmayer(n) {
    if (n==0) return yield axiom;

    for(const rule of lindenmayer(n-1)) {
	for (inst of rule.split("")) {
	    const match = rules.find(([rule]) => rule === inst)
	    match ? yield* match[1] : yield inst;
	}
    }
}

const order = 1;
const step = 1;
let x = 2**order;
let y = 2**order-1;
let angle = 0;
const rotate = 90 * Math.PI / 180;
const points = [[x, y]];

for(const inst of lindenmayer(order)) {
    switch(inst) {
	case "+":
	    angle += rotate
	    break;
	case "-":
	    angle -= rotate
	    break;
	case "F":
	    x1 = Math.cos(angle) * step;
	    y1 = Math.sin(angle) * step;

	    const nx = Math.round(x + x1);
	    const ny = Math.round(y + y1);

	    points.push([nx, ny]);

	    x = nx;
	    y = ny;
	    break;
    }
}

console.log(points)