Damn Cool Algorithms: Spatial indexing
: quadtrees, Hilbert curves, and geohashing, as seen in Google’s new Closure library. useful for multidimensional addressing in general
(tags: algorithms mapping gis indexing quadtree datastructures spatial geometry)
Quadtrees are used in Oracle’s Spatial geo-spatial – plugin.
It looks like the quad-tree is a quad-tree because you can split a square into four smaller trees, and you can tile a plane with squares.
You can tile the plane using Dragon Curves and each Dragon curve is covered by two smaller Dragon Curves. This means there should be an analogous structure that’s a binary tree. You can even write the coordinates of points in a way where the bits of the coordinates would correspond to the sides of the tree that you follow…