A Simple Algorithm for generating the H-curve

So about four years ago I came across this paper by Martin Wattenberg, where he described the Jigsaw Map:

http://hint.fm/papers/158-wattenberg-final3.pdf

I liked the idea of it, but could not find any implementation of the H-curve required to build one, so into the mental archives of half-forgotten interesting ideas his paper went.

A few months ago I realized that there is actually a really, really simple way to construct these curves - simpler than… I would say almost anything that isn’t a Z-curve. I lacked the motivation to implement it though. Then yesterday @mootari shared a cool work-in-progress on twitter that relied on a different Hamiltonian space-filling curve, reminding me I still had that half-finished idea of creating H-curves. So I just spent the better part of my Sunday writing this notebook.

The most interesting property of the H-curve is the strong locality property, which is better than for any other known curve (and conjectured to be optimal). It becomes almost intuitively visible if we plot the curve as a gradient:

Maybe other people here will find a use for that. For example, as an alternative to the Hilbert curve in

Other potential next steps: implementing my own ZH-hybrid?

(It probably won’t have the optimal locality that a pure H-curve has, but it has the alternative feature that the two points that are the furthest away from each other are also in opposite corners in 2D)

5 Likes

Done:

Better than the Z-curve, but no better than the Hilbert curve - it’s even seems a little bit worse :confused:. What the heck, I was promised better locality!

EDIT: Ok, I think I have a hypothesis what might be the reason for this. The locality property tells you the upper bound for the distance between two points on the curve, but it says nothing about the axis-aligned bounding box of those two points. My suspicion is that the H-curve has larger AABBs than the Hilbert curve because it has a lot more diagonal movement back and forth. Maybe I can convince a mathematician out there to come up with a way to prove the upper bounds for that for various curves - seems like a relevant metric for many applications.

And also done:

Well… it’s different but I don’t see an immediate reason to believe one is better than the other :man_shrugging:

Meh. I didn’t expect world-shattering results but I did expect some improvement. Maybe I’m doing it wrong?

1 Like

I see clear improvements! Less individual jumps that lead to “fault lines”, and a longer continuity of some paths.

2 Likes

I guess it is a bit smoother :slight_smile:

I went back and added a HI-curve version as well - it should be nearly identical to the H-curve when “zoomed out”, but it has added rotational symmetries at the finest level of detail that should make a difference at the pixel level:

image image image

It looks like when compared to the H-curve the HI-curve sometimes removes fault lines and sometimes adds them - I wouldn’t be surprised if that is related to how much rotational movement is present