# S2 geometry library in Go

### Related tags

GIS go geometry sphere geometry-library

# Overview

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 geometry libraries, S2 is primarily designed to work with spherical geometry, i.e., shapes drawn on a sphere rather than on a planar 2D map. (In fact, the name S2 is derived from the mathematical notation for the unit sphere .) This makes it especially suitable for working with geographic data.

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

## Scope

The library provides the following:

• Representations of angles, intervals, latitude-longitude points, unit vectors, 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 are collectively known as "regions".

• A hierarchical decomposition of the sphere into regions called "cells". The hierarchy starts with the six faces of a projected cube and recursively subdivides 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 and topology guarantees).

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

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

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

• Planar geometry.

• Conversions to/from common GIS formats.

### Robustness

What do we mean by "robust"?

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

Robustness is very important when building higher-level algorithms, since unexpected results from low-level operations can be very difficult to handle. S2 achieves this goal using a combination of techniques from computational geometry, including conservative error bounds, exact geometric predicates, and snap rounding.

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

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

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

# Status of the Go Library

This library is principally a port of the C++ S2 library, adapting to Go idioms where it makes sense. We detail the progress of this port below relative to that C++ library.

## ℝ¹ - One-dimensional Cartesian coordinates

Full parity with C++.

## ℝ² - Two-dimensional Cartesian coordinates

Full parity with C++.

## ℝ³ - Three-dimensional Cartesian coordinates

Full parity with C++.

## S¹ - Circular Geometry

Full parity with C++.

## S² - Spherical Geometry

Approximately ~40% complete.

Complete These files have full parity with the C++ implementation.

• Cap
• Cell
• CellID
• CellUnion
• ContainsVertexQuery
• ConvexHullQuery
• CrossingEdgeQuery
• LatLng
• matrix3x3
• Metric
• Point
• PointCompression
• Region
• RegionCoverer
• RegionUnion
• s2edge_clipping
• s2edge_crosser
• s2edge_crossings
• s2edge_distances
• edgeVectorShape
• laxLoop
• laxPolyline
• s2projections - Helpers for projecting points between R2 and S2.
• s2rect_bounder
• s2stuv.go (s2coords.h in C++) - This file is a collection of helper and conversion methods to and from ST-space, UV-space, and XYZ-space.
• s2wedge_relations
• ShapeIndex
• idSetLexicon,sequenceLexicon

Mostly Complete Files that have almost all of the features of the original C++ code, and are reasonably complete enough to use in live code. Up to date listing of the incomplete methods are documented at the end of each file.

• EdgeQuery/Closest/Furthest - missing Project, GetEdge
• ContainsPointQuery - missing visit edges
• laxPolygon
• Loop - Loop is mostly complete now. Missing Project, Distance, Union, etc.
• Polyline - Missing InitTo... methods, NearlyCoversPolyline
• Rect (AKA s2latlngrect in C++) - Missing Centroid, InteriorContains.
• s2_test.go (AKA s2testing and s2textformat in C++) - Missing Fractal test shape generation. This file is a collection of testing helper methods.
• s2edge_distances - Missing Intersection

In Progress Files that have some work done, but are probably not complete enough for general use in production code.

• CellIndex - A queryable index of CellIDs.
• Polygon - Polygons with multiple loops are supported. It fully implements Shape and Region, but it's missing most other methods. (Area, Centroid, Distance, Projection, Intersection, Union, Contains, Normalized, etc.)
• PolylineSimplifier - Initial work has begun on this.
• s2predicates.go - This file is a collection of helper methods used by other parts of the library.
• s2shapeutil - Initial elements added. Missing VisitCrossings.

Not Started Yet. These files (and their associated unit tests) have dependencies on most of the In Progress files before they can begin to be started.

• BooleanOperation - used when assembling polygons and loops.
• Builder - This is a robust tool for creating the various Shape types from collection of simpler S2 types.
• BuilderClosedSetNormalizer
• BuilderFindPolygonDegneracies
• BuilderGraph
• BuilderLayers
• BuilderSnapFunctions
• BuilderTesting
• Centroids
• ClosestPointQuery
• EdgeTesselator
• LoopMeasures
• PointIndex
• PointRegion
• PointUtil
• PolygonMeasures
• RegionIntersection
• RegionTermIndexer
• ShapeIndexRegion - Allows ShapeIndexes to be used as Regions for things like

### Encode/Decode

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

• #### s2: Loop implements Region interface

Also added a LoopFromDegrees function to make building loops easier. I did not do explicit tests in this repo, but the tests here https://github.com/buckhx/gofence/blob/master/geofence/fence_test.go passed.

opened by buckhx 15
• #### make s2.Loop Regions & serializable + Fix loop.IntersectsCell

Hello there,

I really need a way to serialize a big bunch of s2.Loops and also @buckhx made them Region compliant. ( which I needed too )

I'm pushing this here as some people might need that too. Just tell me if something is wrong I'll change it :).

Thoughts: it's much more convenient if everything is public in a struct that is returned by a package. Specially for serialization cases. If you are afraid someone will tweak too much variables and they should not, well they just better know what they are doing :).

o/

opened by azr 12
• #### Loop.Intersects gives incorrect results

I have two geojson objects Polygon 1: [[[-74.93335056304832,39.283340980346445], [-74.93335056305031,40.30000217770297], [-75.91667795181374,40.30000217770097], [-75.91667795181175,40.28334098034444], [-74.93335056304832,39.283340980346445]]] Polygon 2: [[[-74.3122237229173, 39.9541747627284], [-74.1955570274039, 40.0833414585103], [-74.5497238128233, 40.1958414684098], [-74.7163905245327, 40.0583414352459], [-74.8663905578957, 39.8208413826612], [-74.4163904122584,39.7708413884741], [-74.3122237229173, 39.9541747627284]]]

I converted [][][]float64 array to Loop using Function: `func convertFloatListToPolygon(floatList [][][]float64) *s2.Loop {` `points := floatList[0]` `pointList := make([]s2.Point, 0)` `for _, point := range points {` `s2Point := s2.PointFromLatLng(` `s2.LatLng{` `Lat:s1.Angle(point[1]),` Lng:s1.Angle(point[0]), }) pointList = append(pointList, s2Point) } return s2.LoopFromPoints(pointList)}`

`poly = convertFloatListToPolygon(p1)` `comparedPoly = convertFloatListToPolygon(p2)` `poly.Intersects(comparedPoly)`

The results is true. However, when I draw those two polygon in geojson.io, it's not intersected.

Could someone tell me if I use function wrong or there is a bug in intersection?

opened by outsidebedisdoor 8
• #### Q: How do you calculate the distance in km between 2 lat/lng points?

``````package main

import (
"fmt"

"github.com/golang/geo/s1"
"github.com/golang/geo/s2"
)

func main() {
lat1 := 9.1829321
lng1 := 48.7758459
lat2 := 5.03131
lng2 := 39.542448

pg1 := s2.PointFromLatLng(s2.LatLng{
Lat: s1.Angle(lat1),
Lng: s1.Angle(lng1),
})
pg2 := s2.PointFromLatLng(s2.LatLng{
Lat: s1.Angle(lat2),
Lng: s1.Angle(lng2),
})
sdist := pg1.Distance(pg2)
fmt.Printf("s2 distance: %f\n", sdist)

}
``````

s2 distance: 1.499294

This can't be true. It's nearly 1080km.

Can you please tell how to do it?

opened by idc77 7
• #### S2: Regioncoverer slightly intersecting another face doesn't cover whole region

I created a regioncoverer from a rectangle as following:

``````var regionCoverer s2.RegionCoverer

regionCoverer.MaxCells = 10000
regionCoverer.MinLevel = 7
regionCoverer.MaxLevel = 7

topleft := s2.LatLngFromDegrees(72.0000064, -141.0000000)
topright := s2.LatLngFromDegrees(72.0000064, -55.6152420)
bottomleft := s2.LatLngFromDegrees(41.9017143, -141.0000000)
bottomright := s2.LatLngFromDegrees(41.9017143, -55.6152420)

rect = s2.Rect{}

covering := regionCoverer.Covering(s2.Region(rect))
``````

The result is not 100% what I was expecting. A cellUnion of CellID's covering the whole rectangle should be the result but the small part of the rectangle that lies on a different face does not get any cellID's returned for it. I visualized all cell's in QGIS so that you can see what I mean:

The part where it looks like somebody took a bite out of it lies on a different face (face 4 vs. face 2).

Slightly lowering the bottomleft and bottomright latitude solves the problem.

opened by zeevogels 7
• #### Question: Overflow converting `CellID.Pos()` to float64 is possible?

Hi

I have to convert the latlongs of a polyline into list of `s2CellId Pos`(uint64) and store the POS() value in redis as sorted set(which needs value as float64) Now I am a bit afraid of overflow while converting POS from `uint64` to `float64` because below code overflows -

``````	numUint64 := math.MaxUint64
numFloat64 := float64(numUint64)
``````

However, the documentation of `CellID.Pos()` confirms the range as `[0,2^posBits-1]`. If we calculate, `posBits = 2<<maxLevel + 1`, given `maxLevel = 30` below code works fine without overflow.

``````        posBits := (2<<30+1) - 1
floatEq := float64(posBits)
``````

### Now, is it safe to say `CellID.Pos()` conversion to `float64` will never overflow?

opened by amarjeetanandsingh 6
• #### s2: Implement Project and IsOnRight on Polyline.

The implementation and tests are a direct translation from C++, only Project() uses ChordAngle rather than Angle, in line with newer code working with distances.

opened by andreweland 6
• #### WIP: Implement ConvexHullQuery

This is a port of the C++ ConvexHullQuery code.

Also adds detection for reversed versions of a loop in `Loop.BoundaryEqual()` (noticed when porting `TestConvexHullQuerySimplePolyline`)

There are some bugs and the tests aren't working but I figure'd I'd do the PR anyway to get some feedback right away.

opened by markus-wa 6
• #### Support for Polygon Contains and Intersects method

I wanted to check if its possible to add support for Contains/Intersects for Polygon. Since the library doesn't yet support those methods for Polygon/MultiPolygon we just use the outer `s2.Loop` and do Intersects/Contains using that. That is error prone because it ignores the holes in the polygon.

If it's not very complicated then I could try porting them over from the C++ library and send over a PR?

opened by pawanrawal 6
• #### Inconsistent result using RegionCoverer over Loop

I've come up with some results using the CellUnion method of RegionCoverer which are unexpected to me. I've created this gist to reproduce what I'm observing.

I'm basically comparing the cells covered by a Polyline containing 3 points and a Loop which is defined using the same 3 points. Using a RegionCoverer, it identifies 3 cells for the Polyline but returns an empty list of cells in the case of the Loop.

I've done some digging and although the FastCovering call identifies the same initial candidates in both cases, Loop's IntersectsCell method results in a "Disjoint" CellRelation for each of the 4 identified candidates.

I would have expected similar cells returning for both geometries or at least a non empty slice in the case of the Loop.

opened by prl900 6
• #### Coverer.CellUnion(Point) can have multiple cells?

In S2, in some cases, a `Coverer.CellUnion()` of a `Point` can contain two cells. Is that the correct behavior? If so, what's the story?

Example:

``````package main

import (
"fmt"

"github.com/golang/geo/s2"
)

func main() {
var (
level   = 7
coverer = s2.RegionCoverer{
MinLevel: level,
MaxLevel: level,
}
ll    = s2.LatLng{Lat: -0.8248776721189366, Lng: -2.038611228784389}
p     = s2.PointFromLatLng(ll)
union = coverer.CellUnion(p)
)
fmt.Println(len(union))
}

``````

At the playground.

opened by jsmorph 4
• #### ppc64le - Fix deviation in floating point values caused by FMA

This was exposed while testing CockroachDB. Following tests from pkg/sql/opt/exec/execbuilder fail due to floating point precision differences caused by FMA:

• TestExecBuild/local/geospatial
• TestExecBuild/local-vec-off/geospatial
• TestExecBuild/local-spec-planning/geospatial
• TestExecBuild/fakedist/geospatial
• TestExecBuild/fakedist-vec-off/geospatial
• TestExecBuild/fakedist-disk/geospatial
• TestExecBuild/fakedist-spec-planning/geospatial

With explicit casts in this patch, these failures are resolved.

opened by prashantkhoje 4
• #### Fix floating point failures seen on ppc64le

Fixes test failures: - TestClosestEdgeQueryTrueDistanceLessThanChordAngleDistance (#88) - TestPointMeasuresPointArea (#87) - TestPredicatesRobustSignEqualities (#86)

opened by prashantkhoje 5
• #### ppc64le - TestClosestEdgeQueryTrueDistanceLessThanChordAngleDistance failure due to floating point precision differences

I ran tests on ppc64le using "go test -v ./..." command.

The TestClosestEdgeQueryTrueDistanceLessThanChordAngleDistance fails due to floating point precision differences:

``````=== RUN   TestClosestEdgeQueryTrueDistanceLessThanChordAngleDistance
edge_query_closest_test.go:122: CompareDistance((0.785167625848291916845767, -0.502004006908459698976799, -0.362634494177826782745910), (0.785630117324294330316548, -0.501876559404935029817807, -0.361808288839380542967206), 9.127564928066267e-07) = 1, want >= 0
--- FAIL: TestClosestEdgeQueryTrueDistanceLessThanChordAngleDistance (0.00s)
``````
``````[[email protected] geo]# go env
GO111MODULE=""
GOARCH="ppc64le"
GOBIN=""
GOCACHE="/root/.cache/go-build"
GOENV="/root/.config/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="ppc64le"
GOHOSTOS="linux"
GOINSECURE=""
GOMODCACHE="/root/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/root/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/usr/lib/golang"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/usr/lib/golang/pkg/tool/linux_ppc64le"
GOVCS=""
GOVERSION="go1.17.7"
GCCGO="gccgo"
GOPPC64="power8"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/root/go/src/github.com/geo/geo/go.mod"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
``````
``````[[email protected] geo]# git branch
* master
``````
opened by prashantkhoje 0
• #### ppc64le - TestPointMeasuresPointArea failure due to floating point precision differences

I ran tests on ppc64le using "go test -v ./..." command.

The TestPointMeasuresPointArea fails due to floating point precision differences:

``````=== RUN   TestPointMeasuresPointArea
point_measures_test.go:65: PointArea((0.257000000000000006217249, -0.572300000000000030908609, 0.112000000000000002331468), (0.257000000000000006217249, -0.572300000000000030908609, 0.112000000000000002331468), (0.257000000000000006217249, -0.572300000000000030908609, 0.112000000000000002331468)), got 1.9819499942010192e-34 want 0
--- FAIL: TestPointMeasuresPointArea (0.02s)
``````
``````[[email protected] geo]# go env
GO111MODULE=""
GOARCH="ppc64le"
GOBIN=""
GOCACHE="/root/.cache/go-build"
GOENV="/root/.config/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="ppc64le"
GOHOSTOS="linux"
GOINSECURE=""
GOMODCACHE="/root/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/root/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/usr/lib/golang"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/usr/lib/golang/pkg/tool/linux_ppc64le"
GOVCS=""
GOVERSION="go1.17.7"
GCCGO="gccgo"
GOPPC64="power8"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/root/go/src/github.com/geo/geo/go.mod"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
``````
``````[[email protected] geo]# git branch
* master
``````
opened by prashantkhoje 0
• #### ppc64le - TestPredicatesRobustSignEqualities failure due to floating point precision differences

I ran tests on ppc64le using "go test -v ./..." command.

The TestPredicatesRobustSignEqualities fails due to floating point precision differences:

``````=== RUN   TestPredicatesRobustSignEqualities
predicates_test.go:130: Testing equality for RobustSign. (0.577350269189625731058868, 0.577350269189625731058868, 0.577350269189625731058868) = (0.577350269189625842081171, 0.577350269189625842081171, 0.577350269189625842081171), got false want true
--- FAIL: TestPredicatesRobustSignEqualities (0.00s)
``````
``````[[email protected] geo]# go env
GO111MODULE=""
GOARCH="ppc64le"
GOBIN=""
GOCACHE="/root/.cache/go-build"
GOENV="/root/.config/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="ppc64le"
GOHOSTOS="linux"
GOINSECURE=""
GOMODCACHE="/root/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/root/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/usr/lib/golang"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/usr/lib/golang/pkg/tool/linux_ppc64le"
GOVCS=""
GOVERSION="go1.17.7"
GCCGO="gccgo"
GOPPC64="power8"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/root/go/src/github.com/geo/geo/go.mod"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
``````
``````[[email protected] geo]# git branch
* master
``````
opened by prashantkhoje 0
###### Go
The Go Programming Language
###### Efficient 2D geometry library for Go.

geometry An efficient 2D geometry library for Go. Features Point, Rect, Line, and Polygon geometry types Operations such as Intersects, Contains, and

30 Aug 30, 2022
###### Package geom implements efficient geometry types for geospatial applications.

go-geom Package geom implements efficient geometry types for geospatial applications. Key features OpenGeo Consortium-style geometries. Support for 2D

641 Nov 29, 2022
###### Types and utilities for working with 2d geometry in Golang

orb Package orb defines a set of types for working with 2d geo and planar/projected geometric data in Golang. There are a set of sub-packages that use

604 Dec 4, 2022
###### Go bindings for the Cartographic Projections Library PROJ.4

The Go package proj provides a limited interface to the Cartographic Projections Library PROJ. For PROJ version 5 and beyond, see also: https://github

42 Nov 10, 2022
###### General purpose library for reading, writing and working with OpenStreetMap data

osm This package is a general purpose library for reading, writing and working with OpenStreetMap data in Go (golang). It has the ability to read OSM

241 Nov 25, 2022

232 Nov 12, 2022
###### geoserver is a Go library for manipulating a GeoServer instance via the GeoServer REST API.

Geoserver geoserver Is a Go Package For Manipulating a GeoServer Instance via the GeoServer REST API. How to install: go get -v gopkg.in/hishamkaram/g

76 Sep 26, 2022
###### A library provides spatial data and geometric algorithms

Geoos Our organization spatial-go is officially established! The first open source project Geoos(Using Golang) provides spatial data and geometric alg

548 Nov 25, 2022
###### S2 geometry library in Go

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

1.5k Dec 1, 2022
###### S2 geometry library in Go

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

1.5k Nov 23, 2022
###### Efficient 2D geometry library for Go.

geometry An efficient 2D geometry library for Go. Features Point, Rect, Line, and Polygon geometry types Operations such as Intersects, Contains, and

30 Aug 30, 2022
###### Package geom implements efficient geometry types for geospatial applications.

go-geom Package geom implements efficient geometry types for geospatial applications. Key features OpenGeo Consortium-style geometries. Support for 2D

641 Nov 29, 2022
###### Types and utilities for working with 2d geometry in Golang

orb Package orb defines a set of types for working with 2d geo and planar/projected geometric data in Golang. There are a set of sub-packages that use

604 Dec 4, 2022
###### Types and utilities for working with 2d geometry in Golang

orb Package orb defines a set of types for working with 2d geo and planar/projected geometric data in Golang. There are a set of sub-packages that use

604 Dec 7, 2022
###### Transitland routes geometry generator from gtfs shapes

Transitland route geometry generator Generate your transitland route shapes from gtfs trips - WIP This project aims to generate transitland gtfs route

3 Dec 8, 2021
###### golang feature toggle library - a library to help make golang feature toggling clean and easy

toggle supports env_variable backed toggling. It can also be updated via a pubsub interface (tested w/ redis) 2 engines for toggle backing are include

24 Mar 29, 2022
###### sqlx is a library which provides a set of extensions on go's standard database/sql library

sqlx is a library which provides a set of extensions on go's standard database/sql library. The sqlx versions of sql.DB, sql.TX, sql.Stmt, et al. all leave the underlying interfaces untouched, so that their interfaces are a superset on the standard ones. This makes it relatively painless to integrate existing codebases using database/sql with sqlx.

12.9k Dec 6, 2022
###### This library generate a new tlsconfig usable within go standard library configured with a self-signed certificate generated on the fly

sslcert This library generate a new tlsconfig usable within go standard library configured with a self-signed certificate generated on the fly. Exampl

8 Nov 21, 2022