I have a friend on the google maps team and we had a brief conversation about this library a few weeks ago while I was helping him out with some projects at home.
If I remember him correctly, this project started off as a 20% time project of just one employee. The more amazing part was it sounded like that employee had been working on the problem, largely by himself, for near a decade.
And now this project, started by one guy, is in production use for an application hundreds of millions (if not billions) of people use daily. All because he just kept working on it. Inspiring.
I'm not sure if that's the best way to describe it. That one employee was Eric Veach, who led the creation of this auction system called AdWords. Then he wrote the first version of SmartAss, the ML system that predicts CTR for AdWords and AdSense. S2 comes from his background in graphics. He had joined from Pixar and won a couple of Oscars. (There's actually someone else at Google who has won more.)
Yes, it was mostly one employee, but it wasn't an ordinary one.
I was playing around with s2 a year or two ago, and it was surprisingly difficult to find information on it, so FWIW here are some links I was able to find at the time if you're looking for some historical reading on s2:
When I was working at Google in 2005ish it was briefly my job to port Dodgeball(1) from an existing PHP codebase to Java on Google infrastructure. It was SO NICE that this library already existed. It made a decent chunk of my work significantly easier.
I didn't know much about S2 geometry before I discovered the library. It was a lot of fun to dive in and learn how it all worked.
from my understanding, H3 doesn't guarantee that a child cell falls strictly inside the geographical region of its parent (since is a hexagon cannot be perfectly comprised of smaller hexagons).
While the hexagon has less distortion - we loose some of the nice child <> parent guarantees that S2 offers in my experience.
Hexagons are all equidistant from their neighbors and all share the same size edge with all neighbors. This allows you to do cool stuff like k-rings. These properties are useful for all sorts of reasons.
With S2 cells there are two different distances to neighbors at the corners vs the sides and the neighbors at the sites have long borders and neighbors at the corners have vertice borders.
Both S3 and H3 are useful, but for different reasons. It's worth knowing the benefits and tradeoffs of both and choosing the solution that fits your particular problem.
H3 uses Buckminster Fuller's Dymaxion project and puts the 20 pentagonal vertices all in the ocean. I'm not sure the impact of this for maritime usage and I'm not sure if there is yet a different orientation that puts all vertices on land, so you can use it for maritime usage without having to concern yourself with these vertices.
> Hexagons are all equidistant from their neighbors and all share the same size edge with all neighbors.
Technically, in spherical geometry this isn't true. It's actually not possible to tile the sphere with regular hexagons (even after including those 12 pentagons). Unlike a planar tiling, some hexagons end up bigger or smaller than others, the internal angles aren't all equal to each other, and the internal angles sum to more than 360 degrees.
Now ignoring some cheats, like just putting 6 vertices on the equator and calling both hemisphere a hexagon, a shape consisting solely of 'h' hexagons and 'p' pentagons will have (h+p) faces, (6h+5p)/2 edges and at most (6h+5p)/3 vertices (we're forbidding the construction where you just cut an edge into two and claim you've created a vertex, so each vertex is part of at least 3 faces). This gives an Euler characeristic of at most:
Since a sphere has a characteristic of 2 you need at least twelve pentagons. And apparently you can achieve this lower bound by subdividing the triangular faces of an icosahedron, leaving you with 12 pentagons at the corners of the icosahedron.
Quick note that may be of interest: S² is the mathematical notation for the "2-sphere", aka what we call a sphere in everyday language. I suppose that's explained by this:
> A unique feature of the S2 library is that unlike traditional geographic information systems, which represent data as flat two-dimensional projections (similar to an atlas), the S2 library represents all data on a three-dimensional sphere (similar to a globe).
(S^2 if the superscript character doesn't show up for you.)
I'm still puzzled why they went with 6 quad-trees, instead of doing an equal-area projection with 2:1 ratio and quad-treeing that instead. You lose a bit for half the map but you do with 6 sides too (takes 3 bits).
Somewhere there's an older doc/presentation that goes into the reasons for the cube in more detail, and if I remember where it is, I'll post it here later.
Consistent uniform cell size, minimizing distortions and relegating them to remote parts of the ocean, grouping land masses together (one cube side is almost pure ocean), optimizing for geodesics, and making it easy to index and reason about were some of the considerations in the design decision. It's been a while so I'm little fuzzy on all the reasoning, but I'm sure someone else on here can provide ptrs or fill in the details.
I reckon an equal area projection for a full hemisphere would lead to some unacceptable degree of distortion. It's hard to say exactly but it shouldn't be too difficult to see that a cube is closer to a sphere than two squares stuck together.
Edit: it may also be easier to figure out which squares are adjacent when using a grid based on a cube.
Yeah I guess it depends on what you're trying to optimize (they use web mercator because roads didn't meet at right angles up north for example). But if you're mostly interested in indexing physical areas with polygon approximations, it seems like having each cell be the same area would be the ideal, but idk.
so clearly folks using this library are using it as part of their own geospatial analysis work, but would it make sense to include this as part of something like PostGIS? It seems like it lets you make much finer grained approximations of complex geometries and would be useful for speeding up things like analyzing geometry intersections/containments.
> This makes it possible to build a worldwide geographic database with no seams or singularities
The geographic database may have no singularities but the coordinate system used does. The coordinate system has a singularity at the origin since it is just an equivalence class on R^3 / {0} but probably (I don't know the domain well) this never comes up in practice.
If I'm reading the signs correctly, your working demo is at maps.google.com
Remember a couple weeks (months?) ago when google changed their maps from being a flat Cartesian style to having a more polar spherical look to them as you actually moved away from the surface of the earth? This is the library responsible for that.
As far as I know, the map tiles google serves are still in mercator projection -- it's just that mercator was always designed to be projected onto a sphere, not a plane, so now it looks better.
What S2 is, is a better way of representing sets of coordinates within GIS systems, such that searching for features that are close to each other, or within a complex polygon, can be performed much quicker than with other coordinate reference systems ie. floating point latitude/longitude pairs. They're storing points on a 3D sphere (unit vectors) as easily subdivisible 64-bit integers which have a logical order which is much faster to index / iterate over nearby areas.
Makes sense for applications like google maps; "find local businesses near point X,Y" etc.
The mercator projection is designed to project a ~sphere onto a plane. The distorted tiles are now being redistorted to drape the plane back onto the sphere.
Yeah I don't actually know if I was using the right terminology. Most of what I wrote in that comment stemmed from me asking a friend 'Hey, so that thing you work on -- looks less flat and more round. What's up with that?'
If I remember correctly, he also mentioned something about the same project being responsible for better stitching and less overlaps/voids in the map.
Thanks for explaining though, helped me understand things a bit better.
Are you sure? I just checked for myself, but (on the google maps version I am served) the south pole is still shows as a black hole when zoomed out far enough that the earth is rendered as a sphere. Also the elongated shape of the tiles near the poles looks an awful lot like a mercator projection.
Pretty sure? I'm just going off a cursory examining of the github repo linked on the website from the OP and a conversation I had in passing with a friend who works on the google maps team.
Also, I'm not a mathematician and everything I know about computer science (and most of math for that matter) I've taught myself or learned on the job. So... maybe I'm using the wrong terminology?
I'm 98% certain the library is the same one currently used on google maps web app.
If I remember him correctly, this project started off as a 20% time project of just one employee. The more amazing part was it sounded like that employee had been working on the problem, largely by himself, for near a decade.
And now this project, started by one guy, is in production use for an application hundreds of millions (if not billions) of people use daily. All because he just kept working on it. Inspiring.