Hacker News Reader

Comment by coffeemug | Hacker News Reader

All the open source implementations (including Mongo, PostGIS, and Rethink) use Google's S2 library (https://code.google.com/p/s2-geometry-library/). Implementing algorithms from scratch would be a huge and extremely bug-prone effort (although tons of fun).

View on HN

Actually, PostGIS does not use s2. I believe it uses its own modified R-Tree index. The main downside to this is that the entire index must be kept in memory, which is one of the the primary motivations for libraries like s2. There are alternatives to s2 as well like tile-cover[1], a tile-based indexer that can run client-side. Most of the NoSQL DBs these days do use s2 though.

[1] https://github.com/mapbox/tile-cover

I work on Google Maps and think s2 is wonderful. It's a mostly overlooked gem. What advantage does tile-cover have over s2?

3 main reasons:

- Runs in browser, for client-side indexing.

- Based off of tiles, instead of s2's 6-faced-cube thing. This allows it to be used with a lot of well established tools and mathematical formulas. Also much easier to reason about IMHO.

- Indexes points about twice as fast at the moment.

I also use s2, and it really is terrific. There are many cases where s2 is the superior choice (mostly due to its hilburt curve indexing scheme).

Ah, great info, thanks!

I know nothing about s2, but PostGIS uses two external libraries for its calculations: Proj4 [1] and GEOS [2].

Proj4 is for working with projections. It comes with a handy command line tool that lets you easily perform chores like converting between coordinate systems/projects.

GEOS is a C++ library (with a C API on top) that's actually a port of a Java library called JTS. It's used for expressing structured geometry/geography primitives and performing calculations on them, as well as encoding/decoding them in the WKT/WKB (text and binary respectively) formats (the PostGIS "geometry" data type). All the geometry testing and manipulation functions, eg. ST_Intersects(), use GEOS.

GEOS actually comes with support for a spatial index called STR, or STRtree, but I believe it's not used by PostGIS. Instead, PostGIS uses Postgres' own GiST, which is a generalization of R-trees that perform better in a relational environment.

[1] http://www.remotesensing.org/proj

[2] http://geos.osgeo.org/

Reply on news.ycombinator.com