Hacker News Reader

Comment by wfunction | Hacker News Reader

Would someone please explain to me how you one convert between the 1D and 2D coordinates of a Hilbert curve? Is there a formula for it? The drawings look nice but they don't tell you how to actually do the conversion, which seems to be the crucial piece of the data structure.

View on HN

If you don't mind worse order-preserving behavior, you can use z-order curves. Encoding and decoding coordinates can then be done by (de)interlacing the bits of (X,Y), which is quite simple: https://fgiesen.wordpress.com/2009/12/13/decoding-morton-cod...

Here is Google's code for doing it:

https://code.google.com/p/s2-geometry-library/source/browse/...

The lookup table it references is generated up here:

https://code.google.com/p/s2-geometry-library/source/browse/...

Thanks!

This is a great reference that I relied on while struggling with my own implementation:

http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-...

In contrast there is an incomprehensible bit of code by Ken Musgrave in Graphics Gems II: http://www.realtimerendering.com/resources/GraphicsGems/gems...

(peano not hilbert but very similar idea)

I was looking for the same thing, this article below has an incredible explanation of the algorithm using Python:

http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-...

There is a sample of code in the Wikipedia page about it. https://en.m.wikipedia.org/wiki/Hilbert_curve

The links the authors provide to learn more about the HSFC probably discuss it too!

Thanks!

I recommend you to read these two sources:

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=731...

http://www.fundza.com/algorithmic/space_filling/hilbert/basi...

I suspect that there are more efficient ways to do this, but simple recursion should work. Divide the curves into quadrants[0]. We know that a given point should be in the same quadrant in both the 1D and the 2D curve. Due to the fractal nature of the curve, you can repeat this procedure on the given quadrant.

[0] For the 2D version, split divide the quadrants with the center x and y axis. For the 1D version, just break it into four equal length pieces.

This is called a quadtree. Here's a comparison: http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-...

Reply on news.ycombinator.com