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.
Given a value how do you determine the granularity? How do you tell whether a leading 00 indicates a lower resolution quad or a higher resolution one in the 0th corner?
If you take a square, and split into 4, that has 2-Bit indexes. If your square has been split twice, it has 4-bit indexes for each of the tiniest sub-squares. So 'granularity' is a function of 'number of splits'. Quadrant a=00, b=01, c=10, d=11. So a bit sequence like 0110, would mean subquadrant 'c', within subquadrant 'b'. Each additional pair of bits added onto the right side "zooms you in" deeper by choosing which quadrant to jump to within a given square. Each time you zoom in, that requires two additional bits. Upper right hand corner would be an infinite series of 01010101010101 repeating. Top right quad of top right quad of top right quad, etc.
But most of the time these numbers will be represented in fixed size integers (64 bit words for example); there is no easy way to represent the bit sequence 0110 without making it at least 00000110, but more likely 64 bits, which becomes ambiguous; is this the top left of the top left of the top left of the top right of the bottom right (or whatever those coordinated might represent)? Or do we only look at the last two pairs? how many bits are significant? When sequential integers are used as described, there's no ambiguity; you can always figure out what where a value's quad is positioned from its magnitude.
There are many times in software development where you have an array of bits. By definition, an array doesn't have anything "in front" of it. Implementing an array of bits in a computer is a different matter. Normally you store bytes (8 bits at a time), but that's just an implementation detail, and only because computers handle bytes as the fundamental unit. Each two contiguous bits in a bit array can be used to "pick a quadrant" to zoom into a square, recursively. There is no limit or definition of how long the array needs to be unless you want to pre-specify that. You are basically confusing the concepts "Bit Array" with "Two's Compliment Integer storage". These two things are completely separate concepts of storage.
But the point of the representation is that locations can easily and unambiguously be stored in a single number, say a 64bit integer. A bit array necessarily has some overhead to specify the number of bits; something unnecessary in this proposal. Yes a standard using two bits per sector and specifying how many bits have been used in the actual representation is easier for a human to start to decipher, but it requires more information to be unambiguous and doesn't have as nice a binary representation (I'd rather have a fixed sized larger representation that the more complex one needed for an arbitrary sized bit array).
I was talking about pure arrays of bits, as a theoretical construct, but you are right to notice that if not all your arrays are the same length, then each array needs to specify a length. 64-bit integers are like bit-arrays where each array is pre-defined to be 64-bits long and therefore doesn't need to store its length. You could define all your bit arrays to be 8 bytes long each and accomplish the same thing. Your better tact at shooting holes in the bit-array approach is not from memory consumption (you loose on those grounds), but you from a 'performance' standpoint, you can make the case the integer comparisons all take one clock cycle, and operations on bit-arrays are slower, because you have to check each bit individually to do logic. Summary: For storage size, bit-arrays win, and for performance integers win. So based on system needs you'd choose a solution, weighing the pros/cons.
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!
This process is known as Z-Order Curve (http://en.wikipedia.org/wiki/Z-order_(curve)). 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.
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)
Thanks for the link. I was familiar with google's system from when I worked there but couldn't find a good description of it so I assumed it was purely internal.
The PYXIS spatial indexing scheme takes a similar approach, with a few interesting advantages (and undoubtedly some consequent disadvantages to go with them).
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:
- 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.
- 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.
- 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.
(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.)
I was thinking "why not a Hilbert curve?" but (from your link):
"As an alternative, the Hilbert curve has been suggested as it has a better order-preserving behaviour, but here the calculations are much more complicated, leading to significant processor overhead."
I did give Hilbert curves a try at one point, what made me go with z-order instead is that there's an elegant way to convert between coordinates and z-order quads (which I'll describe in a later post) and I couldn't find something similar for Hilbert quads.
That's an exaggeration. The Hilbert curve calculations are also done using bit flipping. They are harder to understand, but are not that cpu-intensive.
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.
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?
