5 ms·

Z-Quads, a spatial coordinate system

31 points by plesner 12y ago

ch 12y ago
Very neat. For more on this check out the wikipedia article on Morton order curved (http://en.wikipedia.org/wiki/Z-order_(curve) http://en.wikipedia.org/wiki/Z-order_(curve))
- frankus 12y ago
  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."
  - gniv 12y ago
    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.
  - plesner 12y ago
    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.
    - axman6 12y ago
      Really looking forward to this post! It's fascinating just how simple this system is; maybe I'll make a simple Haskell library implementing it.
      - plesner 12y ago
        Here it is: http://h14s.p5r.org/2014/09/z-quads-conversions.html http://h14s.p5r.org/2014/09/z-quads-conversions.html
- plesner 12y ago
  Thanks for the link! There's a ton of relevant information there I hadn't seen.
prospero 12y ago
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 http://en.m.wikipedia.org/wiki/Geohash http://en.m.wikipedia.org/wiki/Geohash
- JonathonW 12y ago
  Also, MGRS: http://en.wikipedia.org/wiki/MGRS http://en.wikipedia.org/wiki/MGRS
apu 12y ago
I wonder if existing mipmap algorithms and hardware could be used for this kind of representation?
- theoutlander 12y ago
  This can be done using an Array, so yes you can.
blahedo 12y ago
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? That doesn't mean it isn't nifty, of course.
- plesner 12y ago
  Thanks for the pointer to d-ary heaps, there's some overlap there. You're right -- I simply wasn't aware of how those work.
kinguy 12y ago
Here is a good explanation of the Quad-Key system used by both Bing and Google maps. http://msdn.microsoft.com/en-us/library/bb259689.aspx http://msdn.microsoft.com/en-us/library/bb259689.aspx 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)
- plesner 12y ago
  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.
  - gbhn 12y ago
    The S2 library is here: https://code.google.com/p/s2-geometry-library/ https://code.google.com/p/s2-geometry-library/ It's based on the hilbert curve.
Demiurge 12y ago
what are the pro/cons compared to TMS z/x/y system?
ClayFerguson 12y ago
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.
- plesner 12y ago
  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?
  - ClayFerguson 12y ago
    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.
    - axman6 12y ago
      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.
slashgrin 12y ago
The PYXIS spatial indexing scheme takes a similar approach, with a few interesting advantages (and undoubtedly some consequent disadvantages to go with them). http://www.pyxisinnovation.com/pyxwiki/index.php?title=How_PYXIS_Works http://www.pyxisinnovation.com/pyxwiki/index.php?title=How_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: - 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.)
steanne 12y ago
i worry that this is only applicable to one map projection. (the map is not the territory.)
theoutlander 12y ago
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) 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. Foundations of Multidimensional and Metric Data Structures is a great resource! Check it out at http://gisandscience.com/2009/08/21/award-winning-book-by-hanan-samet-details-spatial-data-indexing-processes/ http://gisandscience.com/2009/08/21/award-winning-book-by-ha....
eximius 12y ago
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! :)

31 points by plesner 12y ago

ch 12y ago

Very neat. For more on this check out the wikipedia article on Morton order curved (http://en.wikipedia.org/wiki/Z-order_(curve) http://en.wikipedia.org/wiki/Z-order_(curve))

frankus 12y ago
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."
- gniv 12y ago
  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.
- plesner 12y ago
  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.
  - axman6 12y ago
    Really looking forward to this post! It's fascinating just how simple this system is; maybe I'll make a simple Haskell library implementing it.
    - plesner 12y ago
      Here it is: http://h14s.p5r.org/2014/09/z-quads-conversions.html http://h14s.p5r.org/2014/09/z-quads-conversions.html
plesner 12y ago
Thanks for the link! There's a ton of relevant information there I hadn't seen.

prospero 12y ago

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 http://en.m.wikipedia.org/wiki/Geohash http://en.m.wikipedia.org/wiki/Geohash

JonathonW 12y ago
Also, MGRS: http://en.wikipedia.org/wiki/MGRS http://en.wikipedia.org/wiki/MGRS

apu 12y ago

I wonder if existing mipmap algorithms and hardware could be used for this kind of representation?

theoutlander 12y ago
This can be done using an Array, so yes you can.

blahedo 12y ago

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? That doesn't mean it isn't nifty, of course.

plesner 12y ago
Thanks for the pointer to d-ary heaps, there's some overlap there. You're right -- I simply wasn't aware of how those work.

kinguy 12y ago

Here is a good explanation of the Quad-Key system used by both Bing and Google maps. http://msdn.microsoft.com/en-us/library/bb259689.aspx http://msdn.microsoft.com/en-us/library/bb259689.aspx 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)

plesner 12y ago
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.
- gbhn 12y ago
  The S2 library is here: https://code.google.com/p/s2-geometry-library/ https://code.google.com/p/s2-geometry-library/ It's based on the hilbert curve.

Demiurge 12y ago

what are the pro/cons compared to TMS z/x/y system?

ClayFerguson 12y ago

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.

plesner 12y ago
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?
- ClayFerguson 12y ago
  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.
  - axman6 12y ago
    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.

slashgrin 12y ago

The PYXIS spatial indexing scheme takes a similar approach, with a few interesting advantages (and undoubtedly some consequent disadvantages to go with them). http://www.pyxisinnovation.com/pyxwiki/index.php?title=How_PYXIS_Works http://www.pyxisinnovation.com/pyxwiki/index.php?title=How_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: - 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.)

steanne 12y ago

i worry that this is only applicable to one map projection. (the map is not the territory.)

theoutlander 12y ago

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) 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. Foundations of Multidimensional and Metric Data Structures is a great resource! Check it out at http://gisandscience.com/2009/08/21/award-winning-book-by-hanan-samet-details-spatial-data-indexing-processes/ http://gisandscience.com/2009/08/21/award-winning-book-by-ha....

eximius 12y ago

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! :)