Repository files navigation

S2 is a library for spherical geometry that aims to have the same robustness,flexibility, and performance as the best planar geometry libraries.

This is a library for manipulating geometric shapes. Unlike many geometrylibraries, S2 is primarily designed to work withspherical geometry, i.e.,shapes drawn on a sphere rather than on a planar 2D map. (In fact, the name S2is derived from the mathematical notation for the unit sphereS².) This makesit especially suitable for working with geographic data.

More details about S2 in general are available on the S2 Geometry Websites2geometry.io.

The library provides the following:

• Representations of angles, intervals, latitude-longitude points, unitvectors, and so on, and various operations on these types.

• Geometric shapes over the unit sphere, such as spherical caps ("discs"),latitude-longitude rectangles, polylines, and polygons. These arecollectively known as "regions".

• A hierarchical decomposition of the sphere into regions called "cells". Thehierarchy starts with the six faces of a projected cube and recursivelysubdivides them in a quadtree-like fashion.

• Robust constructive operations (e.g., union) and boolean predicates (e.g.,containment) for arbitrary collections of points, polylines, and polygons.

• Fast in-memory indexing of collections of points, polylines, and polygons.

• Algorithms for measuring distances and finding nearby objects.

• Robust algorithms for snapping and simplifying geometry (with accuracy andtopology guarantees).

• A collection of efficient yet exact mathematical predicates for testingrelationships among geometric objects.

• Support for spatial indexing, including the ability to approximate regionsas collections of discrete "S2 cells". This feature makes it easy to buildlarge distributed spatial indexes.

On the other hand, the following are outside the scope of S2:

• Planar geometry.

• Conversions to/from common GIS formats.

What do we mean by "robust"?

In the S2 library, the core operations are designed to be 100% robust. Thismeans that each operation makes strict mathematical guarantees about its output,and is implemented in such a way that it meets those guarantees for all possiblevalid inputs. For example, if you compute the intersection of two polygons, notonly is the output guaranteed to be topologically correct (up to the creation ofdegeneracies), but it is also guaranteed that the boundary of the output stayswithin a user-specified tolerance of true, mathematically exact result.

Robustness is very important when building higher-level algorithms, sinceunexpected results from low-level operations can be very difficult to handle. S2achieves this goal using a combination of techniques from computationalgeometry, includingconservative error bounds,exact geometric predicates,andsnap rounding.

The implementation attempts to be precise both in terms of mathematicaldefinitions (e.g. whether regions include their boundaries, and how degeneraciesare handled) and numerical accuracy (e.g. minimizing cancellation error).

Note that the intent of this library is to represent geometry as a mathematicalabstraction. For example, although the unit sphere is obviously a usefulapproximation for the Earth's surface, functions that are specifically relatedto geography are not part of the core library (e.g. easting/northingconversions, ellipsoid approximations, geodetic vs. geocentric coordinates,etc).

Seehttp://godoc.org/github.com/golang/geo for specific package documentation.

For an analogous library in C++, seehttps://github.com/google/s2geometry, inJava, seehttps://github.com/google/s2-geometry-library-java, and Python, seehttps://github.com/google/s2geometry/tree/master/src/python

This library is principally a port of theC++ S2 library, adapting to Go idiomswhere it makes sense. We detail the progress of this port below relative to thatC++ library.

Legend:

• ✅ - Feature Complete
• 🟡 - Mostly Complete
• ❌ - Not available

Encoding and decoding of S2 types is fully implemented and interoperable withC++ and Java.