6 ms·
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 b
by wfunction 11y ago
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.
- perone 11y agoI recommend you to read these two sources: http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=731DBDA9A341BA2474FF162F76A5A604?doi=10.1.1.37.4165&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=731... http://www.fundza.com/algorithmic/space_filling/hilbert/basics/index.html http://www.fundza.com/algorithmic/space_filling/hilbert/basi...
- vmarsy 11y agoThere is a sample of code in the Wikipedia page about it. https://en.m.wikipedia.org/wiki/Hilbert_curve https://en.m.wikipedia.org/wiki/Hilbert_curve The links the authors provide to learn more about the HSFC probably discuss it too!
- wfunction 11y agoThanks!
- gizmo686 11y agoI 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.
- heydenberk 11y agoThis is called a quadtree. Here's a comparison: http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-...
- devbug 11y agoIf 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-codes/ https://fgiesen.wordpress.com/2009/12/13/decoding-morton-cod...
- jonas21 11y agoHere is Google's code for doing it: https://code.google.com/p/s2-geometry-library/source/browse/geometry/s2cellid.cc#205 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/geometry/s2cellid.cc#28 https://code.google.com/p/s2-geometry-library/source/browse/...
- wfunction 11y agoThanks!
- powvans 11y agoThis is a great reference that I relied on while struggling with my own implementation: http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-...
- theoh 11y agoIn contrast there is an incomprehensible bit of code by Ken Musgrave in Graphics Gems II: http://www.realtimerendering.com/resources/GraphicsGems/gemsii/Peano/peano.c http://www.realtimerendering.com/resources/GraphicsGems/gems... (peano not hilbert but very similar idea)
- eva1984 11y agoI 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-indexing-with-Quadtrees-and-Hilbert-Curves http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-...