I think rather than using decimal numbering system lots of your logic (like finding the parent square, or all its children), if not all of it, really calls for a binary scheme: like this: First two bits defines which quad you are in (relative to root square), then the second two bits represents which quad within the quad you are in, and on down recursively. The number of bits in your system is perfectly determinable based on the granularity, you go for. Then bit masks, can be used for determining what are all the children of a given block (as integers), and what are all the parents. So the definition of your bit sequence IS 1) as efficient as possible with storage, 2) provides actual "free functionality" by bit masks, and so forth.
Great job on taking the time to do a writeup! Last year, I designed a similar algorithm from scratch one weekend to implement some complex spatio-temporal visualizations. I was ecstatic because it was faster than Quadtrees. I thought that I had invented something new. Later, I read somewhere that a mathematician had invented that algorithm close to 200 years ago! Not only did that burst my bubble, but it also made me feel stupid for not having found it. Anyway, using this approach I was able to implement a Linear Quadtree in Javascript using Typed arrays that could accommodate 1 Arc Second resolution all the way up to 60 Arc Minutes if you wanted to. It is extremely performant and I ended up using it to do some really neat animated heatmaps. I went through the invention process myself only to realize someone had thought of that problem ~200 years ago. No idea why that person did it though. I suppose mathematicians did that back in the days....wonder what the application was!<p>This process is known as Z-Order Curve (<a href="http://en.wikipedia.org/wiki/Z-order_(curve)" rel="nofollow">http://en.wikipedia.org/wiki/Z-order_(curve)</a>). You can quickly get to an index in memory or a cell/location on the map using Morton-Encoding. It is also known as a Linear Quadtree.<p>Foundations of Multidimensional and Metric Data Structures is a great resource! Check it out at <a href="http://gisandscience.com/2009/08/21/award-winning-book-by-hanan-samet-details-spatial-data-indexing-processes/" rel="nofollow">http://gisandscience.com/2009/08/21/award-winning-book-by-ha...</a>.
Here is a good explanation of the Quad-Key system used by both Bing and Google maps. <a href="http://msdn.microsoft.com/en-us/library/bb259689.aspx" rel="nofollow">http://msdn.microsoft.com/en-us/library/bb259689.aspx</a><p>Similar, but without sacrificing accuracy for built-in zoom information. Due to it's layout, they also support using bit -wise operators for all of their operations (since in reality these systems are all just interleaved x/y bits)
<i>Unlike the existing coordinate systems I could find described on the web, a z-quad doesn’t represent a point but a square with an area</i><p><a href="http://en.m.wikipedia.org/wiki/Geohash" rel="nofollow">http://en.m.wikipedia.org/wiki/Geohash</a>
The PYXIS spatial indexing scheme takes a similar approach, with a few interesting advantages (and undoubtedly some consequent disadvantages to go with them).<p><a href="http://www.pyxisinnovation.com/pyxwiki/index.php?title=How_PYXIS_Works" rel="nofollow">http://www.pyxisinnovation.com/pyxwiki/index.php?title=How_P...</a><p>Once you get past the inexplicably florid and fervent language (it's a spatial indexing scheme, guys—not a holy revelation!) there are a couple of cool qualities that stand out to me:<p>- The distribution of indices is very even over the globe. Yes, this scheme is specifically suited to indexing space on a globe, and not much else.<p>- You can be arbitrarily precise by specifying a longer index. Truncating that index just makes it less precise. A major benefit that springs to mind here is the ease with which you could then query for overlapping indices.<p>- Subdividing space by placing child indices at both cell vertices and centroids means there is always overlap between cells at neighbouring resolutions. Whilst this does make the scheme a tad inefficient in terms of storage (which may or may not be the most important detail depending on your application) it has the really neat consequence that any area smaller than a continent is guaranteed to fit wholly within a single index at some resolution. Schemes that avoid overlapping indices or coordinates for the sake of efficiency can never have this property.<p>(I stumbled upon PYXIS while looking for an addressing scheme to rip off for a game project I was working on years ago. Ultimately I decided that PYXIS was not well-suited to my needs and took a much simpler approach, but its novelty stuck it firmly in my mind anyway.)
Very neat. For more on this check out the wikipedia article on Morton order curved (<a href="http://en.wikipedia.org/wiki/Z-order_(curve)" rel="nofollow">http://en.wikipedia.org/wiki/Z-order_(curve)</a>)
As I mentioned in the comment section on the link, I think splitting into 16 and represented as a sequence hex digits would be amazing. It would vastly simplify operations since 123 contains 123(anything else) and is only contained by 12 and 1. Tada.<p>0xDEADBEEF would represent about a .14 mi^2 area. I wonder where it would be... Guess I'll have to implement it to find out! :)
This is neat, but I can't believe the author managed to get through that entire explanation without ever using the word "heap". Perhaps he doesn't realise that his numbering is essentially using the same trick that we use with heaps to implement them within arrays?<p>That doesn't mean it isn't nifty, of course.