# S2 geometry library in Go

### Related tags

Images tools 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 2
• #### Fix floating point failures seen on ppc64le

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

opened by prashantkhoje 4
• #### 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
###### 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

220 Aug 1, 2022
###### Go package for fast high-level image processing powered by libvips C library

bimg Small Go package for fast high-level image processing using libvips via C bindings, providing a simple programmatic API. bimg was designed to be

2k Aug 2, 2022
###### Image processing library and rendering toolkit for Go.

blend Image processing library and rendering toolkit for Go. (WIP) Installation: This library is compatible with Go1. go get github.com/phrozen/blend

59 Dec 24, 2021
###### Go bindings to OpenGL Utility Library

GLU This package offers minimal bindings for GLU functions. Usage go get github.com/go-gl-legacy/glu License Copyright 2012 The go-gl Authors. All ri

21 Aug 18, 2018
###### Go binding for the cairo graphics library

go-cairo Go binding for the cairo graphics library Based on Dethe Elza's version https://bitbucket.org/dethe/gocairo but significantly extended and up

120 Jul 25, 2022
###### A library for playing with colors in go (golang).

go-colorful A library for playing with colors in Go. Supports Go 1.13 onwards. Why? I love games. I make games. I love detail and I get lost in detail

972 Jul 29, 2022
###### A lightning fast image processing and resizing library for Go

govips A lightning fast image processing and resizing library for Go This package wraps the core functionality of libvips image processing library by

731 Aug 8, 2022
12 Jun 4, 2019
###### A library to read, write, and transform Stereolithography (.stl) files in Go.

stl A library to read, write, and transform Stereolithography (.stl) files in Go. It is used in the command line STL manipulation tool stltool. Featur

62 Jun 19, 2022
###### Go Language Library for SVG generation

SVGo: A Go library for SVG generation The library generates SVG as defined by the Scalable Vector Graphics 1.1 Specification (http://www.w3.org/TR/SVG

1.9k Jul 28, 2022
###### Twilio Go library

twilio-go A client for accessing the Twilio API with several nice features: Easy-to-use helpers for purchasing phone numbers and sending MMS messages

135 May 5, 2022
###### :eyeglasses: Go library for [d]encoding glTF 2.0 files

gltf A Go module for efficient and robust serialization/deserialization of glTF 2.0, a royalty-free specification for the efficient transmission and l

168 Jul 31, 2022
###### Port of webcolors library from Python to Go

go-webcolors A library for working with color names and color value formats defined by the HTML and CSS specifications for use in documents on the Web

26 Jan 23, 2022
###### Avatar generation library for GO language

GOvatar GOvatar is an avatar generation library written in GO Install To install the library and command-line program, use the following: \$ go get -u

509 Jul 29, 2022
###### A Grid based 2D Graphics library

gridder Built on top of Go Graphics github.com/fogleman/gg with the idea to simplify visualizing Grids using 2D Graphics. Dependencies gg github.com/f

54 Jul 3, 2022
###### go library for image programming (merge, crop, resize, watermark, animate, ease, transit)

Result Terminal Code mergi -t TT -i https://raw.githubusercontent.com/ashleymcnamara/gophers/master/Facepalm_Gopher.png -r "131 131" -i https://raw.gi

178 Jul 29, 2022
###### Pure Golang Library that allows simple LSB steganography on images

Steganography Lib Steganography is a library written in Pure go to allow simple LSB steganography on images. It is capable of both encoding and decodi

150 Jul 26, 2022
###### Go cross-platform glfw library for creating an OpenGL context and receiving events.

glfw Package glfw experimentally provides a glfw-like API with desktop (via glfw) and browser (via HTML5 canvas) backends. It is used for creating a G

75 Jul 23, 2022
###### A pure Go 3D math library.

MathGL This is a Go matrix and vector math library specialized for Open GL graphics capabilities. This package is made primarily with code generation

445 Jul 29, 2022