Hilbert Curves & Polyhedrons for Geo-Indexing | ArangoDB Blog 2012

6 Comments

1. Karussell on April 4, 2012 at 8:57 pm

   Who was earlier? Mr Parker or this guy here:

   http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves

   Reply
   • Richpark on April 5, 2012 at 6:48 am

     Apologies if you felt I was claiming that using Hilbert Curves for indexing on the Earth’s surface was original.  Of course it was not.  Martin Schoenert suggested I look at it, as it might be better than the Z-curve I originally proposed to use.  It was use of the observation that one can store, in each node of a binary search tree, the maximum distance to some fixed points and thereby effectively make “rectangles” even on the curved surface of a sphere that I though might be new.

     Reply
     • Karussell on April 5, 2012 at 10:40 am

       I see, I probably misinterpreted the title and in the video.

       One question: do you need to store this ‘maximum distances’ information into the pots? In my implementation I’m not using this trick (+ I’m not sure I’ve understood it properly) but I’m using a bounding box calculated on the fly while searching – is this the same idea?

       I can calculate the bounding box of a branch-node easily derived from the current geo string

       Reply
       • Richpark on April 5, 2012 at 12:42 pm

         Calculating the bounding box on the fly is not so good for three reasons.  Firstly you must compute the maximum box of all points within the Hilbert Curve bounds, so that the bounds are not so tight – it is better to compute them for the points you actually have, not the curve.  Secondly to reverse-engineer the Hilbert Curve into distances is very time consuming in itself.  Thirdly I found five points were rather better, so that the bounding “box” was in fact a pentagon.

         Reply
2. Karussell on April 4, 2012 at 9:00 pm

   BTW: geostrings (called spatial key from me) are implemented in Java here:

   https://github.com/karussell/GraphHopper/blob/master/src/main/java/de/jetsli/graph/geohash/SpatialKeyAlgo.java

   resulting in Z curves … here is a quadtree implemented with this

   https://github.com/karussell/GraphHopper/blob/master/src/main/java/de/jetsli/graph/trees/QuadTreeSimple.java

   Reply
3. Using Hilbert curves and Polyhedrons for Geo-Indexing « Another Word For It on April 5, 2012 at 9:38 pm

   […] Using Hilbert curves and Polyhedrons for Geo-Indexing […]

   Reply