1# Overview
2
3S2 is a library for spherical geometry that aims to have the same robustness,
4flexibility, and performance as the best planar geometry libraries.
5
6This is a library for manipulating geometric shapes. Unlike many geometry
7libraries, S2 is primarily designed to work with *spherical geometry*, i.e.,
8shapes drawn on a sphere rather than on a planar 2D map. (In fact, the name S2
9is derived from the mathematical notation for the unit sphere *S²*.) This makes
10it especially suitable for working with geographic data.
11
12More details about S2 in general are available on the S2 Geometry Website
13[s2geometry.io](https://s2geometry.io/).
14
15## Scope
16
17The library provides the following:
18
19* Representations of angles, intervals, latitude-longitude points, unit
20 vectors, and so on, and various operations on these types.
21
22* Geometric shapes over the unit sphere, such as spherical caps ("discs"),
23 latitude-longitude rectangles, polylines, and polygons. These are
24 collectively known as "regions".
25
26* A hierarchical decomposition of the sphere into regions called "cells". The
27 hierarchy starts with the six faces of a projected cube and recursively
28 subdivides them in a quadtree-like fashion.
29
30* Robust constructive operations (e.g., union) and boolean predicates (e.g.,
31 containment) for arbitrary collections of points, polylines, and polygons.
32
33* Fast in-memory indexing of collections of points, polylines, and polygons.
34
35* Algorithms for measuring distances and finding nearby objects.
36
37* Robust algorithms for snapping and simplifying geometry (with accuracy and
38 topology guarantees).
39
40* A collection of efficient yet exact mathematical predicates for testing
41 relationships among geometric objects.
42
43* Support for spatial indexing, including the ability to approximate regions
44 as collections of discrete "S2 cells". This feature makes it easy to build
45 large distributed spatial indexes.
46
47On the other hand, the following are outside the scope of S2:
48
49* Planar geometry.
50
51* Conversions to/from common GIS formats.
52
53### Robustness
54
55What do we mean by "robust"?
56
57In the S2 library, the core operations are designed to be 100% robust. This
58means that each operation makes strict mathematical guarantees about its output,
59and is implemented in such a way that it meets those guarantees for all possible
60valid inputs. For example, if you compute the intersection of two polygons, not
61only is the output guaranteed to be topologically correct (up to the creation of
62degeneracies), but it is also guaranteed that the boundary of the output stays
63within a user-specified tolerance of true, mathematically exact result.
64
65Robustness is very important when building higher-level algorithms, since
66unexpected results from low-level operations can be very difficult to handle. S2
67achieves this goal using a combination of techniques from computational
68geometry, including *conservative error bounds*, *exact geometric predicates*,
69and *snap rounding*.
70
71The implementation attempts to be precise both in terms of mathematical
72definitions (e.g. whether regions include their boundaries, and how degeneracies
73are handled) and numerical accuracy (e.g. minimizing cancellation error).
74
75Note that the intent of this library is to represent geometry as a mathematical
76abstraction. For example, although the unit sphere is obviously a useful
77approximation for the Earth's surface, functions that are specifically related
78to geography are not part of the core library (e.g. easting/northing
79conversions, ellipsoid approximations, geodetic vs. geocentric coordinates,
80etc).
81
82See http://godoc.org/github.com/golang/geo for specific package documentation.
83
84For an analogous library in C++, see https://github.com/google/s2geometry, in
85Java, see https://github.com/google/s2-geometry-library-java, and Python, see
86https://github.com/google/s2geometry/tree/master/src/python
87
88# Status of the Go Library
89
90This library is principally a port of the
91[C++ S2 library](https://github.com/google/s2geometry), adapting to Go idioms
92where it makes sense. We detail the progress of this port below relative to that
93C++ library.
94
95Legend:
96
97* ✅ - Feature Complete
98* 🟡 - Mostly Complete
99* ❌ - Not available
100
101## [ℝ¹](https://godoc.org/github.com/golang/geo/r1) - One-dimensional Cartesian coordinates
102
103C++ Type | Go
104:--------- | ---
105R1Interval | ✅
106
107## [ℝ²](https://godoc.org/github.com/golang/geo/r2) - Two-dimensional Cartesian coordinates
108
109C++ Type | Go
110:------- | ---
111R2Point | ✅
112R2Rect | ✅
113
114## [ℝ³](https://godoc.org/github.com/golang/geo/r3) - Three-dimensional Cartesian coordinates
115
116C++ Type | Go
117:------------ | ---
118R3Vector | ✅
119R3ExactVector | ✅
120Matrix3x3 | ✅
121
122## [S¹](https://godoc.org/github.com/golang/geo/s1) - Circular Geometry
123
124C++ Type | Go
125:----------- | ---
126S1Angle | ✅
127S1ChordAngle | ✅
128S1Interval | ✅
129
130## [S²](https://godoc.org/github.com/golang/geo/s2) - Spherical Geometry
131
132### Basic Types
133
134C++ Type | Go
135:------------------- | ---
136S2Cap | ✅
137S2Cell | ✅
138S2CellId | ✅
139S2CellIdVector | ❌
140S2CellIndex | 🟡
141S2CellUnion | ✅
142S2Coords | ✅
143S2DensityTree | ❌
144S2DistanceTarget | ✅
145S2EdgeVector | ✅
146S2LatLng | ✅
147S2LatLngRect | ✅
148S2LaxLoop | 🟡
149S2LaxPolygon | 🟡
150S2LaxPolyline | 🟡
151S2Loop | ✅
152S2PaddedCell | ✅
153S2Point | ✅
154S2PointIndex | ❌
155S2PointSpan | ❌
156S2PointRegion | ❌
157S2PointVector | ✅
158S2Polygon | 🟡
159S2Polyline | ✅
160S2R2Rect | ❌
161S2Region | ✅
162S2RegionCoverer | ✅
163S2RegionIntersection | ❌
164S2RegionUnion | ✅
165S2Shape | ✅
166S2ShapeIndex | ✅
167S2ShapeIndexRegion | ❌
168EncodedLaxPolygon | ❌
169EncodedLaxPolyline | ❌
170EncodedShapeIndex | ❌
171EncodedStringVector | ❌
172EncodedUintVector | ❌
173IdSetLexicon | ❌
174ValueSetLexicon | ❌
175SequenceLexicon | ❌
176LaxClosedPolyline | ❌
177VertexIDLaxLoop | ❌
178
179### Query Types
180
181C++ Type | Go
182:------------------- | ---
183S2ChainInterpolation | ❌
184S2ClosestCell | ❌
185S2FurthestCell | ❌
186S2ClosestEdge | ✅
187S2FurthestEdge | ✅
188S2ClosestPoint | ❌
189S2FurthestPoint | ❌
190S2ContainsPoint | ✅
191S2ContainsVertex | ✅
192S2ConvexHull | ✅
193S2CrossingEdge | ✅
194S2HausdorffDistance | ❌
195S2ShapeNesting | ❌
196
197### Supporting Types
198
199C++ Type | Go
200:------------------------------- | ---
201S2BooleanOperation | ❌
202S2BufferOperation | ❌
203S2Builder | ❌
204S2BuilderClosedSetNormalizer | ❌
205S2BuilderFindPolygonDegeneracies | ❌
206S2BuilderGraph | ❌
207S2BuilderLayers | ❌
208S2BuilderSnapFunctions | ❌
209S2BuilderTesting | ❌
210S2Builderutil\* | ❌
211S2Coder | ❌
212S2EdgeClipping | ✅
213S2EdgeCrosser | ✅
214S2EdgeCrossings | ✅
215S2EdgeDistances | ✅
216S2EdgeTessellator | ✅
217S2LoopMeasures | ❌
218S2Measures | ✅
219S2MemoryTracker | ❌
220S2Metrics | ❌
221S2PointUtil | 🟡
222S2PolygonBuilder | ❌
223S2PolylineAlignment | ❌
224S2PolylineMeasures | ✅
225S2PolylineSimplifier | ❌
226S2Predicates | ✅
227S2Projections | ❌
228S2rectBounder | ❌
229S2RegionTermIndexer | ❌
230S2ShapeIndexMeasures | ❌
231S2ShapeIndexUtil\* | 🟡
232S2ShapeMeasures | ❌
233S2ShapeUtil\* | 🟡
234S2Stats | ❌
235S2Testing | ✅
236S2TextFormat | ✅
237S2WedgeRelations | ✅
238S2WindingOperation | ❌
239
240### Encode/Decode
241
242Encoding and decoding of S2 types is fully implemented and interoperable with
243C++ and Java.
View as plain text