# 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](https://www.sciencedirect.com/science/article/pii/S0166218X00003267)". 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](https://observablehq.com/@jobleonard/a-simple-algorithm-to-generate-h-curves). 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 Lindenmayer 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
- `-` and `+`: rotate around Y axis (clockwise/counter-clockwise)
Order 1:
```
F-F-FFF-F-F+F+F-F-FFF-F-F
```
![[h-index-1.png]]
```
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
```
![[h-index-2.png]]
```
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
```
![[h-index-3.png]]
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.
![[h-index-6.png]]
P.S. H-curve implemented in Javascript:
```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);
```