Socket
Socket
Sign inDemoInstall

github.com/golang/geo

Package Overview
Dependencies
0
Alerts
File Explorer

Install Socket

Detect and block malicious and high-risk dependencies

Install

    github.com/golang/geo


Version published

Readme

Source

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 SΒ².) 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.

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

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.

Legend:

  • βœ… - Feature Complete
  • 🟑 - Mostly Complete
  • ❌ - Not available

ℝ¹ - One-dimensional Cartesian coordinates

C++ TypeGo
R1Intervalβœ…

ℝ² - Two-dimensional Cartesian coordinates

C++ TypeGo
R2Pointβœ…
R2Rectβœ…

ℝ³ - Three-dimensional Cartesian coordinates

C++ TypeGo
R3Vectorβœ…
R3ExactVectorβœ…
Matrix3x3βœ…

SΒΉ - Circular Geometry

C++ TypeGo
S1Angleβœ…
S1ChordAngleβœ…
S1Intervalβœ…

SΒ² - Spherical Geometry

Basic Types

C++ TypeGo
S2Capβœ…
S2Cellβœ…
S2CellIdβœ…
S2CellIdVector❌
S2CellIndex🟑
S2CellUnionβœ…
S2Coordsβœ…
S2DensityTree❌
S2DistanceTargetβœ…
S2EdgeVectorβœ…
S2LatLngβœ…
S2LatLngRectβœ…
S2LaxLoop🟑
S2LaxPolygon🟑
S2LaxPolyline🟑
S2Loopβœ…
S2PaddedCellβœ…
S2Pointβœ…
S2PointIndex❌
S2PointSpan❌
S2PointRegion❌
S2PointVectorβœ…
S2Polygon🟑
S2Polylineβœ…
S2R2Rect❌
S2Regionβœ…
S2RegionCovererβœ…
S2RegionIntersection❌
S2RegionUnionβœ…
S2Shapeβœ…
S2ShapeIndexβœ…
S2ShapeIndexRegion❌
EncodedLaxPolygon❌
EncodedLaxPolyline❌
EncodedShapeIndex❌
EncodedStringVector❌
EncodedUintVector❌
IdSetLexicon❌
ValueSetLexicon❌
SequenceLexicon❌
LaxClosedPolyline❌
VertexIDLaxLoop❌

Query Types

C++ TypeGo
S2ChainInterpolation❌
S2ClosestCell❌
S2FurthestCell❌
S2ClosestEdgeβœ…
S2FurthestEdgeβœ…
S2ClosestPoint❌
S2FurthestPoint❌
S2ContainsPointβœ…
S2ContainsVertexβœ…
S2ConvexHullβœ…
S2CrossingEdgeβœ…
S2HausdorffDistance❌
S2ShapeNesting❌

Supporting Types

C++ TypeGo
S2BooleanOperation❌
S2BufferOperation❌
S2Builder❌
S2BuilderClosedSetNormalizer❌
S2BuilderFindPolygonDegeneracies❌
S2BuilderGraph❌
S2BuilderLayers❌
S2BuilderSnapFunctions❌
S2BuilderTesting❌
S2Builderutil*❌
S2Coder❌
S2EdgeClippingβœ…
S2EdgeCrosserβœ…
S2EdgeCrossingsβœ…
S2EdgeDistancesβœ…
S2EdgeTessellatorβœ…
S2LoopMeasures❌
S2Measuresβœ…
S2MemoryTracker❌
S2Metrics❌
S2PointUtil🟑
S2PolygonBuilder❌
S2PolylineAlignment❌
S2PolylineMeasuresβœ…
S2PolylineSimplifier❌
S2Predicatesβœ…
S2Projections❌
S2rectBounder❌
S2RegionTermIndexer❌
S2ShapeIndexMeasures❌
S2ShapeIndexUtil*🟑
S2ShapeMeasures❌
S2ShapeUtil*🟑
S2Stats❌
S2Testingβœ…
S2TextFormatβœ…
S2WedgeRelationsβœ…
S2WindingOperation❌

Encode/Decode

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

FAQs

Last updated on 21 Apr 2023

Did you know?

Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.

Install

Related posts

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap

Stay in touch

Get open source security insights delivered straight into your inbox.


  • Terms
  • Privacy
  • Security

Made with ⚑️ by Socket Inc