4 ms·

Google’s S2, geometry on the sphere, cells and Hilbert curve

166 points by perone 11y ago

thrownaway2424 11y ago
http://webcache.googleusercontent.com/search?q=cache:AhGDevVVT_MJ:blog.christianperone.com/%3Fp%3D2840&hl=en&gl=us&strip=1&vwsrc=0 http://webcache.googleusercontent.com/search?q=cache:AhGDevV...
- perone 11y ago
  Thanks. I solved the problem, lots of visits and missing swap space lol.
crazy1van 11y ago
Is it faster for spatial queries to store the S2 cells in a Btree index in a database like the article mentions or to just use something like PostGIS with its gist spatial indices -- specifically, for determining whether points are inside or outside of a polygon?
jacobolus 11y ago
The linked presentation slides give a bit better explanation IMO: https://docs.google.com/presentation/d/1Hl4KapfAENAOf4gv-pSngKwvS_jwNVHRPZTTDzXXn6Q/view?pli=1 https://docs.google.com/presentation/d/1Hl4KapfAENAOf4gv-pSn... Too bad there aren’t more general docs for the library. I still don’t quite understand the benefit of using a single number instead of a pair of numbers for describing a cell in a two-dimensional space. Seems like a pair of 32-bit fixed point numbers would be just as descriptive as a single double-precision float along the hilbert curve. The way they project the sphere onto a cube also leads to cell shapes that aren’t especially relevant to typical human purposes, whereas there are many shapes on a map which align with the latitude/longitude grid.
- perone 11y ago
  It isn't a matter of representation, but also how data structures could take advantage of such representations. B-trees for instance are very efficient with one-dimensional data. Take a look here: http://www.drdobbs.com/database/space-filling-curves-in-geospatial-appli/184410998 http://www.drdobbs.com/database/space-filling-curves-in-geos...
- vmarsy 11y ago
  I think that if you used a pair of numbers you wouldn't be able to do the fast "checking of containment" described by the author, which is just a bitwise comparison apparently. I don't think they use a floating point representation for the 1D hilbert space coordinate. The checking of containment, to verify if a cell is contained in another cell, all you just have to do is to do a prefix comparison. These operations are really fast and they are possible only due to the Hilbert Curve enumeration and the hierarchical decomposition method used.
  - jacobolus 11y ago
    If you had a pair of numbers you could do two bitwise comparisons instead. If you packed both 32-bit fixed point numbers into one 64-bit integer, you might even be able to handle both parts with the same few instructions. In the worst case it would be within a factor of two of the Hilbert-curve version in terms of instructions, and I highly doubt this operation is ever a bottleneck in practice. Would be interesting to see some benchmarks.
- danbruc 11y ago
  The purpose of the space filling curve is to preserve locality when you store the two dimensional data on a one dimensional storage medium. If you used x and y coordinates and stored the data like an image row by row, then data of cells adjacent in the x direction would get stored close together but data of cells adjacent in the y direction would get stored quite a bit away because of the other cells of the rows in between. On the other hand the Hilbert curve keeps cells adjacent in both directions closer together and therefore preserves locality better which in turn means less read head repositioning on spinning disks or a better hit probability when you prefetch adjacent data.
  - david-given 11y ago
    It also allows you to do the opposite, and turn a single-dimensional quantity into two-dimensional coordinates in a useful manner. The most famous example I know is, of course, XKCD's Map of the Internet: https://xkcd.com/195/ https://xkcd.com/195/
wfunction 11y ago
Would someone please explain to me how you one convert between the 1D and 2D coordinates of a Hilbert curve? Is there a formula for it? The drawings look nice but they don't tell you how to actually do the conversion, which seems to be the crucial piece of the data structure.
- perone 11y ago
  I recommend you to read these two sources: http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=731DBDA9A341BA2474FF162F76A5A604?doi=10.1.1.37.4165&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=731... http://www.fundza.com/algorithmic/space_filling/hilbert/basics/index.html http://www.fundza.com/algorithmic/space_filling/hilbert/basi...
- vmarsy 11y ago
  There is a sample of code in the Wikipedia page about it. https://en.m.wikipedia.org/wiki/Hilbert_curve https://en.m.wikipedia.org/wiki/Hilbert_curve The links the authors provide to learn more about the HSFC probably discuss it too!
  - wfunction 11y ago
    Thanks!
- gizmo686 11y ago
  I suspect that there are more efficient ways to do this, but simple recursion should work. Divide the curves into quadrants[0]. We know that a given point should be in the same quadrant in both the 1D and the 2D curve. Due to the fractal nature of the curve, you can repeat this procedure on the given quadrant. [0] For the 2D version, split divide the quadrants with the center x and y axis. For the 1D version, just break it into four equal length pieces.
  - heydenberk 11y ago
    This is called a quadtree. Here's a comparison: http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-...
jkot 11y ago
There is also Healpix and other libraries
dnautics 11y ago
Correct me if I'm wrong but isn't locality unidirectional? Two close points in the plane might by chance be encoded far away on the line if they're unluckily next to a seam.
- jongraehl 11y ago
  Right. Article text says so too.
- guard-of-terra 11y ago
  Theoretically you can try and find projection where most major seams are in un-navigable oceans and it won't hurt that much. My take is that they should allow height to be coded in too.
  - deleted 11y ago
    [deleted]
  - techdragon 11y ago
    I had the fortune to be introduced to this by a Google employee and while they were not from the maps team, they had soaked up enough of the general Google way of doing things that their explanation was able to "hit home" very quickly. As a result one of the first things I asked them was "where are the corners?" and they confirmed my suspicions that they have "tilted" the cube slightly (the vertical edges are not parallel to meridians at the equator) and that a very rough approximate location for two of the corners is one is roughly in the great Australian bight on the South Australian coast line, and another one is roughly in the sea of Okhotsk between Japan and the far eastern half of Siberian region of Russia. TL;DR. Yes, yes they do try to put the vertices in areas where their distortion will be least noticed.
dsymonds 11y ago
There's also a Go port of S2: http://godoc.org/github.com/golang/geo/s2 http://godoc.org/github.com/golang/geo/s2
- logician76 11y ago
  Yeah, it's really awesome. However not complete, but I've added a lot of functionality especially the coverer, there's a pull request for it if you want to take a look.
eveningcoffee 11y ago
I think this is also a great example how Google abandoning the Google Code will affect the availability of previously published work. What I want to tell is that this library is not (yet according to some googling) migrated to the new platform even when it is from people from Google.

166 points by perone 11y ago

http://webcache.googleusercontent.com/search?q=cache:AhGDevVVT_MJ:blog.christianperone.com/%3Fp%3D2840&hl=en&gl=us&strip=1&vwsrc=0 http://webcache.googleusercontent.com/search?q=cache:AhGDevV...

perone 11y ago
Thanks. I solved the problem, lots of visits and missing swap space lol.

crazy1van 11y ago

Is it faster for spatial queries to store the S2 cells in a Btree index in a database like the article mentions or to just use something like PostGIS with its gist spatial indices -- specifically, for determining whether points are inside or outside of a polygon?

jacobolus 11y ago

The linked presentation slides give a bit better explanation IMO: https://docs.google.com/presentation/d/1Hl4KapfAENAOf4gv-pSngKwvS_jwNVHRPZTTDzXXn6Q/view?pli=1 https://docs.google.com/presentation/d/1Hl4KapfAENAOf4gv-pSn... Too bad there aren’t more general docs for the library. I still don’t quite understand the benefit of using a single number instead of a pair of numbers for describing a cell in a two-dimensional space. Seems like a pair of 32-bit fixed point numbers would be just as descriptive as a single double-precision float along the hilbert curve. The way they project the sphere onto a cube also leads to cell shapes that aren’t especially relevant to typical human purposes, whereas there are many shapes on a map which align with the latitude/longitude grid.

perone 11y ago
It isn't a matter of representation, but also how data structures could take advantage of such representations. B-trees for instance are very efficient with one-dimensional data. Take a look here: http://www.drdobbs.com/database/space-filling-curves-in-geospatial-appli/184410998 http://www.drdobbs.com/database/space-filling-curves-in-geos...
vmarsy 11y ago
I think that if you used a pair of numbers you wouldn't be able to do the fast "checking of containment" described by the author, which is just a bitwise comparison apparently. I don't think they use a floating point representation for the 1D hilbert space coordinate. The checking of containment, to verify if a cell is contained in another cell, all you just have to do is to do a prefix comparison. These operations are really fast and they are possible only due to the Hilbert Curve enumeration and the hierarchical decomposition method used.
- jacobolus 11y ago
  If you had a pair of numbers you could do two bitwise comparisons instead. If you packed both 32-bit fixed point numbers into one 64-bit integer, you might even be able to handle both parts with the same few instructions. In the worst case it would be within a factor of two of the Hilbert-curve version in terms of instructions, and I highly doubt this operation is ever a bottleneck in practice. Would be interesting to see some benchmarks.
danbruc 11y ago
The purpose of the space filling curve is to preserve locality when you store the two dimensional data on a one dimensional storage medium. If you used x and y coordinates and stored the data like an image row by row, then data of cells adjacent in the x direction would get stored close together but data of cells adjacent in the y direction would get stored quite a bit away because of the other cells of the rows in between. On the other hand the Hilbert curve keeps cells adjacent in both directions closer together and therefore preserves locality better which in turn means less read head repositioning on spinning disks or a better hit probability when you prefetch adjacent data.
- david-given 11y ago
  It also allows you to do the opposite, and turn a single-dimensional quantity into two-dimensional coordinates in a useful manner. The most famous example I know is, of course, XKCD's Map of the Internet: https://xkcd.com/195/ https://xkcd.com/195/

wfunction 11y ago

Would someone please explain to me how you one convert between the 1D and 2D coordinates of a Hilbert curve? Is there a formula for it? The drawings look nice but they don't tell you how to actually do the conversion, which seems to be the crucial piece of the data structure.

perone 11y ago
I recommend you to read these two sources: http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=731DBDA9A341BA2474FF162F76A5A604?doi=10.1.1.37.4165&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=731... http://www.fundza.com/algorithmic/space_filling/hilbert/basics/index.html http://www.fundza.com/algorithmic/space_filling/hilbert/basi...
vmarsy 11y ago
There is a sample of code in the Wikipedia page about it. https://en.m.wikipedia.org/wiki/Hilbert_curve https://en.m.wikipedia.org/wiki/Hilbert_curve The links the authors provide to learn more about the HSFC probably discuss it too!
- wfunction 11y ago
  Thanks!
gizmo686 11y ago
I suspect that there are more efficient ways to do this, but simple recursion should work. Divide the curves into quadrants[0]. We know that a given point should be in the same quadrant in both the 1D and the 2D curve. Due to the fractal nature of the curve, you can repeat this procedure on the given quadrant. [0] For the 2D version, split divide the quadrants with the center x and y axis. For the 1D version, just break it into four equal length pieces.
- heydenberk 11y ago
  This is called a quadtree. Here's a comparison: http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-...

jkot 11y ago

There is also Healpix and other libraries

dnautics 11y ago

Correct me if I'm wrong but isn't locality unidirectional? Two close points in the plane might by chance be encoded far away on the line if they're unluckily next to a seam.

jongraehl 11y ago
Right. Article text says so too.
guard-of-terra 11y ago
Theoretically you can try and find projection where most major seams are in un-navigable oceans and it won't hurt that much. My take is that they should allow height to be coded in too.
- deleted 11y ago
  [deleted]
- techdragon 11y ago
  I had the fortune to be introduced to this by a Google employee and while they were not from the maps team, they had soaked up enough of the general Google way of doing things that their explanation was able to "hit home" very quickly. As a result one of the first things I asked them was "where are the corners?" and they confirmed my suspicions that they have "tilted" the cube slightly (the vertical edges are not parallel to meridians at the equator) and that a very rough approximate location for two of the corners is one is roughly in the great Australian bight on the South Australian coast line, and another one is roughly in the sea of Okhotsk between Japan and the far eastern half of Siberian region of Russia. TL;DR. Yes, yes they do try to put the vertices in areas where their distortion will be least noticed.

dsymonds 11y ago

There's also a Go port of S2: http://godoc.org/github.com/golang/geo/s2 http://godoc.org/github.com/golang/geo/s2

logician76 11y ago
Yeah, it's really awesome. However not complete, but I've added a lot of functionality especially the coverer, there's a pull request for it if you want to take a look.

eveningcoffee 11y ago

I think this is also a great example how Google abandoning the Google Code will affect the availability of previously published work. What I want to tell is that this library is not (yet according to some googling) migrated to the new platform even when it is from people from Google.