Documentation ¶
Overview ¶
Package s2 is a library for working with geometry in S² (spherical geometry).
Its related packages, parallel to this one, are s1 (operates on S¹), r1 (operates on ℝ¹), r2 (operates on ℝ²) and r3 (operates on ℝ³).
This package provides types and functions for the S2 cell hierarchy and coordinate systems. The S2 cell hierarchy is a hierarchical decomposition of the surface of a unit sphere (S²) into “cells”; it is highly efficient, scales from continental size to under 1 cm² and preserves spatial locality (nearby cells have close IDs).
More information including an indepth introduction to S2 can be found on the S2 website https://s2geometry.io/
Index ¶
 Constants
 Variables
 func Angle(a, b, c Point) s1.Angle
 func AngleContainsVertex(a, b, c Point) bool
 func ChordAngleBetweenPoints(x, y Point) s1.ChordAngle
 func ClipEdge(a, b r2.Point, clip r2.Rect) (aClip, bClip r2.Point, intersects bool)
 func ClipToFace(a, b Point, face int) (aUV, bUV r2.Point, intersects bool)
 func ClipToPaddedFace(a, b Point, f int, padding float64) (aUV, bUV r2.Point, intersects bool)
 func CompareDistance(x, y Point, r s1.ChordAngle) int
 func CompareDistances(x, a, b Point) int
 func DistanceFraction(x, a, b Point) float64
 func DistanceFromSegment(x, a, b Point) s1.Angle
 func EdgeOrVertexCrossing(a, b, c, d Point) bool
 func EdgePairClosestPoints(a0, a1, b0, b1 Point) (Point, Point)
 func GirardArea(a, b, c Point) float64
 func IsDistanceLess(x, a, b Point, limit s1.ChordAngle) bool
 func IsInteriorDistanceLess(x, a, b Point, limit s1.ChordAngle) bool
 func OrderedCCW(a, b, c, o Point) bool
 func PointArea(a, b, c Point) float64
 func Sign(a, b, c Point) bool
 func SignedArea(a, b, c Point) float64
 func TurnAngle(a, b, c Point) s1.Angle
 func UpdateMaxDistance(x, a, b Point, maxDist s1.ChordAngle) (s1.ChordAngle, bool)
 func UpdateMinDistance(x, a, b Point, minDist s1.ChordAngle) (s1.ChordAngle, bool)
 func UpdateMinInteriorDistance(x, a, b Point, minDist s1.ChordAngle) (s1.ChordAngle, bool)
 func VertexCrossing(a, b, c, d Point) bool
 func WedgeContains(a0, ab1, a2, b0, b2 Point) bool
 func WedgeIntersects(a0, ab1, a2, b0, b2 Point) bool
 type Cap
 func CapFromCenterAngle(center Point, angle s1.Angle) Cap
 func CapFromCenterArea(center Point, area float64) Cap
 func CapFromCenterChordAngle(center Point, radius s1.ChordAngle) Cap
 func CapFromCenterHeight(center Point, height float64) Cap
 func CapFromPoint(p Point) Cap
 func EmptyCap() Cap
 func FullCap() Cap
 func (c Cap) AddCap(other Cap) Cap
 func (c Cap) AddPoint(p Point) Cap
 func (c Cap) ApproxEqual(other Cap) bool
 func (c Cap) Area() float64
 func (c Cap) CapBound() Cap
 func (c Cap) CellUnionBound() []CellID
 func (c Cap) Center() Point
 func (c Cap) Centroid() Point
 func (c Cap) Complement() Cap
 func (c Cap) Contains(other Cap) bool
 func (c Cap) ContainsCell(cell Cell) bool
 func (c Cap) ContainsPoint(p Point) bool
 func (c *Cap) Decode(r io.Reader) error
 func (c Cap) Encode(w io.Writer) error
 func (c Cap) Equal(other Cap) bool
 func (c Cap) Expanded(distance s1.Angle) Cap
 func (c Cap) Height() float64
 func (c Cap) InteriorContainsPoint(p Point) bool
 func (c Cap) InteriorIntersects(other Cap) bool
 func (c Cap) Intersects(other Cap) bool
 func (c Cap) IntersectsCell(cell Cell) bool
 func (c Cap) IsEmpty() bool
 func (c Cap) IsFull() bool
 func (c Cap) IsValid() bool
 func (c Cap) Radius() s1.Angle
 func (c Cap) RectBound() Rect
 func (c Cap) String() string
 func (c Cap) Union(other Cap) Cap
 type Cell
 func (c Cell) ApproxArea() float64
 func (c Cell) AverageArea() float64
 func (c Cell) BoundUV() r2.Rect
 func (c Cell) BoundaryDistance(target Point) s1.ChordAngle
 func (c Cell) CapBound() Cap
 func (c Cell) CellUnionBound() []CellID
 func (c Cell) Center() Point
 func (c Cell) Children() ([4]Cell, bool)
 func (c Cell) ContainsCell(oc Cell) bool
 func (c Cell) ContainsPoint(p Point) bool
 func (c *Cell) Decode(r io.Reader) error
 func (c Cell) Distance(target Point) s1.ChordAngle
 func (c Cell) DistanceToCell(target Cell) s1.ChordAngle
 func (c Cell) DistanceToEdge(a, b Point) s1.ChordAngle
 func (c Cell) Edge(k int) Point
 func (c Cell) Encode(w io.Writer) error
 func (c Cell) ExactArea() float64
 func (c Cell) Face() int
 func (c Cell) ID() CellID
 func (c Cell) IntersectsCell(oc Cell) bool
 func (c Cell) IsLeaf() bool
 func (c Cell) Level() int
 func (c Cell) MaxDistance(target Point) s1.ChordAngle
 func (c Cell) MaxDistanceToCell(target Cell) s1.ChordAngle
 func (c Cell) MaxDistanceToEdge(a, b Point) s1.ChordAngle
 func (c Cell) RectBound() Rect
 func (c Cell) SizeIJ() int
 func (c Cell) SizeST() float64
 func (c Cell) Vertex(k int) Point
 type CellID
 func CellIDFromFace(face int) CellID
 func CellIDFromFacePosLevel(face int, pos uint64, level int) CellID
 func CellIDFromLatLng(ll LatLng) CellID
 func CellIDFromString(s string) CellID
 func CellIDFromToken(s string) CellID
 func FloodFillRegionCovering(region Region, start CellID) []CellID
 func SimpleRegionCovering(region Region, start Point, level int) []CellID
 func (ci CellID) Advance(steps int64) CellID
 func (ci CellID) AdvanceWrap(steps int64) CellID
 func (ci CellID) AllNeighbors(level int) []CellID
 func (ci CellID) ChildBegin() CellID
 func (ci CellID) ChildBeginAtLevel(level int) CellID
 func (ci CellID) ChildEnd() CellID
 func (ci CellID) ChildEndAtLevel(level int) CellID
 func (ci CellID) ChildPosition(level int) int
 func (ci CellID) Children() [4]CellID
 func (ci CellID) CommonAncestorLevel(other CellID) (level int, ok bool)
 func (ci CellID) Contains(oci CellID) bool
 func (ci *CellID) Decode(r io.Reader) error
 func (ci CellID) EdgeNeighbors() [4]CellID
 func (ci CellID) Encode(w io.Writer) error
 func (ci CellID) Face() int
 func (ci CellID) Intersects(oci CellID) bool
 func (ci CellID) IsLeaf() bool
 func (ci CellID) IsValid() bool
 func (ci CellID) LatLng() LatLng
 func (ci CellID) Level() int
 func (ci CellID) MaxTile(limit CellID) CellID
 func (ci CellID) Next() CellID
 func (ci CellID) NextWrap() CellID
 func (ci CellID) Parent(level int) CellID
 func (ci CellID) Point() Point
 func (ci CellID) Pos() uint64
 func (ci CellID) Prev() CellID
 func (ci CellID) PrevWrap() CellID
 func (ci CellID) RangeMax() CellID
 func (ci CellID) RangeMin() CellID
 func (ci CellID) String() string
 func (ci CellID) ToToken() string
 func (ci CellID) VertexNeighbors(level int) []CellID
 type CellIDSnapper
 type CellIndex
 type CellIndexContentsIterator
 func (c *CellIndexContentsIterator) CellID() CellID
 func (c *CellIndexContentsIterator) Clear()
 func (c *CellIndexContentsIterator) Done() bool
 func (c *CellIndexContentsIterator) Label() int32
 func (c *CellIndexContentsIterator) Next()
 func (c *CellIndexContentsIterator) StartUnion(r *CellIndexRangeIterator)
 type CellIndexIterator
 type CellIndexRangeIterator
 func (c *CellIndexRangeIterator) Advance(n int) bool
 func (c *CellIndexRangeIterator) Begin()
 func (c *CellIndexRangeIterator) Done() bool
 func (c *CellIndexRangeIterator) Finish()
 func (c *CellIndexRangeIterator) IsEmpty() bool
 func (c *CellIndexRangeIterator) LimitID() CellID
 func (c *CellIndexRangeIterator) Next()
 func (c *CellIndexRangeIterator) Prev() bool
 func (c *CellIndexRangeIterator) Seek(target CellID)
 func (c *CellIndexRangeIterator) StartID() CellID
 type CellRelation
 type CellUnion
 func (cu *CellUnion) ApproxArea() float64
 func (cu *CellUnion) AverageArea() float64
 func (cu *CellUnion) CapBound() Cap
 func (cu *CellUnion) CellUnionBound() []CellID
 func (cu *CellUnion) Contains(o CellUnion) bool
 func (cu *CellUnion) ContainsCell(c Cell) bool
 func (cu *CellUnion) ContainsCellID(id CellID) bool
 func (cu *CellUnion) ContainsPoint(p Point) bool
 func (cu *CellUnion) Decode(r io.Reader) error
 func (cu *CellUnion) Denormalize(minLevel, levelMod int)
 func (cu *CellUnion) Encode(w io.Writer) error
 func (cu CellUnion) Equal(o CellUnion) bool
 func (cu *CellUnion) ExactArea() float64
 func (cu *CellUnion) ExpandAtLevel(level int)
 func (cu *CellUnion) ExpandByRadius(minRadius s1.Angle, maxLevelDiff int)
 func (cu *CellUnion) Intersects(o CellUnion) bool
 func (cu *CellUnion) IntersectsCell(c Cell) bool
 func (cu *CellUnion) IntersectsCellID(id CellID) bool
 func (cu *CellUnion) IsNormalized() bool
 func (cu *CellUnion) IsValid() bool
 func (cu *CellUnion) LeafCellsCovered() int64
 func (cu *CellUnion) Normalize()
 func (cu *CellUnion) RectBound() Rect
 type Chain
 type ChainPosition
 type ContainsPointQuery
 type ContainsVertexQuery
 type ConvexHullQuery
 type Crossing
 type CrossingEdgeQuery
 type CrossingType
 type Direction
 type Edge
 type EdgeCrosser
 type EdgeIterator
 type EdgeMap
 type EdgeQuery
 func (e *EdgeQuery) Distance(target distanceTarget) s1.ChordAngle
 func (e *EdgeQuery) FindEdges(target distanceTarget) []EdgeQueryResult
 func (e *EdgeQuery) IsConservativeDistanceGreaterOrEqual(target distanceTarget, limit s1.ChordAngle) bool
 func (e *EdgeQuery) IsConservativeDistanceLessOrEqual(target distanceTarget, limit s1.ChordAngle) bool
 func (e *EdgeQuery) IsDistanceGreater(target distanceTarget, limit s1.ChordAngle) bool
 func (e *EdgeQuery) IsDistanceLess(target distanceTarget, limit s1.ChordAngle) bool
 func (e *EdgeQuery) Reset()
 type EdgeQueryOptions
 func (e *EdgeQueryOptions) DistanceLimit(limit s1.ChordAngle) *EdgeQueryOptions
 func (e *EdgeQueryOptions) IncludeInteriors(x bool) *EdgeQueryOptions
 func (e *EdgeQueryOptions) MaxError(dist s1.ChordAngle) *EdgeQueryOptions
 func (e *EdgeQueryOptions) MaxResults(n int) *EdgeQueryOptions
 func (e *EdgeQueryOptions) UseBruteForce(x bool) *EdgeQueryOptions
 type EdgeQueryResult
 type EdgeTessellator
 type FaceSegment
 type IdentitySnapper
 type IntLatLngSnapper
 type LatLng
 type LaxLoop
 func (l *LaxLoop) Chain(i int) Chain
 func (l *LaxLoop) ChainEdge(i, j int) Edge
 func (l *LaxLoop) ChainPosition(e int) ChainPosition
 func (l *LaxLoop) Dimension() int
 func (l *LaxLoop) Edge(e int) Edge
 func (l *LaxLoop) IsEmpty() bool
 func (l *LaxLoop) IsFull() bool
 func (l *LaxLoop) NumChains() int
 func (l *LaxLoop) NumEdges() int
 func (l *LaxLoop) ReferencePoint() ReferencePoint
 type LaxPolygon
 func (p *LaxPolygon) Chain(i int) Chain
 func (p *LaxPolygon) ChainEdge(i, j int) Edge
 func (p *LaxPolygon) ChainPosition(e int) ChainPosition
 func (p *LaxPolygon) Dimension() int
 func (p *LaxPolygon) Edge(e int) Edge
 func (p *LaxPolygon) IsEmpty() bool
 func (p *LaxPolygon) IsFull() bool
 func (p *LaxPolygon) NumChains() int
 func (p *LaxPolygon) NumEdges() int
 func (p *LaxPolygon) ReferencePoint() ReferencePoint
 type LaxPolyline
 func (l *LaxPolyline) Chain(i int) Chain
 func (l *LaxPolyline) ChainEdge(i, j int) Edge
 func (l *LaxPolyline) ChainPosition(e int) ChainPosition
 func (l *LaxPolyline) Dimension() int
 func (l *LaxPolyline) Edge(e int) Edge
 func (l *LaxPolyline) IsEmpty() bool
 func (l *LaxPolyline) IsFull() bool
 func (l *LaxPolyline) NumChains() int
 func (l *LaxPolyline) NumEdges() int
 func (l *LaxPolyline) ReferencePoint() ReferencePoint
 type Loop
 func (l *Loop) Area() float64
 func (l *Loop) BoundaryEqual(o *Loop) bool
 func (l *Loop) CanonicalFirstVertex() (firstIdx, direction int)
 func (l *Loop) CapBound() Cap
 func (l *Loop) CellUnionBound() []CellID
 func (l *Loop) Centroid() Point
 func (l *Loop) Chain(chainID int) Chain
 func (l *Loop) ChainEdge(chainID, offset int) Edge
 func (l *Loop) ChainPosition(edgeID int) ChainPosition
 func (l *Loop) Contains(o *Loop) bool
 func (l *Loop) ContainsCell(target Cell) bool
 func (l *Loop) ContainsNested(other *Loop) bool
 func (l *Loop) ContainsOrigin() bool
 func (l *Loop) ContainsPoint(p Point) bool
 func (l *Loop) Decode(r io.Reader) error
 func (l *Loop) Dimension() int
 func (l *Loop) Edge(i int) Edge
 func (l Loop) Encode(w io.Writer) error
 func (l *Loop) Equal(other *Loop) bool
 func (l *Loop) Intersects(o *Loop) bool
 func (l *Loop) IntersectsCell(target Cell) bool
 func (l *Loop) Invert()
 func (l *Loop) IsEmpty() bool
 func (l *Loop) IsFull() bool
 func (l *Loop) IsHole() bool
 func (l *Loop) IsNormalized() bool
 func (l *Loop) Normalize()
 func (l *Loop) NumChains() int
 func (l *Loop) NumEdges() int
 func (l *Loop) NumVertices() int
 func (l *Loop) OrientedVertex(i int) Point
 func (l *Loop) RectBound() Rect
 func (l *Loop) ReferencePoint() ReferencePoint
 func (l *Loop) Sign() int
 func (l *Loop) TurningAngle() float64
 func (l *Loop) Validate() error
 func (l *Loop) Vertex(i int) Point
 func (l *Loop) Vertices() []Point
 type MaxDistanceToCellTarget
 type MaxDistanceToEdgeTarget
 type MaxDistanceToPointTarget
 type MaxDistanceToShapeIndexTarget
 type MercatorProjection
 func (p *MercatorProjection) FromLatLng(ll LatLng) r2.Point
 func (p *MercatorProjection) Interpolate(f float64, a, b r2.Point) r2.Point
 func (p *MercatorProjection) Project(pt Point) r2.Point
 func (p *MercatorProjection) ToLatLng(pt r2.Point) LatLng
 func (p *MercatorProjection) Unproject(pt r2.Point) Point
 func (p *MercatorProjection) WrapDestination(a, b r2.Point) r2.Point
 func (p *MercatorProjection) WrapDistance() r2.Point
 type Metric
 type MinDistanceToCellTarget
 type MinDistanceToEdgeTarget
 type MinDistanceToPointTarget
 type MinDistanceToShapeIndexTarget
 type PaddedCell
 func (p PaddedCell) Bound() r2.Rect
 func (p PaddedCell) CellID() CellID
 func (p PaddedCell) Center() Point
 func (p PaddedCell) ChildIJ(pos int) (i, j int)
 func (p PaddedCell) EntryVertex() Point
 func (p PaddedCell) ExitVertex() Point
 func (p PaddedCell) Level() int
 func (p *PaddedCell) Middle() r2.Rect
 func (p PaddedCell) Padding() float64
 func (p *PaddedCell) ShrinkToFit(rect r2.Rect) CellID
 type PlateCarreeProjection
 func (p *PlateCarreeProjection) FromLatLng(ll LatLng) r2.Point
 func (p *PlateCarreeProjection) Interpolate(f float64, a, b r2.Point) r2.Point
 func (p *PlateCarreeProjection) Project(pt Point) r2.Point
 func (p *PlateCarreeProjection) ToLatLng(pt r2.Point) LatLng
 func (p *PlateCarreeProjection) Unproject(pt r2.Point) Point
 func (p *PlateCarreeProjection) WrapDestination(a, b r2.Point) r2.Point
 func (p *PlateCarreeProjection) WrapDistance() r2.Point
 type Point
 func EdgeTrueCentroid(a, b Point) Point
 func Interpolate(t float64, a, b Point) Point
 func InterpolateAtDistance(ax s1.Angle, a, b Point) Point
 func Intersection(a0, a1, b0, b1 Point) Point
 func OriginPoint() Point
 func Ortho(a Point) Point
 func PlanarCentroid(a, b, c Point) Point
 func PointFromCoords(x, y, z float64) Point
 func PointFromLatLng(ll LatLng) Point
 func Project(x, a, b Point) Point
 func Rotate(p, axis Point, angle s1.Angle) Point
 func TrueCentroid(a, b, c Point) Point
 func (p Point) ApproxEqual(other Point) bool
 func (p Point) CapBound() Cap
 func (p Point) CellUnionBound() []CellID
 func (p Point) Contains(other Point) bool
 func (p Point) ContainsCell(c Cell) bool
 func (p Point) ContainsPoint(other Point) bool
 func (p *Point) Decode(r io.Reader) error
 func (p Point) Distance(b Point) s1.Angle
 func (p Point) Encode(w io.Writer) error
 func (p Point) IntersectsCell(c Cell) bool
 func (p Point) PointCross(op Point) Point
 func (p Point) RectBound() Rect
 type PointVector
 func (p *PointVector) Chain(i int) Chain
 func (p *PointVector) ChainEdge(i, j int) Edge
 func (p *PointVector) ChainPosition(e int) ChainPosition
 func (p *PointVector) Dimension() int
 func (p *PointVector) Edge(i int) Edge
 func (p *PointVector) IsEmpty() bool
 func (p *PointVector) IsFull() bool
 func (p *PointVector) NumChains() int
 func (p *PointVector) NumEdges() int
 func (p *PointVector) ReferencePoint() ReferencePoint
 type Polygon
 func (p *Polygon) Area() float64
 func (p *Polygon) CapBound() Cap
 func (p *Polygon) CellUnionBound() []CellID
 func (p *Polygon) Centroid() Point
 func (p *Polygon) Chain(chainID int) Chain
 func (p *Polygon) ChainEdge(i, j int) Edge
 func (p *Polygon) ChainPosition(edgeID int) ChainPosition
 func (p *Polygon) Contains(o *Polygon) bool
 func (p *Polygon) ContainsCell(cell Cell) bool
 func (p *Polygon) ContainsPoint(point Point) bool
 func (p *Polygon) Decode(r io.Reader) error
 func (p *Polygon) Dimension() int
 func (p *Polygon) Edge(e int) Edge
 func (p *Polygon) Encode(w io.Writer) error
 func (p *Polygon) Intersects(o *Polygon) bool
 func (p *Polygon) IntersectsCell(cell Cell) bool
 func (p *Polygon) Invert()
 func (p *Polygon) IsEmpty() bool
 func (p *Polygon) IsFull() bool
 func (p *Polygon) LastDescendant(k int) int
 func (p *Polygon) Loop(k int) *Loop
 func (p *Polygon) Loops() []*Loop
 func (p *Polygon) NumChains() int
 func (p *Polygon) NumEdges() int
 func (p *Polygon) NumLoops() int
 func (p *Polygon) Parent(k int) (index int, ok bool)
 func (p *Polygon) RectBound() Rect
 func (p *Polygon) ReferencePoint() ReferencePoint
 func (p *Polygon) Validate() error
 type Polyline
 func (p *Polyline) ApproxEqual(o *Polyline) bool
 func (p *Polyline) CapBound() Cap
 func (p *Polyline) CellUnionBound() []CellID
 func (p *Polyline) Centroid() Point
 func (p *Polyline) Chain(chainID int) Chain
 func (p *Polyline) ChainEdge(chainID, offset int) Edge
 func (p *Polyline) ChainPosition(edgeID int) ChainPosition
 func (p *Polyline) ContainsCell(cell Cell) bool
 func (p *Polyline) ContainsPoint(point Point) bool
 func (p *Polyline) Decode(r io.Reader) error
 func (p *Polyline) Dimension() int
 func (p *Polyline) Edge(i int) Edge
 func (p Polyline) Encode(w io.Writer) error
 func (p *Polyline) Equal(b *Polyline) bool
 func (p *Polyline) Interpolate(fraction float64) (Point, int)
 func (p *Polyline) Intersects(o *Polyline) bool
 func (p *Polyline) IntersectsCell(cell Cell) bool
 func (p *Polyline) IsEmpty() bool
 func (p *Polyline) IsFull() bool
 func (p *Polyline) IsOnRight(point Point) bool
 func (p *Polyline) Length() s1.Angle
 func (p *Polyline) NumChains() int
 func (p *Polyline) NumEdges() int
 func (p *Polyline) Project(point Point) (Point, int)
 func (p *Polyline) RectBound() Rect
 func (p *Polyline) ReferencePoint() ReferencePoint
 func (p *Polyline) Reverse()
 func (p *Polyline) SubsampleVertices(tolerance s1.Angle) []int
 func (p *Polyline) Uninterpolate(point Point, nextVertex int) float64
 func (p *Polyline) Validate() error
 type Projection
 type Rect
 func (r Rect) AddPoint(ll LatLng) Rect
 func (r Rect) ApproxEqual(other Rect) bool
 func (r Rect) Area() float64
 func (r Rect) CapBound() Cap
 func (r Rect) CellUnionBound() []CellID
 func (r Rect) Center() LatLng
 func (r Rect) Centroid() Point
 func (r Rect) Contains(other Rect) bool
 func (r Rect) ContainsCell(c Cell) bool
 func (r Rect) ContainsLatLng(ll LatLng) bool
 func (r Rect) ContainsPoint(p Point) bool
 func (r *Rect) Decode(rd io.Reader) error
 func (r Rect) DirectedHausdorffDistance(other Rect) s1.Angle
 func (r Rect) DistanceToLatLng(ll LatLng) s1.Angle
 func (r Rect) Encode(w io.Writer) error
 func (r Rect) HausdorffDistance(other Rect) s1.Angle
 func (r Rect) Hi() LatLng
 func (r Rect) Intersection(other Rect) Rect
 func (r Rect) Intersects(other Rect) bool
 func (r Rect) IntersectsCell(c Cell) bool
 func (r Rect) IsEmpty() bool
 func (r Rect) IsFull() bool
 func (r Rect) IsPoint() bool
 func (r Rect) IsValid() bool
 func (r Rect) Lo() LatLng
 func (r Rect) PolarClosure() Rect
 func (r Rect) RectBound() Rect
 func (r Rect) Size() LatLng
 func (r Rect) String() string
 func (r Rect) Union(other Rect) Rect
 func (r Rect) Vertex(i int) LatLng
 type RectBounder
 type ReferencePoint
 type Region
 type RegionCoverer
 func (rc *RegionCoverer) CellUnion(region Region) CellUnion
 func (rc *RegionCoverer) Covering(region Region) CellUnion
 func (rc *RegionCoverer) FastCovering(region Region) CellUnion
 func (rc *RegionCoverer) InteriorCellUnion(region Region) CellUnion
 func (rc *RegionCoverer) InteriorCovering(region Region) CellUnion
 func (rc *RegionCoverer) IsCanonical(covering CellUnion) bool
 type RegionUnion
 type Shape
 type ShapeEdge
 type ShapeEdgeID
 type ShapeIndex
 func (s *ShapeIndex) Add(shape Shape) int32
 func (s *ShapeIndex) Begin() *ShapeIndexIterator
 func (s *ShapeIndex) Build()
 func (s *ShapeIndex) End() *ShapeIndexIterator
 func (s *ShapeIndex) IsFresh() bool
 func (s *ShapeIndex) Iterator() *ShapeIndexIterator
 func (s *ShapeIndex) Len() int
 func (s *ShapeIndex) NumEdges() int
 func (s *ShapeIndex) NumEdgesUpTo(limit int) int
 func (s *ShapeIndex) Region() *ShapeIndexRegion
 func (s *ShapeIndex) Remove(shape Shape)
 func (s *ShapeIndex) Reset()
 func (s *ShapeIndex) Shape(id int32) Shape
 type ShapeIndexCell
 type ShapeIndexIterator
 func (s *ShapeIndexIterator) Begin()
 func (s *ShapeIndexIterator) CellID() CellID
 func (s *ShapeIndexIterator) Center() Point
 func (s *ShapeIndexIterator) Done() bool
 func (s *ShapeIndexIterator) End()
 func (s *ShapeIndexIterator) IndexCell() *ShapeIndexCell
 func (s *ShapeIndexIterator) LocateCellID(target CellID) CellRelation
 func (s *ShapeIndexIterator) LocatePoint(p Point) bool
 func (s *ShapeIndexIterator) Next()
 func (s *ShapeIndexIterator) Prev() bool
 type ShapeIndexIteratorPos
 type ShapeIndexRegion
 type Snapper
 type VertexModel
 type WedgeRel
Examples ¶
Constants ¶
const ( // FaceBits is the number of bits used to encode the face number. FaceBits = 3 // NumFaces is the number of faces. NumFaces = 6 // MaxLevel is the number of levels needed to specify a leaf cell. MaxLevel = 30 // PosBits is the total number of position bits. The extra bit (61 rather // than 60) lets us encode each cell as its Hilbert curve position at the // cell center (which is halfway along the portion of the Hilbert curve that // fills that cell). PosBits = 2*MaxLevel + 1 // MaxSize is the maximum index of a valid leaf cell plus one. The range of // valid leaf cell indices is [0..MaxSize1]. MaxSize = 1 << MaxLevel )
const SentinelCellID = CellID(^uint64(0))
SentinelCellID is an invalid cell ID guaranteed to be larger than any valid cell ID. It is used primarily by ShapeIndex. The value is also used by some S2 types when encoding data. Note that the sentinel's RangeMin == RangeMax == itself.
Variables ¶
var ( MinAngleSpanMetric = Metric{1, 4.0 / 3} AvgAngleSpanMetric = Metric{1, math.Pi / 2} MaxAngleSpanMetric = Metric{1, 1.704897179199218452} )
Each cell is bounded by four planes passing through its four edges and the center of the sphere. These metrics relate to the angle between each pair of opposite bounding planes, or equivalently, between the planes corresponding to two different svalues or two different tvalues.
var ( MinWidthMetric = Metric{1, 2 * math.Sqrt2 / 3} AvgWidthMetric = Metric{1, 1.434523672886099389} MaxWidthMetric = Metric{1, MaxAngleSpanMetric.Deriv} )
The width of geometric figure is defined as the distance between two parallel bounding lines in a given direction. For cells, the minimum width is always attained between two opposite edges, and the maximum width is attained between two opposite vertices. However, for our purposes we redefine the width of a cell as the perpendicular distance between a pair of opposite edges. A cell therefore has two widths, one in each direction. The minimum width according to this definition agrees with the classic geometric one, but the maximum width is different. (The maximum geometric width corresponds to MaxDiag defined below.)
The average width in both directions for all cells at level k is approximately AvgWidthMetric.Value(k).
The width is useful for bounding the minimum or maximum distance from a point on one edge of a cell to the closest point on the opposite edge. For example, this is useful when growing regions by a fixed distance.
var ( MinEdgeMetric = Metric{1, 2 * math.Sqrt2 / 3} AvgEdgeMetric = Metric{1, 1.459213746386106062} MaxEdgeMetric = Metric{1, MaxAngleSpanMetric.Deriv} // MaxEdgeAspect is the maximum edge aspect ratio over all cells at any level, // where the edge aspect ratio of a cell is defined as the ratio of its longest // edge length to its shortest edge length. MaxEdgeAspect = 1.442615274452682920 MinAreaMetric = Metric{2, 8 * math.Sqrt2 / 9} AvgAreaMetric = Metric{2, 4 * math.Pi / 6} MaxAreaMetric = Metric{2, 2.635799256963161491} )
The edge length metrics can be used to bound the minimum, maximum, or average distance from the center of one cell to the center of one of its edge neighbors. In particular, it can be used to bound the distance between adjacent cell centers along the spacefilling Hilbert curve for cells at any given level.
var ( MinDiagMetric = Metric{1, 8 * math.Sqrt2 / 9} AvgDiagMetric = Metric{1, 2.060422738998471683} MaxDiagMetric = Metric{1, 2.438654594434021032} // MaxDiagAspect is the maximum diagonal aspect ratio over all cells at any // level, where the diagonal aspect ratio of a cell is defined as the ratio // of its longest diagonal length to its shortest diagonal length. MaxDiagAspect = math.Sqrt(3) )
The maximum diagonal is also the maximum diameter of any cell, and also the maximum geometric width (see the comment for widths). For example, the distance from an arbitrary point to the closest cell center at a given level is at most half the maximum diagonal length.
Functions ¶
func Angle ¶
Angle returns the interior angle at the vertex B in the triangle ABC. The return value is always in the range [0, pi]. All points should be normalized. Ensures that Angle(a,b,c) == Angle(c,b,a) for all a,b,c.
The angle is undefined if A or C is diametrically opposite from B, and becomes numerically unstable as the length of edge AB or BC approaches 180 degrees.
func AngleContainsVertex ¶
AngleContainsVertex reports if the angle ABC contains its vertex B. Containment is defined such that if several polygons tile the region around a vertex, then exactly one of those polygons contains that vertex. Returns false for degenerate angles of the form ABA.
Note that this method is not sufficient to determine vertex containment in polygons with duplicate vertices (such as the polygon ABCADE). Use ContainsVertexQuery for such polygons. AngleContainsVertex(a, b, c) is equivalent to using ContainsVertexQuery as follows:
ContainsVertexQuery query(b); query.AddEdge(a, 1); // incoming query.AddEdge(c, 1); // outgoing return query.ContainsVertex() > 0;
Useful properties of AngleContainsVertex:
(1) AngleContainsVertex(a,b,a) == false (2) AngleContainsVertex(a,b,c) == !AngleContainsVertex(c,b,a) unless a == c (3) Given vertices v_1 ... v_k ordered cyclically CCW around vertex b, AngleContainsVertex(v_{i+1}, b, v_i) is true for exactly one value of i.
REQUIRES: a != b && b != c
func ChordAngleBetweenPoints ¶
func ChordAngleBetweenPoints(x, y Point) s1.ChordAngle
ChordAngleBetweenPoints constructs a ChordAngle corresponding to the distance between the two given points. The points must be unit length.
func ClipEdge ¶
ClipEdge returns the portion of the edge defined by AB that is contained by the given rectangle. If there is no intersection, false is returned and aClip and bClip are undefined.
func ClipToFace ¶
ClipToFace returns the (u,v) coordinates for the portion of the edge AB that intersects the given face, or false if the edge AB does not intersect. This method guarantees that the clipped vertices lie within the [1,1]x[1,1] cube face rectangle and are within faceClipErrorUVDist of the line AB, but the results may differ from those produced by FaceSegments.
func ClipToPaddedFace ¶
ClipToPaddedFace returns the (u,v) coordinates for the portion of the edge AB that intersects the given face, but rather than clipping to the square [1,1]x[1,1] in (u,v) space, this method clips to [R,R]x[R,R] where R=(1+padding). Padding must be nonnegative.
func CompareDistance ¶
func CompareDistance(x, y Point, r s1.ChordAngle) int
CompareDistance returns 1, 0, or +1 according to whether the distance XY is respectively less than, equal to, or greater than the provided chord angle. Distances are measured with respect to the positions of all points as though they are projected to lie exactly on the surface of the unit sphere.
func CompareDistances ¶
CompareDistances returns 1, 0, or +1 according to whether AX < BX, A == B, or AX > BX respectively. Distances are measured with respect to the positions of X, A, and B as though they were reprojected to lie exactly on the surface of the unit sphere. Furthermore, this method uses symbolic perturbations to ensure that the result is nonzero whenever A != B, even when AX == BX exactly, or even when A and B project to the same point on the sphere. Such results are guaranteed to be selfconsistent, i.e. if AB < BC and BC < AC, then AB < AC.
func DistanceFraction ¶
DistanceFraction returns the distance ratio of the point X along an edge AB. If X is on the line segment AB, this is the fraction T such that X == Interpolate(T, A, B).
This requires that A and B are distinct.
func DistanceFromSegment ¶
DistanceFromSegment returns the distance of point X from line segment AB. The points are expected to be normalized. The result is very accurate for small distances but may have some numerical error if the distance is large (approximately pi/2 or greater). The case A == B is handled correctly.
func EdgeOrVertexCrossing ¶
EdgeOrVertexCrossing is a convenience function that calls CrossingSign to handle cases where all four vertices are distinct, and VertexCrossing to handle cases where two or more vertices are the same. This defines a crossing function such that pointinpolygon containment tests can be implemented by simply counting edge crossings.
func EdgePairClosestPoints ¶
EdgePairClosestPoints returns the pair of points (a, b) that achieves the minimum distance between edges a0a1 and b0b1, where a is a point on a0a1 and b is a point on b0b1. If the two edges intersect, a and b are both equal to the intersection point. Handles a0 == a1 and b0 == b1 correctly.
func GirardArea ¶
GirardArea returns the area of the triangle computed using Girard's formula. All points should be unit length, and no two points should be antipodal.
This method is about twice as fast as PointArea() but has poor relative accuracy for small triangles. The maximum error is about 5e15 (about 0.25 square meters on the Earth's surface) and the average error is about 1e15. These bounds apply to triangles of any size, even as the maximum edge length of the triangle approaches 180 degrees. But note that for such triangles, tiny perturbations of the input points can change the true mathematical area dramatically.
func IsDistanceLess ¶
func IsDistanceLess(x, a, b Point, limit s1.ChordAngle) bool
IsDistanceLess reports whether the distance from X to the edge AB is less than limit. (For less than or equal to, specify limit.Successor()). This method is faster than DistanceFromSegment(). If you want to compare against a fixed s1.Angle, you should convert it to an s1.ChordAngle once and save the value, since this conversion is relatively expensive.
func IsInteriorDistanceLess ¶
func IsInteriorDistanceLess(x, a, b Point, limit s1.ChordAngle) bool
IsInteriorDistanceLess reports whether the minimum distance from X to the edge AB is attained at an interior point of AB (i.e., not an endpoint), and that distance is less than limit. (Specify limit.Successor() for less than or equal to).
func OrderedCCW ¶
OrderedCCW returns true if the edges OA, OB, and OC are encountered in that order while sweeping CCW around the point O.
You can think of this as testing whether A <= B <= C with respect to the CCW ordering around O that starts at A, or equivalently, whether B is contained in the range of angles (inclusive) that starts at A and extends CCW to C. Properties:
(1) If OrderedCCW(a,b,c,o) && OrderedCCW(b,a,c,o), then a == b (2) If OrderedCCW(a,b,c,o) && OrderedCCW(a,c,b,o), then b == c (3) If OrderedCCW(a,b,c,o) && OrderedCCW(c,b,a,o), then a == b == c (4) If a == b or b == c, then OrderedCCW(a,b,c,o) is true (5) Otherwise if a == c, then OrderedCCW(a,b,c,o) is false
func PointArea ¶
PointArea returns the area of triangle ABC. This method combines two different algorithms to get accurate results for both large and small triangles. The maximum error is about 5e15 (about 0.25 square meters on the Earth's surface), the same as GirardArea below, but unlike that method it is also accurate for small triangles. Example: when the true area is 100 square meters, PointArea yields an error about 1 trillion times smaller than GirardArea.
All points should be unit length, and no two points should be antipodal. The area is always positive.
func Sign ¶
Sign returns true if the points A, B, C are strictly counterclockwise, and returns false if the points are clockwise or collinear (i.e. if they are all contained on some great circle).
Due to numerical errors, situations may arise that are mathematically impossible, e.g. ABC may be considered strictly CCW while BCA is not. However, the implementation guarantees the following:
If Sign(a,b,c), then !Sign(c,b,a) for all a,b,c.
func SignedArea ¶
SignedArea returns a positive value for counterclockwise triangles and a negative value otherwise (similar to PointArea).
func TurnAngle ¶
TurnAngle returns the exterior angle at vertex B in the triangle ABC. The return value is positive if ABC is counterclockwise and negative otherwise. If you imagine an ant walking from A to B to C, this is the angle that the ant turns at vertex B (positive = left = CCW, negative = right = CW). This quantity is also known as the "geodesic curvature" at B.
Ensures that TurnAngle(a,b,c) == TurnAngle(c,b,a) for all distinct a,b,c. The result is undefined if (a == b  b == c), but is either Pi or Pi if (a == c). All points should be normalized.
func UpdateMaxDistance ¶
func UpdateMaxDistance(x, a, b Point, maxDist s1.ChordAngle) (s1.ChordAngle, bool)
UpdateMaxDistance checks if the distance from X to the edge AB is greater than maxDist, and if so, returns the updated value and true. Otherwise it returns false. The case A == B is handled correctly.
func UpdateMinDistance ¶
func UpdateMinDistance(x, a, b Point, minDist s1.ChordAngle) (s1.ChordAngle, bool)
UpdateMinDistance checks if the distance from X to the edge AB is less than minDist, and if so, returns the updated value and true. The case A == B is handled correctly.
Use this method when you want to compute many distances and keep track of the minimum. It is significantly faster than using DistanceFromSegment because (1) using s1.ChordAngle is much faster than s1.Angle, and (2) it can save a lot of work by not actually computing the distance when it is obviously larger than the current minimum.
func UpdateMinInteriorDistance ¶
func UpdateMinInteriorDistance(x, a, b Point, minDist s1.ChordAngle) (s1.ChordAngle, bool)
UpdateMinInteriorDistance reports whether the minimum distance from X to AB is attained at an interior point of AB (i.e., not an endpoint), and that distance is less than minDist. If so, the value of minDist is updated and true is returned. Otherwise it is unchanged and returns false.
func VertexCrossing ¶
VertexCrossing reports whether two edges "cross" in such a way that pointinpolygon containment tests can be implemented by counting the number of edge crossings.
Given two edges AB and CD where at least two vertices are identical (i.e. CrossingSign(a,b,c,d) == 0), the basic rule is that a "crossing" occurs if AB is encountered after CD during a CCW sweep around the shared vertex starting from a fixed reference point.
Note that according to this rule, if AB crosses CD then in general CD does not cross AB. However, this leads to the correct result when counting polygon edge crossings. For example, suppose that A,B,C are three consecutive vertices of a CCW polygon. If we now consider the edge crossings of a segment BP as P sweeps around B, the crossing number changes parity exactly when BP crosses BA or BC.
Useful properties of VertexCrossing (VC):
(1) VC(a,a,c,d) == VC(a,b,c,c) == false (2) VC(a,b,a,b) == VC(a,b,b,a) == true (3) VC(a,b,c,d) == VC(a,b,d,c) == VC(b,a,c,d) == VC(b,a,d,c) (3) If exactly one of a,b equals one of c,d, then exactly one of VC(a,b,c,d) and VC(c,d,a,b) is true
It is an error to call this method with 4 distinct vertices.
func WedgeContains ¶
WedgeContains reports whether nonempty wedge A=(a0, ab1, a2) contains B=(b0, ab1, b2). Equivalent to WedgeRelation == WedgeProperlyContains  WedgeEquals.
func WedgeIntersects ¶
WedgeIntersects reports whether nonempty wedge A=(a0, ab1, a2) intersects B=(b0, ab1, b2). Equivalent but faster than WedgeRelation != WedgeIsDisjoint
Types ¶
type Cap ¶
type Cap struct {
// contains filtered or unexported fields
}
Cap represents a discshaped region defined by a center and radius. Technically this shape is called a "spherical cap" (rather than disc) because it is not planar; the cap represents a portion of the sphere that has been cut off by a plane. The boundary of the cap is the circle defined by the intersection of the sphere and the plane. For containment purposes, the cap is a closed set, i.e. it contains its boundary.
For the most part, you can use a spherical cap wherever you would use a disc in planar geometry. The radius of the cap is measured along the surface of the sphere (rather than the straightline distance through the interior). Thus a cap of radius π/2 is a hemisphere, and a cap of radius π covers the entire sphere.
The center is a point on the surface of the unit sphere. (Hence the need for it to be of unit length.)
A cap can also be defined by its center point and height. The height is the distance from the center point to the cutoff plane. There is also support for "empty" and "full" caps, which contain no points and all points respectively.
Here are some useful relationships between the cap height (h), the cap radius (r), the maximum chord length from the cap's center (d), and the radius of cap's base (a).
h = 1  cos(r) = 2 * sin^2(r/2) d^2 = 2 * h = a^2 + h^2
The zero value of Cap is an invalid cap. Use EmptyCap to get a valid empty cap.
func CapFromCenterAngle ¶
CapFromCenterAngle constructs a cap with the given center and angle.
func CapFromCenterArea ¶
CapFromCenterArea constructs a cap with the given center and surface area. Note that the area can also be interpreted as the solid angle subtended by the cap (because the sphere has unit radius). A negative area yields an empty cap; an area of 4*π or more yields a full cap.
func CapFromCenterChordAngle ¶
func CapFromCenterChordAngle(center Point, radius s1.ChordAngle) Cap
CapFromCenterChordAngle constructs a cap where the angle is expressed as an s1.ChordAngle. This constructor is more efficient than using an s1.Angle.
func CapFromCenterHeight ¶
CapFromCenterHeight constructs a cap with the given center and height. A negative height yields an empty cap; a height of 2 or more yields a full cap. The center should be unit length.
func CapFromPoint ¶
CapFromPoint constructs a cap containing a single point.
func (Cap) AddCap ¶
AddCap increases the cap height if necessary to include the other cap. If this cap is empty, it is set to the other cap.
func (Cap) AddPoint ¶
AddPoint increases the cap if necessary to include the given point. If this cap is empty, then the center is set to the point with a zero height. p must be unitlength.
func (Cap) ApproxEqual ¶
ApproxEqual reports whether this cap is equal to the other cap within the given tolerance.
func (Cap) CapBound ¶
CapBound returns a bounding spherical cap. This is not guaranteed to be exact.
func (Cap) CellUnionBound ¶
CellUnionBound computes a covering of the Cap. In general the covering consists of at most 4 cells except for very large caps, which may need up to 6 cells. The output is not sorted.
func (Cap) Centroid ¶
Centroid returns the true centroid of the cap multiplied by its surface area The result lies on the ray from the origin through the cap's center, but it is not unit length. Note that if you just want the "surface centroid", i.e. the normalized result, then it is simpler to call Center.
The reason for multiplying the result by the cap area is to make it easier to compute the centroid of more complicated shapes. The centroid of a union of disjoint regions can be computed simply by adding their Centroid() results. Caveat: for caps that contain a single point (i.e., zero radius), this method always returns the origin (0, 0, 0). This is because shapes with no area don't affect the centroid of a union whose total area is positive.
func (Cap) Complement ¶
Complement returns the complement of the interior of the cap. A cap and its complement have the same boundary but do not share any interior points. The complement operator is not a bijection because the complement of a singleton cap (containing a single point) is the same as the complement of an empty cap.
func (Cap) ContainsCell ¶
ContainsCell reports whether the cap contains the given cell.
func (Cap) ContainsPoint ¶
ContainsPoint reports whether this cap contains the point.
func (Cap) Expanded ¶
Expanded returns a new cap expanded by the given angle. If the cap is empty, it returns an empty cap.
func (Cap) Height ¶
Height returns the height of the cap. This is the distance from the center point to the cutoff plane.
func (Cap) InteriorContainsPoint ¶
InteriorContainsPoint reports whether the point is within the interior of this cap.
func (Cap) InteriorIntersects ¶
InteriorIntersects reports whether this caps interior intersects the other cap.
func (Cap) Intersects ¶
Intersects reports whether this cap intersects the other cap. i.e. whether they have any points in common.
func (Cap) IntersectsCell ¶
IntersectsCell reports whether the cap intersects the cell.
func (Cap) Radius ¶
Radius returns the cap radius as an s1.Angle. (Note that the cap angle is stored internally as a ChordAngle, so this method requires a trigonometric operation and may yield a slightly different result than the value passed to CapFromCenterAngle).
type Cell ¶
type Cell struct {
// contains filtered or unexported fields
}
Cell is an S2 region object that represents a cell. Unlike CellIDs, it supports efficient containment and intersection tests. However, it is also a more expensive representation.
func CellFromCellID ¶
CellFromCellID constructs a Cell corresponding to the given CellID.
func CellFromLatLng ¶
CellFromLatLng constructs a cell for the given LatLng.
func CellFromPoint ¶
CellFromPoint constructs a cell for the given Point.
func (Cell) ApproxArea ¶
ApproxArea returns the approximate area of this cell. This method is accurate to within 3% percent for all cell sizes and accurate to within 0.1% for cells at level 5 or higher (i.e. squares 350km to a side or smaller on the Earth's surface). It is moderately cheap to compute.
func (Cell) AverageArea ¶
AverageArea returns the average area of cells at the level of this cell. This is accurate to within a factor of 1.7.
func (Cell) BoundaryDistance ¶
func (c Cell) BoundaryDistance(target Point) s1.ChordAngle
BoundaryDistance reports the distance from the cell boundary to the given point.
func (Cell) CellUnionBound ¶
CellUnionBound computes a covering of the Cell.
func (Cell) Center ¶
Center returns the direction vector corresponding to the center in (s,t)space of the given cell. This is the point at which the cell is divided into four subcells; it is not necessarily the centroid of the cell in (u,v)space or (x,y,z)space
func (Cell) Children ¶
Children returns the four direct children of this cell in traversal order and returns true. If this is a leaf cell, or the children could not be created, false is returned. The C++ method is called Subdivide.
func (Cell) ContainsCell ¶
ContainsCell reports whether this cell contains the other cell.
func (Cell) ContainsPoint ¶
ContainsPoint reports whether this cell contains the given point. Note that unlike Loop/Polygon, a Cell is considered to be a closed set. This means that a point on a Cell's edge or vertex belong to the Cell and the relevant adjacent Cells too.
If you want every point to be contained by exactly one Cell, you will need to convert the Cell to a Loop.
func (Cell) Distance ¶
func (c Cell) Distance(target Point) s1.ChordAngle
Distance reports the distance from the cell to the given point. Returns zero if the point is inside the cell.
func (Cell) DistanceToCell ¶
func (c Cell) DistanceToCell(target Cell) s1.ChordAngle
DistanceToCell returns the minimum distance from this cell to the given cell. It returns zero if one cell contains the other.
func (Cell) DistanceToEdge ¶
func (c Cell) DistanceToEdge(a, b Point) s1.ChordAngle
DistanceToEdge returns the minimum distance from the cell to the given edge AB. Returns zero if the edge intersects the cell interior.
func (Cell) Edge ¶
Edge returns the inwardfacing normal of the great circle passing through the CCW ordered edge from vertex k to vertex k+1 (mod 4) (for k = 0,1,2,3).
func (Cell) IntersectsCell ¶
IntersectsCell reports whether the intersection of this cell and the other cell is not nil.
func (Cell) MaxDistance ¶
func (c Cell) MaxDistance(target Point) s1.ChordAngle
MaxDistance reports the maximum distance from the cell (including its interior) to the given point.
func (Cell) MaxDistanceToCell ¶
func (c Cell) MaxDistanceToCell(target Cell) s1.ChordAngle
MaxDistanceToCell returns the maximum distance from the cell (including its interior) to the given target cell.
func (Cell) MaxDistanceToEdge ¶
func (c Cell) MaxDistanceToEdge(a, b Point) s1.ChordAngle
MaxDistanceToEdge returns the maximum distance from the cell (including its interior) to the given edge AB.
type CellID ¶
type CellID uint64
CellID uniquely identifies a cell in the S2 cell decomposition. The most significant 3 bits encode the face number (05). The remaining 61 bits encode the position of the center of this cell along the Hilbert curve on that face. The zero value and the value (1<<64)1 are invalid cell IDs. The first compares less than any valid cell ID, the second as greater than any valid cell ID.
Sequentially increasing cell IDs follow a continuous spacefilling curve over the entire sphere. They have the following properties:
The ID of a cell at level k consists of a 3bit face number followed by k bit pairs that recursively select one of the four children of each cell. The next bit is always 1, and all other bits are 0. Therefore, the level of a cell is determined by the position of its lowestnumbered bit that is turned on (for a cell at level k, this position is 2 * (MaxLevel  k)).
The ID of a parent cell is at the midpoint of the range of IDs spanned by its children (or by its descendants at any level).
Leaf cells are often used to represent points on the unit sphere, and this type provides methods for converting directly between these two representations. For cells that represent 2D regions rather than discrete point, it is better to use Cells.
func CellIDFromFace ¶
CellIDFromFace returns the cell corresponding to a given S2 cube face.
func CellIDFromFacePosLevel ¶
CellIDFromFacePosLevel returns a cell given its face in the range [0,5], the 61bit Hilbert curve position pos within that face, and the level in the range [0,MaxLevel]. The position in the cell ID will be truncated to correspond to the Hilbert curve position at the center of the returned cell.
func CellIDFromLatLng ¶
CellIDFromLatLng returns the leaf cell containing ll.
func CellIDFromString ¶
CellIDFromString returns a CellID from a string in the form "1/3210".
func CellIDFromToken ¶
CellIDFromToken returns a cell given a hexencoded string of its uint64 ID.
func FloodFillRegionCovering ¶
FloodFillRegionCovering returns all edgeconnected cells at the same level as the given CellID that intersect the given region, in arbitrary order.
func SimpleRegionCovering ¶
SimpleRegionCovering returns a set of cells at the given level that cover the connected region and a starting point on the boundary or inside the region. The cells are returned in arbitrary order.
Note that this method is not faster than the regular Covering method for most region types, such as Cap or Polygon, and in fact it can be much slower when the output consists of a large number of cells. Currently it can be faster at generating coverings of long narrow regions such as polylines, but this may change in the future.
func (CellID) Advance ¶
Advance advances or retreats the indicated number of steps along the Hilbert curve at the current level, and returns the new position. The position is never advanced past End() or before Begin().
func (CellID) AdvanceWrap ¶
AdvanceWrap advances or retreats the indicated number of steps along the Hilbert curve at the current level and returns the new position. The position wraps between the first and last faces as necessary.
func (CellID) AllNeighbors ¶
AllNeighbors returns all neighbors of this cell at the given level. Two cells X and Y are neighbors if their boundaries intersect but their interiors do not. In particular, two cells that intersect at a single point are neighbors. Note that for cells adjacent to a face vertex, the same neighbor may be returned more than once. There could be up to eight neighbors including the diagonal ones that share the vertex.
This requires level >= ci.Level().
func (CellID) ChildBegin ¶
ChildBegin returns the first child in a traversal of the children of this cell, in Hilbert curve order.
for ci := c.ChildBegin(); ci != c.ChildEnd(); ci = ci.Next() { ... }
func (CellID) ChildBeginAtLevel ¶
ChildBeginAtLevel returns the first cell in a traversal of children a given level deeper than this cell, in Hilbert curve order. The given level must be no smaller than the cell's level. See ChildBegin for example use.
func (CellID) ChildEnd ¶
ChildEnd returns the first cell after a traversal of the children of this cell in Hilbert curve order. The returned cell may be invalid.
func (CellID) ChildEndAtLevel ¶
ChildEndAtLevel returns the first cell after the last child in a traversal of children a given level deeper than this cell, in Hilbert curve order. The given level must be no smaller than the cell's level. The returned cell may be invalid.
func (CellID) ChildPosition ¶
ChildPosition returns the child position (0..3) of this cell's ancestor at the given level, relative to its parent. The argument should be in the range 1..kMaxLevel. For example, ChildPosition(1) returns the position of this cell's level1 ancestor within its toplevel face cell.
func (CellID) Children ¶
Children returns the four immediate children of this cell. If ci is a leaf cell, it returns four identical cells that are not the children.
func (CellID) CommonAncestorLevel ¶
CommonAncestorLevel returns the level of the common ancestor of the two S2 CellIDs.
func (CellID) EdgeNeighbors ¶
EdgeNeighbors returns the four cells that are adjacent across the cell's four edges. Edges 0, 1, 2, 3 are in the down, right, up, left directions in the face space. All neighbors are guaranteed to be distinct.
func (CellID) Intersects ¶
Intersects returns true iff the CellID intersects oci.
func (CellID) IsLeaf ¶
IsLeaf returns whether this cell ID is at the deepest level; that is, the level at which the cells are smallest.
func (CellID) Level ¶
Level returns the subdivision level of this cell ID, in the range [0, MaxLevel].
func (CellID) MaxTile ¶
MaxTile returns the largest cell with the same RangeMin such that RangeMax < limit.RangeMin. It returns limit if no such cell exists. This method can be used to generate a small set of CellIDs that covers a given range (a tiling). This example shows how to generate a tiling for a semiopen range of leaf cells [start, limit):
for id := start.MaxTile(limit); id != limit; id = id.Next().MaxTile(limit)) { ... }
Note that in general the cells in the tiling will be of different sizes; they gradually get larger (near the middle of the range) and then gradually get smaller as limit is approached.
func (CellID) Next ¶
Next returns the next cell along the Hilbert curve. This is expected to be used with ChildBegin and ChildEnd, or ChildBeginAtLevel and ChildEndAtLevel.
func (CellID) NextWrap ¶
NextWrap returns the next cell along the Hilbert curve, wrapping from last to first as necessary. This should not be used with ChildBegin and ChildEnd.
func (CellID) Parent ¶
Parent returns the cell at the given level, which must be no greater than the current level.
func (CellID) Point ¶
Point returns the center of the s2 cell on the sphere as a Point. The maximum directional error in Point (compared to the exact mathematical result) is 1.5 * dblEpsilon radians, and the maximum length error is 2 * dblEpsilon (the same as Normalize).
func (CellID) Pos ¶
Pos returns the position along the Hilbert curve of this cell ID, in the range [0,2^PosBits1].
func (CellID) PrevWrap ¶
PrevWrap returns the previous cell along the Hilbert curve, wrapping around from first to last as necessary. This should not be used with ChildBegin and ChildEnd.
func (CellID) String ¶
String returns the string representation of the cell ID in the form "1/3210".
func (CellID) ToToken ¶
ToToken returns a hexencoded string of the uint64 cell id, with leading zeros included but trailing zeros stripped.
func (CellID) VertexNeighbors ¶
VertexNeighbors returns the neighboring cellIDs with vertex closest to this cell at the given level. (Normally there are four neighbors, but the closest vertex may only have three neighbors if it is one of the 8 cube vertices.)
type CellIDSnapper ¶
type CellIDSnapper struct {
// contains filtered or unexported fields
}
CellIDSnapper is a type that snaps vertices to CellID centers. This can be useful if you want to encode your geometry compactly for example. You can snap to the centers of cells at any level.
Every snap level has a corresponding minimum snap radius, which is simply the maximum distance that a vertex can move when snapped. It is approximately equal to half of the maximum diagonal length for cells at the chosen level. You can also set the snap radius to a larger value; for example, you could snap to the centers of leaf cells (1cm resolution) but set the snapRadius to 10m. This would result in significant extra simplification, without moving vertices unnecessarily (i.e., vertices that are at least 10m away from all other vertices will move by less than 1cm).
func CellIDSnapperForLevel ¶
func CellIDSnapperForLevel(level int) CellIDSnapper
CellIDSnapperForLevel returns a snap function at the given level.
func NewCellIDSnapper ¶
func NewCellIDSnapper() CellIDSnapper
NewCellIDSnapper returns a snap function with the default level set.
func (CellIDSnapper) MaxEdgeDeviation ¶
func (sf CellIDSnapper) MaxEdgeDeviation() s1.Angle
MaxEdgeDeviation returns the maximum edge deviation this type supports.
func (CellIDSnapper) MinEdgeVertexSeparation ¶
func (sf CellIDSnapper) MinEdgeVertexSeparation() s1.Angle
MinEdgeVertexSeparation returns the guaranteed minimum spacing between edges and nonincident vertices in the output. For CellID snapping, the minimum separation between edges and nonincident vertices depends on level and snapRadius. It can be as low as 0.219 * snapRadius, but is typically 0.5 * snapRadius or more.
func (CellIDSnapper) MinVertexSeparation ¶
func (sf CellIDSnapper) MinVertexSeparation() s1.Angle
MinVertexSeparation returns the guaranteed minimum distance between vertices in the output. This is generally some fraction of SnapRadius. For CellID snapping, the minimum separation between vertices depends on level and snapRadius. It can vary between 0.5 * snapRadius and snapRadius.
func (CellIDSnapper) SnapPoint ¶
func (sf CellIDSnapper) SnapPoint(point Point) Point
SnapPoint returns a candidate snap site for the given point.
func (CellIDSnapper) SnapRadius ¶
func (sf CellIDSnapper) SnapRadius() s1.Angle
SnapRadius reports the maximum distance that vertices can move when snapped. This requires that SnapRadius <= maxSnapRadius Defines the snap radius to be used (see Builder). The snap radius must be at least the minimum value for the current level, but larger values can also be used (e.g., to simplify the geometry).
This requires snapRadius >= MinSnapRadiusForLevel(level) and snapRadius <= maxSnapRadius
type CellIndex ¶
type CellIndex struct {
// contains filtered or unexported fields
}
CellIndex stores a collection of (CellID, label) pairs.
The CellIDs may be overlapping or contain duplicate values. For example, a CellIndex could store a collection of CellUnions, where each CellUnion gets its own nonnegative int32 label.
Similar to ShapeIndex and PointIndex which map each stored element to an identifier, CellIndex stores a label that is typically used to map the results of queries back to client's specific data.
The zero value for a CellIndex is sufficient when constructing a CellIndex.
To build a CellIndex where each Cell has a distinct label, call Add for each (CellID, label) pair, and then Build the index. For example:
// contents is a mapping of an identifier in my system (restaurantID, // vehicleID, etc) to a CellID var contents = map[int32]CellID{...} for key, val := range contents { index.Add(val, key) } index.Build()
There is also a helper method that adds all elements of CellUnion with the same label:
index.AddCellUnion(cellUnion, label)
Note that the index is not dynamic; the contents of the index cannot be changed once it has been built. Adding more after calling Build results in undefined behavior of the index.
There are several options for retrieving data from the index. The simplest is to use a builtin method such as IntersectingLabels (which returns the labels of all cells that intersect a given target CellUnion):
labels := index.IntersectingLabels(targetUnion);
Alternatively, you can use a ClosestCellQuery which computes the cell(s) that are closest to a given target geometry.
For example, here is how to find all cells that are closer than distanceLimit to a given target point:
query := NewClosestCellQuery(cellIndex, opts) target := NewMinDistanceToPointTarget(targetPoint); for result := range query.FindCells(target) { // result.Distance() is the distance to the target. // result.CellID() is the indexed CellID. // result.Label() is the label associated with the CellID. DoSomething(targetPoint, result); }
Internally, the index consists of a set of nonoverlapping leaf cell ranges that subdivide the sphere and such that each range intersects a particular set of (cellID, label) pairs.
Most clients should use either the methods such as VisitIntersectingCells and IntersectingLabels, or a helper such as ClosestCellQuery.
func (*CellIndex) AddCellUnion ¶
AddCellUnion adds all of the elements of the given CellUnion to the index with the same label.
type CellIndexContentsIterator ¶
type CellIndexContentsIterator struct {
// contains filtered or unexported fields
}
CellIndexContentsIterator is an iterator that visits the (CellID, label) pairs that cover a set of leaf cell ranges (see CellIndexRangeIterator). Note that when multiple leaf cell ranges are visited, this iterator only guarantees that each result will be reported at least once, i.e. duplicate values may be suppressed. If you want duplicate values to be reported again, be sure to call Clear first.
In particular, the implementation guarantees that when multiple leaf cell ranges are visited in monotonically increasing order, then each (CellID, label) pair is reported exactly once.
func NewCellIndexContentsIterator ¶
func NewCellIndexContentsIterator(index *CellIndex) *CellIndexContentsIterator
NewCellIndexContentsIterator returns a new contents iterator.
Note that the iterator needs to be positioned using StartUnion before it can be safely used.
func (*CellIndexContentsIterator) CellID ¶
func (c *CellIndexContentsIterator) CellID() CellID
CellID returns the current CellID.
func (*CellIndexContentsIterator) Clear ¶
func (c *CellIndexContentsIterator) Clear()
Clear clears all state with respect to which range(s) have been visited.
func (*CellIndexContentsIterator) Done ¶
func (c *CellIndexContentsIterator) Done() bool
Done reports if all (CellID, label) pairs have been visited.
func (*CellIndexContentsIterator) Label ¶
func (c *CellIndexContentsIterator) Label() int32
Label returns the current Label.
func (*CellIndexContentsIterator) Next ¶
func (c *CellIndexContentsIterator) Next()
Next advances the iterator to the next (CellID, label) pair covered by the current leaf cell range.
This requires the iterator to not be done.
func (*CellIndexContentsIterator) StartUnion ¶
func (c *CellIndexContentsIterator) StartUnion(r *CellIndexRangeIterator)
StartUnion positions the ContentsIterator at the first (cell_id, label) pair that covers the given leaf cell range. Note that when multiple leaf cell ranges are visited using the same ContentsIterator, duplicate values may be suppressed. If you don't want this behavior, call Reset() first.
type CellIndexIterator ¶
type CellIndexIterator struct { }
CellIndexIterator is an iterator that visits the entire set of indexed (CellID, label) pairs in an unspecified order.
func NewCellIndexIterator ¶
func NewCellIndexIterator(index *CellIndex) *CellIndexIterator
NewCellIndexIterator creates an iterator for the given CellIndex.
type CellIndexRangeIterator ¶
type CellIndexRangeIterator struct {
// contains filtered or unexported fields
}
CellIndexRangeIterator is an iterator that seeks and iterates over a set of nonoverlapping leaf cell ranges that cover the entire sphere. The indexed (CellID, label) pairs that intersect the current leaf cell range can be visited using CellIndexContentsIterator (see below).
func NewCellIndexNonEmptyRangeIterator ¶
func NewCellIndexNonEmptyRangeIterator(index *CellIndex) *CellIndexRangeIterator
NewCellIndexNonEmptyRangeIterator creates an iterator for the given CellIndex. The iterator is initially *unpositioned*; you must call a positioning method such as Begin() or Seek() before accessing its contents.
func NewCellIndexRangeIterator ¶
func NewCellIndexRangeIterator(index *CellIndex) *CellIndexRangeIterator
NewCellIndexRangeIterator creates an iterator for the given CellIndex. The iterator is initially *unpositioned*; you must call a positioning method such as Begin() or Seek() before accessing its contents.
func (*CellIndexRangeIterator) Advance ¶
func (c *CellIndexRangeIterator) Advance(n int) bool
Advance reports if advancing would leave it positioned on a valid range. If the value would not be valid, the positioning is not changed.
func (*CellIndexRangeIterator) Begin ¶
func (c *CellIndexRangeIterator) Begin()
Begin positions the iterator at the first range of leaf cells (if any).
func (*CellIndexRangeIterator) Done ¶
func (c *CellIndexRangeIterator) Done() bool
Done reports if the iterator is positioned beyond the last valid range.
func (*CellIndexRangeIterator) Finish ¶
func (c *CellIndexRangeIterator) Finish()
Finish positions the iterator so that done is true.
func (*CellIndexRangeIterator) IsEmpty ¶
func (c *CellIndexRangeIterator) IsEmpty() bool
IsEmpty reports if no (CellID, label) pairs intersect this range. Also returns true if done() is true.
func (*CellIndexRangeIterator) LimitID ¶
func (c *CellIndexRangeIterator) LimitID() CellID
LimitID reports the noninclusive end of the current range of leaf CellIDs.
This assumes the iterator is not done.
func (*CellIndexRangeIterator) Next ¶
func (c *CellIndexRangeIterator) Next()
Next advances the iterator to the next range of leaf cells.
This assumes the iterator is not done.
func (*CellIndexRangeIterator) Prev ¶
func (c *CellIndexRangeIterator) Prev() bool
Prev positions the iterator at the previous entry and reports whether it was not already positioned at the beginning.
func (*CellIndexRangeIterator) Seek ¶
func (c *CellIndexRangeIterator) Seek(target CellID)
Seek positions the iterator at the first range with startID >= target. Such an entry always exists as long as "target" is a valid leaf cell.
Note that it is valid to access startID even when done is true.
func (*CellIndexRangeIterator) StartID ¶
func (c *CellIndexRangeIterator) StartID() CellID
StartID reports the CellID of the start of the current range of leaf CellIDs.
If done is true, this returns the last possible CellID. This property means that most loops do not need to test done explicitly.
type CellRelation ¶
type CellRelation int
CellRelation describes the possible relationships between a target cell and the cells of the ShapeIndex. If the target is an index cell or is contained by an index cell, it is Indexed. If the target is subdivided into one or more index cells, it is Subdivided. Otherwise it is Disjoint.
const ( Indexed CellRelation = iota Subdivided Disjoint )
The possible CellRelations for a ShapeIndex.
type CellUnion ¶
type CellUnion []CellID
A CellUnion is a collection of CellIDs.
It is normalized if it is sorted, and does not contain redundancy. Specifically, it may not contain the same CellID twice, nor a CellID that is contained by another, nor the four sibling CellIDs that are children of a single higher level CellID.
CellUnions are not required to be normalized, but certain operations will return different results if they are not (e.g. Contains).
func CellUnionFromDifference ¶
CellUnionFromDifference creates a CellUnion from the difference (x  y) of the given CellUnions.
func CellUnionFromIntersection ¶
CellUnionFromIntersection creates a CellUnion from the intersection of the given CellUnions.
func CellUnionFromIntersectionWithCellID ¶
CellUnionFromIntersectionWithCellID creates a CellUnion from the intersection of a CellUnion with the given CellID. This can be useful for splitting a CellUnion into chunks.
func CellUnionFromRange ¶
CellUnionFromRange creates a CellUnion that covers the halfopen range of leaf cells [begin, end). If begin == end the resulting union is empty. This requires that begin and end are both leaves, and begin <= end. To create a closedended range, pass in end.Next().
func CellUnionFromUnion ¶
CellUnionFromUnion creates a CellUnion from the union of the given CellUnions.
func (*CellUnion) ApproxArea ¶
ApproxArea returns the approximate area of this CellUnion. This method is accurate to within 3% percent for all cell sizes and accurate to within 0.1% for cells at level 5 or higher within the union.
func (*CellUnion) AverageArea ¶
AverageArea returns the average area of this CellUnion. This is accurate to within a factor of 1.7.
func (*CellUnion) CellUnionBound ¶
CellUnionBound computes a covering of the CellUnion.
func (*CellUnion) Contains ¶
Contains reports whether this CellUnion contains all of the CellIDs of the given CellUnion.
func (*CellUnion) ContainsCell ¶
ContainsCell reports whether this cell union contains the given cell.
func (*CellUnion) ContainsCellID ¶
ContainsCellID reports whether the CellUnion contains the given cell ID. Containment is defined with respect to regions, e.g. a cell contains its 4 children.
CAVEAT: If you have constructed a nonnormalized CellUnion, note that groups of 4 child cells are *not* considered to contain their parent cell. To get this behavior you must use one of the call Normalize() explicitly.
func (*CellUnion) ContainsPoint ¶
ContainsPoint reports whether this cell union contains the given point.
func (*CellUnion) Denormalize ¶
Denormalize replaces this CellUnion with an expanded version of the CellUnion where any cell whose level is less than minLevel or where (level  minLevel) is not a multiple of levelMod is replaced by its children, until either both of these conditions are satisfied or the maximum level is reached.
func (*CellUnion) ExactArea ¶
ExactArea returns the area of this CellUnion as accurately as possible.
func (*CellUnion) ExpandAtLevel ¶
ExpandAtLevel expands this CellUnion by adding a rim of cells at expandLevel around the unions boundary.
For each cell c in the union, we add all cells at level expandLevel that abut c. There are typically eight of those (four edgeabutting and four sharing a vertex). However, if c is finer than expandLevel, we add all cells abutting c.Parent(expandLevel) as well as c.Parent(expandLevel) itself, as an expandLevel cell rarely abuts a smaller cell.
Note that the size of the output is exponential in expandLevel. For example, if expandLevel == 20 and the input has a cell at level 10, there will be on the order of 4000 adjacent cells in the output. For most applications the ExpandByRadius method below is easier to use.
func (*CellUnion) ExpandByRadius ¶
ExpandByRadius expands this CellUnion such that it contains all points whose distance to the CellUnion is at most minRadius, but do not use cells that are more than maxLevelDiff levels higher than the largest cell in the input. The second parameter controls the tradeoff between accuracy and output size when a large region is being expanded by a small amount (e.g. expanding Canada by 1km). For example, if maxLevelDiff == 4 the region will always be expanded by approximately 1/16 the width of its largest cell. Note that in the worst case, the number of cells in the output can be up to 4 * (1 + 2 ** maxLevelDiff) times larger than the number of cells in the input.
func (*CellUnion) Intersects ¶
Intersects reports whether this CellUnion intersects any of the CellIDs of the given CellUnion.
func (*CellUnion) IntersectsCell ¶
IntersectsCell reports whether this cell union intersects the given cell.
func (*CellUnion) IntersectsCellID ¶
IntersectsCellID reports whether this CellUnion intersects the given cell ID.
func (*CellUnion) IsNormalized ¶
IsNormalized reports whether the cell union is normalized, meaning that it is satisfies IsValid and that no four cells have a common parent. Certain operations such as Contains will return a different result if the cell union is not normalized.
func (*CellUnion) IsValid ¶
IsValid reports whether the cell union is valid, meaning that the CellIDs are valid, nonoverlapping, and sorted in increasing order.
func (*CellUnion) LeafCellsCovered ¶
LeafCellsCovered reports the number of leaf cells covered by this cell union. This will be no more than 6*2^60 for the whole sphere.
type Chain ¶
type Chain struct {
Start, Length int
}
Chain represents a range of edge IDs corresponding to a chain of connected edges, specified as a (start, length) pair. The chain is defined to consist of edge IDs {start, start + 1, ..., start + length  1}.
type ChainPosition ¶
type ChainPosition struct {
ChainID, Offset int
}
ChainPosition represents the position of an edge within a given edge chain, specified as a (chainID, offset) pair. Chains are numbered sequentially starting from zero, and offsets are measured from the start of each chain.
type ContainsPointQuery ¶
type ContainsPointQuery struct {
// contains filtered or unexported fields
}
ContainsPointQuery determines whether one or more shapes in a ShapeIndex contain a given Point. The ShapeIndex may contain any number of points, polylines, and/or polygons (possibly overlapping). Shape boundaries may be modeled as Open, SemiOpen, or Closed (this affects whether or not shapes are considered to contain their vertices).
This type is not safe for concurrent use.
However, note that if you need to do a large number of point containment tests, it is more efficient to reuse the query rather than creating a new one each time.
func NewContainsPointQuery ¶
func NewContainsPointQuery(index *ShapeIndex, model VertexModel) *ContainsPointQuery
NewContainsPointQuery creates a new instance of the ContainsPointQuery for the index and given vertex model choice.
func (*ContainsPointQuery) ContainingShapes ¶
func (q *ContainsPointQuery) ContainingShapes(p Point) []Shape
ContainingShapes returns a slice of all shapes that contain the given point.
func (*ContainsPointQuery) Contains ¶
func (q *ContainsPointQuery) Contains(p Point) bool
Contains reports whether any shape in the queries index contains the point p under the queries vertex model (Open, SemiOpen, or Closed).
func (*ContainsPointQuery) ShapeContains ¶
func (q *ContainsPointQuery) ShapeContains(shape Shape, p Point) bool
ShapeContains reports whether the given shape contains the point under this queries vertex model (Open, SemiOpen, or Closed).
This requires the shape belongs to this queries index.
type ContainsVertexQuery ¶
type ContainsVertexQuery struct {
// contains filtered or unexported fields
}
ContainsVertexQuery is used to track the edges entering and leaving the given vertex of a Polygon in order to be able to determine if the point is contained by the Polygon.
Point containment is defined according to the semiopen boundary model which means that if several polygons tile the region around a vertex, then exactly one of those polygons contains that vertex.
func NewContainsVertexQuery ¶
func NewContainsVertexQuery(target Point) *ContainsVertexQuery
NewContainsVertexQuery returns a new query for the given vertex whose containment will be determined.
func (*ContainsVertexQuery) AddEdge ¶
func (q *ContainsVertexQuery) AddEdge(v Point, direction int)
AddEdge adds the edge between target and v with the given direction. (+1 = outgoing, 1 = incoming, 0 = degenerate).
func (*ContainsVertexQuery) ContainsVertex ¶
func (q *ContainsVertexQuery) ContainsVertex() int
ContainsVertex reports a +1 if the target vertex is contained, 1 if it is not contained, and 0 if the incident edges consisted of matched sibling pairs.
type ConvexHullQuery ¶
type ConvexHullQuery struct {
// contains filtered or unexported fields
}
ConvexHullQuery builds the convex hull of any collection of points, polylines, loops, and polygons. It returns a single convex loop.
The convex hull is defined as the smallest convex region on the sphere that contains all of your input geometry. Recall that a region is "convex" if for every pair of points inside the region, the straight edge between them is also inside the region. In our case, a "straight" edge is a geodesic, i.e. the shortest path on the sphere between two points.
Containment of input geometry is defined as follows:
Each input loop and polygon is contained by the convex hull exactly (i.e., according to Polygon's Contains(Polygon)).
Each input point is either contained by the convex hull or is a vertex of the convex hull. (Recall that S2Loops do not necessarily contain their vertices.)
For each input polyline, the convex hull contains all of its vertices according to the rule for points above. (The definition of convexity then ensures that the convex hull also contains the polyline edges.)
To use this type, call the various Add... methods to add your input geometry, and then call ConvexHull. Note that ConvexHull does *not* reset the state; you can continue adding geometry if desired and compute the convex hull again. If you want to start from scratch, simply create a new ConvexHullQuery value.
This implement Andrew's monotone chain algorithm, which is a variant of the Graham scan (see https://en.wikipedia.org/wiki/Graham_scan). The time complexity is O(n log n), and the space required is O(n). In fact only the call to "sort" takes O(n log n) time; the rest of the algorithm is linear.
Demonstration of the algorithm and code: en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
This type is not safe for concurrent use.
func NewConvexHullQuery ¶
func NewConvexHullQuery() *ConvexHullQuery
NewConvexHullQuery creates a new ConvexHullQuery.
func (*ConvexHullQuery) AddLoop ¶
func (q *ConvexHullQuery) AddLoop(l *Loop)
AddLoop adds the given loop to the input geometry.
func (*ConvexHullQuery) AddPoint ¶
func (q *ConvexHullQuery) AddPoint(p Point)
AddPoint adds the given point to the input geometry.
func (*ConvexHullQuery) AddPolygon ¶
func (q *ConvexHullQuery) AddPolygon(p *Polygon)
AddPolygon adds the given polygon to the input geometry.
func (*ConvexHullQuery) AddPolyline ¶
func (q *ConvexHullQuery) AddPolyline(p *Polyline)
AddPolyline adds the given polyline to the input geometry.
func (*ConvexHullQuery) CapBound ¶
func (q *ConvexHullQuery) CapBound() Cap
CapBound returns a bounding cap for the input geometry provided.
Note that this method does not clear the geometry; you can continue adding to it and call this method again if desired.
func (*ConvexHullQuery) ConvexHull ¶
func (q *ConvexHullQuery) ConvexHull() *Loop
ConvexHull returns a Loop representing the convex hull of the input geometry provided.
If there is no geometry, this method returns an empty loop containing no points.
If the geometry spans more than half of the sphere, this method returns a full loop containing the entire sphere.
If the geometry contains 1 or 2 points, or a single edge, this method returns a very small loop consisting of three vertices (which are a superset of the input vertices).
Note that this method does not clear the geometry; you can continue adding to the query and call this method again.
type Crossing ¶
type Crossing int
A Crossing indicates how edges cross.
func CrossingSign ¶
CrossingSign reports whether the edge AB intersects the edge CD. If AB crosses CD at a point that is interior to both edges, Cross is returned. If any two vertices from different edges are the same it returns MaybeCross. Otherwise it returns DoNotCross. If either edge is degenerate (A == B or C == D), the return value is MaybeCross if two vertices from different edges are the same and DoNotCross otherwise.
Properties of CrossingSign:
(1) CrossingSign(b,a,c,d) == CrossingSign(a,b,c,d) (2) CrossingSign(c,d,a,b) == CrossingSign(a,b,c,d) (3) CrossingSign(a,b,c,d) == MaybeCross if a==c, a==d, b==c, b==d (3) CrossingSign(a,b,c,d) == DoNotCross or MaybeCross if a==b or c==d
This method implements an exact, consistent perturbation model such that no three points are ever considered to be collinear. This means that even if you have 4 points A, B, C, D that lie exactly in a line (say, around the equator), C and D will be treated as being slightly to one side or the other of AB. This is done in a way such that the results are always consistent (see RobustSign).
type CrossingEdgeQuery ¶
type CrossingEdgeQuery struct {
// contains filtered or unexported fields
}
CrossingEdgeQuery is used to find the Edge IDs of Shapes that are crossed by a given edge(s).
Note that if you need to query many edges, it is more efficient to declare a single CrossingEdgeQuery instance and reuse it.
If you want to find *all* the pairs of crossing edges, it is more efficient to use the not yet implemented VisitCrossings in shapeutil.
func NewCrossingEdgeQuery ¶
func NewCrossingEdgeQuery(index *ShapeIndex) *CrossingEdgeQuery
NewCrossingEdgeQuery creates a CrossingEdgeQuery for the given index.
func (*CrossingEdgeQuery) Crossings ¶
func (c *CrossingEdgeQuery) Crossings(a, b Point, shape Shape, crossType CrossingType) []int
Crossings returns the set of edge of the shape S that intersect the given edge AB. If the CrossingType is Interior, then only intersections at a point interior to both edges are reported, while if it is CrossingTypeAll then edges that share a vertex are also reported.
func (*CrossingEdgeQuery) CrossingsEdgeMap ¶
func (c *CrossingEdgeQuery) CrossingsEdgeMap(a, b Point, crossType CrossingType) EdgeMap
CrossingsEdgeMap returns the set of all edges in the index that intersect the given edge AB. If crossType is CrossingTypeInterior, then only intersections at a point interior to both edges are reported, while if it is CrossingTypeAll then edges that share a vertex are also reported.
The edges are returned as a mapping from shape to the edges of that shape that intersect AB. Every returned shape has at least one crossing edge.
type CrossingType ¶
type CrossingType int
CrossingType defines different ways of reporting edge intersections.
const ( // CrossingTypeInterior reports intersections that occur at a point // interior to both edges (i.e., not at a vertex). CrossingTypeInterior CrossingType = iota // CrossingTypeAll reports all intersections, even those where two edges // intersect only because they share a common vertex. CrossingTypeAll // CrossingTypeNonAdjacent reports all intersections except for pairs of // the form (AB, BC) where both edges are from the same ShapeIndex. CrossingTypeNonAdjacent )
type Direction ¶
type Direction int
Direction is an indication of the ordering of a set of points.
These are the three options for the direction of a set of points.
func RobustSign ¶
RobustSign returns a Direction representing the ordering of the points. CounterClockwise is returned if the points are in counterclockwise order, Clockwise for clockwise, and Indeterminate if any two points are the same (collinear), or the sign could not completely be determined.
This function has additional logic to make sure that the above properties hold even when the three points are coplanar, and to deal with the limitations of floatingpoint arithmetic.
RobustSign satisfies the following conditions:
(1) RobustSign(a,b,c) == Indeterminate if and only if a == b, b == c, or c == a (2) RobustSign(b,c,a) == RobustSign(a,b,c) for all a,b,c (3) RobustSign(c,b,a) == RobustSign(a,b,c) for all a,b,c
In other words:
(1) The result is Indeterminate if and only if two points are the same. (2) Rotating the order of the arguments does not affect the result. (3) Exchanging any two arguments inverts the result.
On the other hand, note that it is not true in general that RobustSign(a,b,c) == RobustSign(a,b,c), or any similar identities involving antipodal points.
type Edge ¶
type Edge struct {
V0, V1 Point
}
Edge represents a geodesic edge consisting of two vertices. Zerolength edges are allowed, and can be used to represent points.
type EdgeCrosser ¶
type EdgeCrosser struct {
// contains filtered or unexported fields
}
EdgeCrosser allows edges to be efficiently tested for intersection with a given fixed edge AB. It is especially efficient when testing for intersection with an edge chain connecting vertices v0, v1, v2, ...
Example usage:
func CountIntersections(a, b Point, edges []Edge) int { count := 0 crosser := NewEdgeCrosser(a, b) for _, edge := range edges { if crosser.CrossingSign(&edge.First, &edge.Second) != DoNotCross { count++ } } return count }
func NewChainEdgeCrosser ¶
func NewChainEdgeCrosser(a, b, c Point) *EdgeCrosser
NewChainEdgeCrosser is a convenience constructor that uses AB as the fixed edge, and C as the first vertex of the vertex chain (equivalent to calling RestartAt(c)).
You don't need to use this or any of the chain functions unless you're trying to squeeze out every last drop of performance. Essentially all you are saving is a test whether the first vertex of the current edge is the same as the second vertex of the previous edge.
func NewEdgeCrosser ¶
func NewEdgeCrosser(a, b Point) *EdgeCrosser
NewEdgeCrosser returns an EdgeCrosser with the fixed edge AB.
func (*EdgeCrosser) ChainCrossingSign ¶
func (e *EdgeCrosser) ChainCrossingSign(d Point) Crossing
ChainCrossingSign is like CrossingSign, but uses the last vertex passed to one of the crossing methods (or RestartAt) as the first vertex of the current edge.
func (*EdgeCrosser) CrossingSign ¶
func (e *EdgeCrosser) CrossingSign(c, d Point) Crossing
CrossingSign reports whether the edge AB intersects the edge CD. If any two vertices from different edges are the same, returns MaybeCross. If either edge is degenerate (A == B or C == D), returns either DoNotCross or MaybeCross.
Properties of CrossingSign:
(1) CrossingSign(b,a,c,d) == CrossingSign(a,b,c,d) (2) CrossingSign(c,d,a,b) == CrossingSign(a,b,c,d) (3) CrossingSign(a,b,c,d) == MaybeCross if a==c, a==d, b==c, b==d (3) CrossingSign(a,b,c,d) == DoNotCross or MaybeCross if a==b or c==d
Note that if you want to check an edge against a chain of other edges, it is slightly more efficient to use the singleargument version ChainCrossingSign below.
func (*EdgeCrosser) EdgeOrVertexChainCrossing ¶
func (e *EdgeCrosser) EdgeOrVertexChainCrossing(d Point) bool
EdgeOrVertexChainCrossing is like EdgeOrVertexCrossing, but uses the last vertex passed to one of the crossing methods (or RestartAt) as the first vertex of the current edge.
func (*EdgeCrosser) EdgeOrVertexCrossing ¶
func (e *EdgeCrosser) EdgeOrVertexCrossing(c, d Point) bool
EdgeOrVertexCrossing reports whether if CrossingSign(c, d) > 0, or AB and CD share a vertex and VertexCrossing(a, b, c, d) is true.
This method extends the concept of a "crossing" to the case where AB and CD have a vertex in common. The two edges may or may not cross, according to the rules defined in VertexCrossing above. The rules are designed so that point containment tests can be implemented simply by counting edge crossings. Similarly, determining whether one edge chain crosses another edge chain can be implemented by counting.
func (*EdgeCrosser) RestartAt ¶
func (e *EdgeCrosser) RestartAt(c Point)
RestartAt sets the current point of the edge crosser to be c. Call this method when your chain 'jumps' to a new place. The argument must point to a value that persists until the next call.
type EdgeIterator ¶
type EdgeIterator struct {
// contains filtered or unexported fields
}
EdgeIterator is an iterator that advances through all edges in an ShapeIndex. This is different to the ShapeIndexIterator, which advances through the cells in the ShapeIndex.
func NewEdgeIterator ¶
func NewEdgeIterator(index *ShapeIndex) *EdgeIterator
NewEdgeIterator creates a new edge iterator for the given index.
func (*EdgeIterator) Done ¶
func (e *EdgeIterator) Done() bool
Done reports if the iterator is positioned at or after the last index edge.
func (*EdgeIterator) EdgeID ¶
func (e *EdgeIterator) EdgeID() int32
EdgeID returns the current edge ID.
func (*EdgeIterator) Next ¶
func (e *EdgeIterator) Next()
Next positions the iterator at the next index edge.
func (*EdgeIterator) ShapeEdgeID ¶
func (e *EdgeIterator) ShapeEdgeID() ShapeEdgeID
ShapeEdgeID returns the current (shapeID, edgeID).
func (*EdgeIterator) ShapeID ¶
func (e *EdgeIterator) ShapeID() int32
ShapeID returns the current shape ID.
type EdgeQuery ¶
type EdgeQuery struct {
// contains filtered or unexported fields
}
EdgeQuery is used to find the edge(s) between two geometries that match a given set of options. It is flexible enough so that it can be adapted to compute maximum distances and even potentially Hausdorff distances.
By using the appropriate options, this type can answer questions such as:
 Find the minimum distance between two geometries A and B.
 Find all edges of geometry A that are within a distance D of geometry B.
 Find the k edges of geometry A that are closest to a given point P.
You can also specify whether polygons should include their interiors (i.e., if a point is contained by a polygon, should the distance be zero or should it be measured to the polygon boundary?)
The input geometries may consist of any number of points, polylines, and polygons (collectively referred to as "shapes"). Shapes do not need to be disjoint; they may overlap or intersect arbitrarily. The implementation is designed to be fast for both simple and complex geometries.
func NewClosestEdgeQuery ¶
func NewClosestEdgeQuery(index *ShapeIndex, opts *EdgeQueryOptions) *EdgeQuery
NewClosestEdgeQuery returns an EdgeQuery that is used for finding the closest edge(s) to a given Point, Edge, Cell, or geometry collection.
You can find either the k closest edges, or all edges within a given radius, or both (i.e., the k closest edges up to a given maximum radius). E.g. to find all the edges within 5 kilometers, set the DistanceLimit in the options.
By default *all* edges are returned, so you should always specify either MaxResults or DistanceLimit options or both.
Note that by default, distances are measured to the boundary and interior of polygons. For example, if a point is inside a polygon then its distance is zero. To change this behavior, set the IncludeInteriors option to false.
If you only need to test whether the distance is above or below a given threshold (e.g., 10 km), you can use the IsDistanceLess() method. This is much faster than actually calculating the distance with FindEdge, since the implementation can stop as soon as it can prove that the minimum distance is either above or below the threshold.
func NewFurthestEdgeQuery ¶
func NewFurthestEdgeQuery(index *ShapeIndex, opts *EdgeQueryOptions) *EdgeQuery
NewFurthestEdgeQuery returns an EdgeQuery that is used for finding the furthest edge(s) to a given Point, Edge, Cell, or geometry collection.
The furthest edge is defined as the one which maximizes the distance from any point on that edge to any point on the target geometry.
Similar to the example in NewClosestEdgeQuery, to find the 5 furthest edges from a given Point:
func (*EdgeQuery) Distance ¶
func (e *EdgeQuery) Distance(target distanceTarget) s1.ChordAngle
Distance reports the distance to the target. If the index or target is empty, returns the EdgeQuery's maximal sentinel.
Use IsDistanceLess()/IsDistanceGreater() if you only want to compare the distance against a threshold value, since it is often much faster.
func (*EdgeQuery) FindEdges ¶
func (e *EdgeQuery) FindEdges(target distanceTarget) []EdgeQueryResult
FindEdges returns the edges for the given target that satisfy the current options.
Note that if opts.IncludeInteriors is true, the results may include some entries with edge_id == 1. This indicates that the target intersects the indexed polygon with the given ShapeID.
Example (FindClosestEdges) ¶
package main import ( "fmt" "github.com/golang/geo/s2" ) func main() { // Let's start with one or more Polylines that we wish to compare against. polylines := []s2.Polyline{ // This is an iteration = 3 Koch snowflake centered at the // center of the continental US. s2.Polyline{ s2.PointFromLatLng(s2.LatLngFromDegrees(47.5467, 103.6035)), s2.PointFromLatLng(s2.LatLngFromDegrees(45.9214, 103.7320)), s2.PointFromLatLng(s2.LatLngFromDegrees(45.1527, 105.8000)), s2.PointFromLatLng(s2.LatLngFromDegrees(44.2866, 103.8538)), s2.PointFromLatLng(s2.LatLngFromDegrees(42.6450, 103.9695)), s2.PointFromLatLng(s2.LatLngFromDegrees(41.8743, 105.9314)), s2.PointFromLatLng(s2.LatLngFromDegrees(42.7141, 107.8226)), s2.PointFromLatLng(s2.LatLngFromDegrees(41.0743, 107.8377)), s2.PointFromLatLng(s2.LatLngFromDegrees(40.2486, 109.6869)), s2.PointFromLatLng(s2.LatLngFromDegrees(39.4333, 107.8521)), s2.PointFromLatLng(s2.LatLngFromDegrees(37.7936, 107.8658)), s2.PointFromLatLng(s2.LatLngFromDegrees(38.5849, 106.0503)), s2.PointFromLatLng(s2.LatLngFromDegrees(37.7058, 104.2841)), s2.PointFromLatLng(s2.LatLngFromDegrees(36.0638, 104.3793)), s2.PointFromLatLng(s2.LatLngFromDegrees(35.3062, 106.1585)), s2.PointFromLatLng(s2.LatLngFromDegrees(34.4284, 104.4703)), s2.PointFromLatLng(s2.LatLngFromDegrees(32.8024, 104.5573)), s2.PointFromLatLng(s2.LatLngFromDegrees(33.5273, 102.8163)), s2.PointFromLatLng(s2.LatLngFromDegrees(32.6053, 101.1982)), s2.PointFromLatLng(s2.LatLngFromDegrees(34.2313, 101.0361)), s2.PointFromLatLng(s2.LatLngFromDegrees(34.9120, 99.2189)), s2.PointFromLatLng(s2.LatLngFromDegrees(33.9382, 97.6134)), s2.PointFromLatLng(s2.LatLngFromDegrees(32.3185, 97.8489)), s2.PointFromLatLng(s2.LatLngFromDegrees(32.9481, 96.0510)), s2.PointFromLatLng(s2.LatLngFromDegrees(31.9449, 94.5321)), s2.PointFromLatLng(s2.LatLngFromDegrees(33.5521, 94.2263)), s2.PointFromLatLng(s2.LatLngFromDegrees(34.1285, 92.3780)), s2.PointFromLatLng(s2.LatLngFromDegrees(35.1678, 93.9070)), s2.PointFromLatLng(s2.LatLngFromDegrees(36.7893, 93.5734)), s2.PointFromLatLng(s2.LatLngFromDegrees(37.3529, 91.6381)), s2.PointFromLatLng(s2.LatLngFromDegrees(36.2777, 90.1050)), s2.PointFromLatLng(s2.LatLngFromDegrees(37.8824, 89.6824)), s2.PointFromLatLng(s2.LatLngFromDegrees(38.3764, 87.7108)), s2.PointFromLatLng(s2.LatLngFromDegrees(39.4869, 89.2407)), s2.PointFromLatLng(s2.LatLngFromDegrees(41.0883, 88.7784)), s2.PointFromLatLng(s2.LatLngFromDegrees(40.5829, 90.8289)), s2.PointFromLatLng(s2.LatLngFromDegrees(41.6608, 92.4765)), s2.PointFromLatLng(s2.LatLngFromDegrees(43.2777, 92.0749)), s2.PointFromLatLng(s2.LatLngFromDegrees(43.7961, 89.9408)), s2.PointFromLatLng(s2.LatLngFromDegrees(44.8865, 91.6533)), s2.PointFromLatLng(s2.LatLngFromDegrees(46.4844, 91.2100)), s2.PointFromLatLng(s2.LatLngFromDegrees(45.9512, 93.4327)), s2.PointFromLatLng(s2.LatLngFromDegrees(46.9863, 95.2792)), s2.PointFromLatLng(s2.LatLngFromDegrees(45.3722, 95.6237)), s2.PointFromLatLng(s2.LatLngFromDegrees(44.7496, 97.7776)), s2.PointFromLatLng(s2.LatLngFromDegrees(45.7189, 99.6629)), s2.PointFromLatLng(s2.LatLngFromDegrees(47.3422, 99.4244)), s2.PointFromLatLng(s2.LatLngFromDegrees(46.6523, 101.6056)), }, } // We will use a point that we wish to find the edges which are closest to it. point := s2.PointFromLatLng(s2.LatLngFromDegrees(37.7, 122.5)) // Load them into a ShapeIndex. index := s2.NewShapeIndex() for _, l := range polylines { index.Add(&l) } // Create a ClosestEdgeQuery and specify that we want the 7 closest. // // Note that if you were to request all results, and compare to the results // of a FurthestEdgeQuery, the results will not be a complete reversal. This // is because the distances being reported are to the closest end of a given // edge, while the Furthest query is reporting distances to the farthest end // of a given edge. q := s2.NewClosestEdgeQuery(index, s2.NewClosestEdgeQueryOptions().MaxResults(7)) target := s2.NewMinDistanceToPointTarget(point) for _, result := range q.FindEdges(target) { polylineIndex := result.ShapeID() edgeIndex := result.EdgeID() distance := result.Distance() fmt.Printf("Polyline %d, Edge %d is %0.4f degrees from Point (%0.6f, %0.6f, %0.6f)\n", polylineIndex, edgeIndex, distance.Angle().Degrees(), point.X, point.Y, point.Z) } }
Output: Polyline 0, Edge 7 is 10.2718 degrees from Point (0.425124, 0.667311, 0.611527) Polyline 0, Edge 8 is 10.2718 degrees from Point (0.425124, 0.667311, 0.611527) Polyline 0, Edge 9 is 11.5362 degrees from Point (0.425124, 0.667311, 0.611527) Polyline 0, Edge 10 is 11.5602 degrees from Point (0.425124, 0.667311, 0.611527) Polyline 0, Edge 6 is 11.8071 degrees from Point (0.425124, 0.667311, 0.611527) Polyline 0, Edge 5 is 12.2577 degrees from Point (0.425124, 0.667311, 0.611527) Polyline 0, Edge 11 is 12.9502 degrees from Point (0.425124, 0.667311, 0.611527)
Example (FindFurthestEdges) ¶
package main import ( "fmt" "github.com/golang/geo/s2" ) func main() { // Let's start with one or more Polylines that we wish to compare against. polylines := []s2.Polyline{ // This is an iteration = 3 Koch snowflake centered at the // center of the continental US. s2.Polyline{ s2.PointFromLatLng(s2.LatLngFromDegrees(47.5467, 103.6035)), s2.PointFromLatLng(s2.LatLngFromDegrees(45.9214, 103.7320)), s2.PointFromLatLng(s2.LatLngFromDegrees(45.1527, 105.8000)), s2.PointFromLatLng(s2.LatLngFromDegrees(44.2866, 103.8538)), s2.PointFromLatLng(s2.LatLngFromDegrees(42.6450, 103.9695)), s2.PointFromLatLng(s2.LatLngFromDegrees(41.8743, 105.9314)), s2.PointFromLatLng(s2.LatLngFromDegrees(42.7141, 107.8226)), s2.PointFromLatLng(s2.LatLngFromDegrees(41.0743, 107.8377)), s2.PointFromLatLng(s2.LatLngFromDegrees(40.2486, 109.6869)), s2.PointFromLatLng(s2.LatLngFromDegrees(39.4333, 107.8521)), s2.PointFromLatLng(s2.LatLngFromDegrees(37.7936, 107.8658)), s2.PointFromLatLng(s2.LatLngFromDegrees(38.5849, 106.0503)), s2.PointFromLatLng(s2.LatLngFromDegrees(37.7058, 104.2841)), s2.PointFromLatLng(s2.LatLngFromDegrees(36.0638, 104.3793)), s2.PointFromLatLng(s2.LatLngFromDegrees(35.3062, 106.1585)), s2.PointFromLatLng(s2.LatLngFromDegrees(34.4284, 104.4703)), s2.PointFromLatLng(s2.LatLngFromDegrees(32.8024, 104.5573)), s2.PointFromLatLng(s2.LatLngFromDegrees(33.5273, 102.8163)), s2.PointFromLatLng(s2.LatLngFromDegrees(32.6053, 101.1982)), s2.PointFromLatLng(s2.LatLngFromDegrees(34.2313, 101.0361)), s2.PointFromLatLng(s2.LatLngFromDegrees(34.9120, 99.2189)), s2.PointFromLatLng(s2.LatLngFromDegrees(33.9382, 97.6134)), s2.PointFromLatLng(s2.LatLngFromDegrees(32.3185, 97.8489)), s2.PointFromLatLng(s2.LatLngFromDegrees(32.9481, 96.0510)), s2.PointFromLatLng(s2.LatLngFromDegrees(31.9449, 94.5321)), s2.PointFromLatLng(s2.LatLngFromDegrees(33.5521, 94.2263)), s2.PointFromLatLng(s2.LatLngFromDegrees(34.1285, 92.3780)), s2.PointFromLatLng(s2.LatLngFromDegrees(35.1678, 93.9070)), s2.PointFromLatLng(s2.LatLngFromDegrees(36.7893, 93.5734)), s2.PointFromLatLng(s2.LatLngFromDegrees(37.3529, 91.6381)), s2.PointFromLatLng(s2.LatLngFromDegrees(36.2777, 90.1050)), s2.PointFromLatLng(s2.LatLngFromDegrees(37.8824, 89.6824)), s2.PointFromLatLng(s2.LatLngFromDegrees(38.3764, 87.7108)), s2.PointFromLatLng(s2.LatLngFromDegrees(39.4869, 89.2407)), s2.PointFromLatLng(s2.LatLngFromDegrees(41.0883, 88.7784)), s2.PointFromLatLng(s2.LatLngFromDegrees(40.5829, 90.8289)), s2.PointFromLatLng(s2.LatLngFromDegrees(41.6608, 92.4765)), s2.PointFromLatLng(s2.LatLngFromDegrees(43.2777, 92.0749)), s2.PointFromLatLng(s2.LatLngFromDegrees(43.7961, 89.9408)), s2.PointFromLatLng(s2.LatLngFromDegrees(44.8865, 91.6533)), s2.PointFromLatLng(s2.LatLngFromDegrees(46.4844, 91.2100)), s2.PointFromLatLng(s2.LatLngFromDegrees(45.9512, 93.4327)), s2.PointFromLatLng(s2.LatLngFromDegrees(46.9863, 95.2792)), s2.PointFromLatLng(s2.LatLngFromDegrees(45.3722, 95.6237)), s2.PointFromLatLng(s2.LatLngFromDegrees(44.7496, 97.7776)), s2.PointFromLatLng(s2.LatLngFromDegrees(45.7189, 99.6629)), s2.PointFromLatLng(s2.LatLngFromDegrees(47.3422, 99.4244)), s2.PointFromLatLng(s2.LatLngFromDegrees(46.6523, 101.6056)), }, } // We will use a point that we want to find the edges which are furthest from it. point := s2.PointFromLatLng(s2.LatLngFromDegrees(37.7, 122.5)) // Load them into a ShapeIndex index := s2.NewShapeIndex() for _, l := range polylines { index.Add(&l) } // Create a FurthestEdgeQuery and specify that we want the 3 furthest. q := s2.NewFurthestEdgeQuery(index, s2.NewFurthestEdgeQueryOptions().MaxResults(3)) target := s2.NewMaxDistanceToPointTarget(point) for _, result := range q.FindEdges(target) { polylineIndex := result.ShapeID() edgeIndex := result.EdgeID() distance := result.Distance() fmt.Printf("Polyline %d, Edge %d is %0.3f degrees from Point (%0.6f, %0.6f, %0.6f)\n", polylineIndex, edgeIndex, distance.Angle().Degrees(), point.X, point.Y, point.Z) } }
Output: Polyline 0, Edge 31 is 27.245 degrees from Point (0.425124, 0.667311, 0.611527) Polyline 0, Edge 32 is 27.245 degrees from Point (0.425124, 0.667311, 0.611527) Polyline 0, Edge 33 is 26.115 degrees from Point (0.425124, 0.667311, 0.611527)
func (*EdgeQuery) IsConservativeDistanceGreaterOrEqual ¶
func (e *EdgeQuery) IsConservativeDistanceGreaterOrEqual(target distanceTarget, limit s1.ChordAngle) bool
IsConservativeDistanceGreaterOrEqual reports if the distance to the target is greater than or equal to the given limit with some small tolerance.
func (*EdgeQuery) IsConservativeDistanceLessOrEqual ¶
func (e *EdgeQuery) IsConservativeDistanceLessOrEqual(target distanceTarget, limit s1.ChordAngle) bool
IsConservativeDistanceLessOrEqual reports if the distance to target is less or equal to the limit, where the limit has been expanded by the maximum error for the distance calculation.
For example, suppose that we want to test whether two geometries might intersect each other after they are snapped together using Builder (using the IdentitySnapFunction with a given "snap radius"). Since Builder uses exact distance predicates (s2predicates), we need to measure the distance between the two geometries conservatively. If the distance is definitely greater than "snap radius", then the geometries are guaranteed to not intersect after snapping.
func (*EdgeQuery) IsDistanceGreater ¶
func (e *EdgeQuery) IsDistanceGreater(target distanceTarget, limit s1.ChordAngle) bool
IsDistanceGreater reports if the distance to target is greater than limit.
This method is usually much faster than Distance, since it is much less work to determine whether the maximum distance is above or below a threshold than it is to calculate the actual maximum distance. If you wish to check if the distance is less than or equal to the limit, use:
query.IsDistanceGreater(target, limit.Predecessor())
func (*EdgeQuery) IsDistanceLess ¶
func (e *EdgeQuery) IsDistanceLess(target distanceTarget, limit s1.ChordAngle) bool
IsDistanceLess reports if the distance to target is less than the given limit.
This method is usually much faster than Distance(), since it is much less work to determine whether the minimum distance is above or below a threshold than it is to calculate the actual minimum distance.
If you wish to check if the distance is less than or equal to the limit, use:
query.IsDistanceLess(target, limit.Successor())
type EdgeQueryOptions ¶
type EdgeQueryOptions struct {
// contains filtered or unexported fields
}
EdgeQueryOptions holds the options for controlling how EdgeQuery operates.
Options can be chained together builderstyle:
opts = NewClosestEdgeQueryOptions(). MaxResults(1). DistanceLimit(s1.ChordAngleFromAngle(3 * s1.Degree)). MaxError(s1.ChordAngleFromAngle(0.001 * s1.Degree)) query = NewClosestEdgeQuery(index, opts) or set individually: opts = NewClosestEdgeQueryOptions() opts.IncludeInteriors(true)
or just inline:
query = NewClosestEdgeQuery(index, NewClosestEdgeQueryOptions().MaxResults(3))
If you pass a nil as the options you get the default values for the options.
func NewClosestEdgeQueryOptions ¶
func NewClosestEdgeQueryOptions() *EdgeQueryOptions
NewClosestEdgeQueryOptions returns a set of edge query options suitable for performing closest edge queries.
func NewFurthestEdgeQueryOptions ¶
func NewFurthestEdgeQueryOptions() *EdgeQueryOptions
NewFurthestEdgeQueryOptions returns a set of edge query options suitable for performing furthest edge queries.
func (*EdgeQueryOptions) DistanceLimit ¶
func (e *EdgeQueryOptions) DistanceLimit(limit s1.ChordAngle) *EdgeQueryOptions
DistanceLimit specifies that only edges whose distance to the target is within, this distance should be returned. Edges whose distance is equal are not returned. To include values that are equal, specify the limit with the next largest representable distance. i.e. limit.Successor().
func (*EdgeQueryOptions) IncludeInteriors ¶
func (e *EdgeQueryOptions) IncludeInteriors(x bool) *EdgeQueryOptions
IncludeInteriors specifies whether polygon interiors should be included when measuring distances.
func (*EdgeQueryOptions) MaxError ¶
func (e *EdgeQueryOptions) MaxError(dist s1.ChordAngle) *EdgeQueryOptions
MaxError specifies that edges up to dist away than the true matching edges may be substituted in the result set, as long as such edges satisfy all the remaining search criteria (such as DistanceLimit). This option only has an effect if MaxResults is also specified; otherwise all edges closer than MaxDistance will always be returned.
func (*EdgeQueryOptions) MaxResults ¶
func (e *EdgeQueryOptions) MaxResults(n int) *EdgeQueryOptions
MaxResults specifies that at most MaxResults edges should be returned. This must be at least 1.
func (*EdgeQueryOptions) UseBruteForce ¶
func (e *EdgeQueryOptions) UseBruteForce(x bool) *EdgeQueryOptions
UseBruteForce sets or disables the use of brute force in a query.
type EdgeQueryResult ¶
type EdgeQueryResult struct {
// contains filtered or unexported fields
}
EdgeQueryResult represents an edge that meets the target criteria for the query. Note the following special cases:
ShapeID >= 0 && EdgeID < 0 represents the interior of a shape. Such results may be returned when the option IncludeInteriors is true.
ShapeID < 0 && EdgeID < 0 is returned to indicate that no edge satisfies the requested query options.
func (EdgeQueryResult) Distance ¶
func (e EdgeQueryResult) Distance() s1.ChordAngle
Distance reports the distance between the edge in this shape that satisfied the query's parameters.
func (EdgeQueryResult) EdgeID ¶
func (e EdgeQueryResult) EdgeID() int32
EdgeID reports the ID of the edge in the results Shape.
func (EdgeQueryResult) IsEmpty ¶
func (e EdgeQueryResult) IsEmpty() bool
IsEmpty reports if this has no edge that satisfies the given edge query options. This result is only returned in one special case, namely when FindEdge() does not find any suitable edges.
func (EdgeQueryResult) IsInterior ¶
func (e EdgeQueryResult) IsInterior() bool
IsInterior reports if this result represents the interior of a Shape.
func (EdgeQueryResult) Less ¶
func (e EdgeQueryResult) Less(other EdgeQueryResult) bool
Less reports if this results is less that the other first by distance, then by (shapeID, edgeID). This is used for sorting.
func (EdgeQueryResult) ShapeID ¶
func (e EdgeQueryResult) ShapeID() int32
ShapeID reports the ID of the Shape this result is for.
type EdgeTessellator ¶
type EdgeTessellator struct {
// contains filtered or unexported fields
}
EdgeTessellator converts an edge in a given projection (e.g., Mercator) into a chain of spherical geodesic edges such that the maximum distance between the original edge and the geodesic edge chain is at most the requested tolerance. Similarly, it can convert a spherical geodesic edge into a chain of edges in a given 2D projection such that the maximum distance between the geodesic edge and the chain of projected edges is at most the requested tolerance.
Method  Input  Output  Projected  S2 geodesics  Planar projected edges Unprojected  Planar projected edges  S2 geodesics
func NewEdgeTessellator ¶
func NewEdgeTessellator(p Projection, tolerance s1.Angle) *EdgeTessellator
NewEdgeTessellator creates a new edge tessellator for the given projection and tolerance.
func (*EdgeTessellator) AppendProjected ¶
AppendProjected converts the spherical geodesic edge AB to a chain of planar edges in the given projection and returns the corresponding vertices.
If the given projection has one or more coordinate axes that wrap, then every vertex's coordinates will be as close as possible to the previous vertex's coordinates. Note that this may yield vertices whose coordinates are outside the usual range. For example, tessellating the edge (0:170, 0:170) (in lat:lng notation) yields (0:170, 0:190).
func (*EdgeTessellator) AppendUnprojected ¶
func (e *EdgeTessellator) AppendUnprojected(pa, pb r2.Point, vertices []Point) []Point
AppendUnprojected converts the planar edge AB in the given projection to a chain of spherical geodesic edges and returns the vertices.
Note that to construct a Loop, you must eliminate the duplicate first and last vertex. Note also that if the given projection involves coordinate wrapping (e.g. across the 180 degree meridian) then the first and last vertices may not be exactly the same.
type FaceSegment ¶
type FaceSegment struct {
// contains filtered or unexported fields
}
FaceSegment represents an edge AB clipped to an S2 cube face. It is represented by a face index and a pair of (u,v) coordinates.
func FaceSegments ¶
func FaceSegments(a, b Point) []FaceSegment
FaceSegments subdivides the given edge AB at every point where it crosses the boundary between two S2 cube faces and returns the corresponding FaceSegments. The segments are returned in order from A toward B. The input points must be unit length.
This function guarantees that the returned segments form a continuous path from A to B, and that all vertices are within faceClipErrorUVDist of the line AB. All vertices lie within the [1,1]x[1,1] cube face rectangles. The results are consistent with Sign, i.e. the edge is welldefined even its endpoints are antipodal. TODO(roberts): Extend the implementation of PointCross so that this is true.
type IdentitySnapper ¶
type IdentitySnapper struct {
// contains filtered or unexported fields
}
IdentitySnapper is a Snapper that snaps every vertex to itself. It should be used when vertices do not need to be snapped to a discrete set of locations (such as E7 lat/lngs), or when maximum accuracy is desired.
If the snapRadius is zero, then all input vertices are preserved exactly. Otherwise, Builder merges nearby vertices to ensure that no vertex pair is closer than snapRadius. Furthermore, vertices are separated from nonincident edges by at least MinEdgeVertexSeparation, equal to (0.5 * snapRadius). For example, if the snapRadius is 1km, then vertices will be separated from nonincident edges by at least 500m.
func NewIdentitySnapper ¶
func NewIdentitySnapper(snapRadius s1.Angle) IdentitySnapper
NewIdentitySnapper returns an IdentitySnapper with the given snap radius.
func (IdentitySnapper) MaxEdgeDeviation ¶
func (sf IdentitySnapper) MaxEdgeDeviation() s1.Angle
MaxEdgeDeviation returns the maximum edge deviation this type supports.
func (IdentitySnapper) MinEdgeVertexSeparation ¶
func (sf IdentitySnapper) MinEdgeVertexSeparation() s1.Angle
MinEdgeVertexSeparation returns the minimum edge vertex separation. For the identity snap function, edges are separated from all nonincident vertices by at least 0.5 * snapRadius.
func (IdentitySnapper) MinVertexSeparation ¶
func (sf IdentitySnapper) MinVertexSeparation() s1.Angle
MinVertexSeparation returns the minimum vertex separation for this snap type.
func (IdentitySnapper) SnapPoint ¶
func (sf IdentitySnapper) SnapPoint(point Point) Point
SnapPoint snaps the given point to the appropriate level for this type.
func (IdentitySnapper) SnapRadius ¶
func (sf IdentitySnapper) SnapRadius() s1.Angle
SnapRadius returns this types snapping radius.
type IntLatLngSnapper ¶
type IntLatLngSnapper struct {
// contains filtered or unexported fields
}
IntLatLngSnapper is a Snapper that snaps vertices to LatLngs in E5, E6, or E7 coordinates. These coordinates are expressed in degrees multiplied by a power of 10 and then rounded to the nearest integer. For example, in E6 coordinates the point (23.12345651, 45.65432149) would become (23123457, 45654321).
Each exponent has a corresponding minimum snap radius, which is simply the maximum distance that a vertex can move when snapped. It is approximately equal to 1/sqrt(2) times the nominal point spacing; for example, for snapping to E7 the minimum snap radius is (1e7 / sqrt(2)) degrees. You can also set the snap radius to any value larger than this; this can result in significant extra simplification (similar to using a larger exponent) but does not move vertices unnecessarily.
func NewIntLatLngSnapper ¶
func NewIntLatLngSnapper(exponent int) IntLatLngSnapper
NewIntLatLngSnapper returns a Snapper with the specified exponent.
func (IntLatLngSnapper) MaxEdgeDeviation ¶
func (sf IntLatLngSnapper) MaxEdgeDeviation() s1.Angle
MaxEdgeDeviation returns the maximum edge deviation this type supports.
func (IntLatLngSnapper) MinEdgeVertexSeparation ¶
func (sf IntLatLngSnapper) MinEdgeVertexSeparation() s1.Angle
MinEdgeVertexSeparation returns the guaranteed minimum spacing between edges and nonincident vertices in the output. For IntLatLng snapping, the minimum separation between edges and nonincident vertices depends on level and snapRadius. It can be as low as 0.222 * snapRadius, but is typically 0.39 * snapRadius or more.
func (IntLatLngSnapper) MinVertexSeparation ¶
func (sf IntLatLngSnapper) MinVertexSeparation() s1.Angle
MinVertexSeparation returns the guaranteed minimum distance between vertices in the output. For IntLatLng snapping, the minimum separation between vertices depends on exponent and snapRadius.
func (IntLatLngSnapper) SnapPoint ¶
func (sf IntLatLngSnapper) SnapPoint(point Point) Point
SnapPoint returns a candidate snap site for the given point.
func (IntLatLngSnapper) SnapRadius ¶
func (sf IntLatLngSnapper) SnapRadius() s1.Angle
SnapRadius reports the snap radius to be used. The snap radius must be at least the minimum value for the current exponent, but larger values can also be used (e.g., to simplify the geometry).
This requires snapRadius >= minSnapRadiusForExponent(sh.exponent) and snapRadius <= maxSnapRadius
type LatLng ¶
LatLng represents a point on the unit sphere as a pair of angles.
func LatLngFromDegrees ¶
LatLngFromDegrees returns a LatLng for the coordinates given in degrees.
func LatLngFromPoint ¶
LatLngFromPoint returns an LatLng for a given Point.
func (LatLng) ApproxEqual ¶
ApproxEqual reports whether the latitude and longitude of the two LatLngs are the same up to a small tolerance.
func (LatLng) IsValid ¶
IsValid returns true iff the LatLng is normalized, with Lat ∈ [π/2,π/2] and Lng ∈ [π,π].
func (LatLng) Normalized ¶
Normalized returns the normalized version of the LatLng, with Lat clamped to [π/2,π/2] and Lng wrapped in [π,π].
type LaxLoop ¶
type LaxLoop struct {
// contains filtered or unexported fields
}
LaxLoop represents a closed loop of edges surrounding an interior region. It is similar to Loop except that this class allows duplicate vertices and edges. Loops may have any number of vertices, including 0, 1, or 2. (A onevertex loop defines a degenerate edge consisting of a single point.)
Note that LaxLoop is faster to initialize and more compact than Loop, but does not support the same operations as Loop.
func LaxLoopFromLoop ¶
LaxLoopFromLoop creates a LaxLoop from the given Loop, copying its points.
func LaxLoopFromPoints ¶
LaxLoopFromPoints creates a LaxLoop from the given points.
func (*LaxLoop) ChainPosition ¶
func (l *LaxLoop) ChainPosition(e int) ChainPosition
func (*LaxLoop) ReferencePoint ¶
func (l *LaxLoop) ReferencePoint() ReferencePoint
type LaxPolygon ¶
type LaxPolygon struct {
// contains filtered or unexported fields
}
LaxPolygon represents a region defined by a collection of zero or more closed loops. The interior is the region to the left of all loops. This is similar to Polygon except that this class supports polygons with degeneracies. Degeneracies are of two types: degenerate edges (from a vertex to itself) and sibling edge pairs (consisting of two oppositely oriented edges). Degeneracies can represent either "shells" or "holes" depending on the loop they are contained by. For example, a degenerate edge or sibling pair contained by a "shell" would be interpreted as a degenerate hole. Such edges form part of the boundary of the polygon.
Loops with fewer than three vertices are interpreted as follows:  A loop with two vertices defines two edges (in opposite directions).  A loop with one vertex defines a single degenerate edge.  A loop with no vertices is interpreted as the "full loop" containing
all points on the sphere. If this loop is present, then all other loops must form degeneracies (i.e., degenerate edges or sibling pairs). For example, two loops {} and {X} would be interpreted as the full polygon with a degenerate singlepoint hole at X.
LaxPolygon does not have any error checking, and it is perfectly fine to create LaxPolygon objects that do not meet the requirements below (e.g., in order to analyze or fix those problems). However, LaxPolygons must satisfy some additional conditions in order to perform certain operations:
 In order to be valid for point containment tests, the polygon must
satisfy the "interior is on the left" rule. This means that there must not be any crossing edges, and if there are duplicate edges then all but at most one of them must belong to a sibling pair (i.e., the number of edges in opposite directions must differ by at most one).
 To be valid for polygon operations (BoundaryOperation), degenerate
edges and sibling pairs cannot coincide with any other edges. For example, the following situations are not allowed: {AA, AA} // degenerate edge coincides with another edge {AA, AB} // degenerate edge coincides with another edge {AB, BA, AB} // sibling pair coincides with another edge
Note that LaxPolygon is much faster to initialize and is more compact than Polygon, but unlike Polygon it does not have any builtin operations. Instead you should use ShapeIndex based operations such as BoundaryOperation, ClosestEdgeQuery, etc.
func LaxPolygonFromPoints ¶
func LaxPolygonFromPoints(loops [][]Point) *LaxPolygon
LaxPolygonFromPoints creates a LaxPolygon from the given points.
func LaxPolygonFromPolygon ¶
func LaxPolygonFromPolygon(p *Polygon) *LaxPolygon
LaxPolygonFromPolygon creates a LaxPolygon from the given Polygon.
func (*LaxPolygon) Chain ¶
func (p *LaxPolygon) Chain(i int) Chain
func (*LaxPolygon) ChainEdge ¶
func (p *LaxPolygon) ChainEdge(i, j int) Edge
func (*LaxPolygon) ChainPosition ¶
func (p *LaxPolygon) ChainPosition(e int) ChainPosition
func (*LaxPolygon) Dimension ¶
func (p *LaxPolygon) Dimension() int
func (*LaxPolygon) Edge ¶
func (p *LaxPolygon) Edge(e int) Edge
func (*LaxPolygon) IsEmpty ¶
func (p *LaxPolygon) IsEmpty() bool
func (*LaxPolygon) IsFull ¶
func (p *LaxPolygon) IsFull() bool
func (*LaxPolygon) NumChains ¶
func (p *LaxPolygon) NumChains() int
func (*LaxPolygon) NumEdges ¶
func (p *LaxPolygon) NumEdges() int
func (*LaxPolygon) ReferencePoint ¶
func (p *LaxPolygon) ReferencePoint() ReferencePoint
type LaxPolyline ¶
type LaxPolyline struct {
// contains filtered or unexported fields
}
LaxPolyline represents a polyline. It is similar to Polyline except that adjacent vertices are allowed to be identical or antipodal, and the representation is slightly more compact.
Polylines may have any number of vertices, but note that polylines with fewer than 2 vertices do not define any edges. (To create a polyline consisting of a single degenerate edge, either repeat the same vertex twice or use LaxClosedPolyline.
func LaxPolylineFromPoints ¶
func LaxPolylineFromPoints(vertices []Point) *LaxPolyline
LaxPolylineFromPoints constructs a LaxPolyline from the given points.
func LaxPolylineFromPolyline ¶
func LaxPolylineFromPolyline(p Polyline) *LaxPolyline
LaxPolylineFromPolyline converts the given Polyline into a LaxPolyline.
func (*LaxPolyline) Chain ¶
func (l *LaxPolyline) Chain(i int) Chain
func (*LaxPolyline) ChainEdge ¶
func (l *LaxPolyline) ChainEdge(i, j int) Edge
func (*LaxPolyline) ChainPosition ¶
func (l *LaxPolyline) ChainPosition(e int) ChainPosition
func (*LaxPolyline) Dimension ¶
func (l *LaxPolyline) Dimension() int
func (*LaxPolyline) Edge ¶
func (l *LaxPolyline) Edge(e int) Edge
func (*LaxPolyline) IsEmpty ¶
func (l *LaxPolyline) IsEmpty() bool
func (*LaxPolyline) IsFull ¶
func (l *LaxPolyline) IsFull() bool
func (*LaxPolyline) NumChains ¶
func (l *LaxPolyline) NumChains() int
func (*LaxPolyline) NumEdges ¶
func (l *LaxPolyline) NumEdges() int
func (*LaxPolyline) ReferencePoint ¶
func (l *LaxPolyline) ReferencePoint() ReferencePoint
type Loop ¶
type Loop struct {
// contains filtered or unexported fields
}
Loop represents a simple spherical polygon. It consists of a sequence of vertices where the first vertex is implicitly connected to the last. All loops are defined to have a CCW orientation, i.e. the interior of the loop is on the left side of the edges. This implies that a clockwise loop enclosing a small area is interpreted to be a CCW loop enclosing a very large area.
Loops are not allowed to have any duplicate vertices (whether adjacent or not). Nonadjacent edges are not allowed to intersect, and furthermore edges of length 180 degrees are not allowed (i.e., adjacent vertices cannot be antipodal). Loops must have at least 3 vertices (except for the "empty" and "full" loops discussed below).
There are two special loops: the "empty" loop contains no points and the "full" loop contains all points. These loops do not have any edges, but to preserve the invariant that every loop can be represented as a vertex chain, they are defined as having exactly one vertex each (see EmptyLoop and FullLoop).
func LoopFromCell ¶
LoopFromCell constructs a loop corresponding to the given cell.
Note that the loop and cell *do not* contain exactly the same set of points, because Loop and Cell have slightly different definitions of point containment. For example, a Cell vertex is contained by all four neighboring Cells, but it is contained by exactly one of four Loops constructed from those cells. As another example, the cell coverings of cell and LoopFromCell(cell) will be different, because the loop contains points on its boundary that actually belong to other cells (i.e., the covering will include a layer of neighboring cells).
func LoopFromPoints ¶
LoopFromPoints constructs a loop from the given points.
func RegularLoop ¶
RegularLoop creates a loop with the given number of vertices, all located on a circle of the specified radius around the given center.
func RegularLoopForFrame ¶
RegularLoopForFrame creates a loop centered around the zaxis of the given coordinate frame, with the first vertex in the direction of the positive xaxis.
func (*Loop) Area ¶
Area returns the area of the loop interior, i.e. the region on the left side of the loop. The return value is between 0 and 4*pi. (Note that the return value is not affected by whether this loop is a "hole" or a "shell".)
func (*Loop) BoundaryEqual ¶
BoundaryEqual reports whether the two loops have the same boundary. This is true if and only if the loops have the same vertices in the same cyclic order (i.e., the vertices may be cyclically rotated). The empty and full loops are considered to have different boundaries.
func (*Loop) CanonicalFirstVertex ¶
CanonicalFirstVertex returns a first index and a direction (either +1 or 1) such that the vertex sequence (first, first+dir, ..., first+(n1)*dir) does not change when the loop vertex order is rotated or inverted. This allows the loop vertices to be traversed in a canonical order. The return values are chosen such that (first, ..., first+n*dir) are in the range [0, 2*n1] as expected by the Vertex method.
func (*Loop) CapBound ¶
CapBound returns a bounding cap that may have more padding than the corresponding RectBound. The bound is conservative such that if the loop contains a point P, the bound also contains it.
func (*Loop) CellUnionBound ¶
CellUnionBound computes a covering of the Loop.
func (*Loop) Centroid ¶
Centroid returns the true centroid of the loop multiplied by the area of the loop. The result is not unit length, so you may want to normalize it. Also note that in general, the centroid may not be contained by the loop.
We prescale by the loop area for two reasons: (1) it is cheaper to compute this way, and (2) it makes it easier to compute the centroid of more complicated shapes (by splitting them into disjoint regions and adding their centroids).
Note that the return value is not affected by whether this loop is a "hole" or a "shell".
func (*Loop) ChainPosition ¶
func (l *Loop) ChainPosition(edgeID int) ChainPosition
ChainPosition returns a ChainPosition pair (i, j) such that edgeID is the jth edge of the Loop.
func (*Loop) Contains ¶
Contains reports whether the region contained by this loop is a superset of the region contained by the given other loop.
func (*Loop) ContainsCell ¶
ContainsCell reports whether the given Cell is contained by this Loop.
func (*Loop) ContainsNested ¶
ContainsNested reports whether the given loops is contained within this loop. This function does not test for edge intersections. The two loops must meet all of the Polygon requirements; for example this implies that their boundaries may not cross or have any shared edges (although they may have shared vertices).
func (*Loop) ContainsOrigin ¶
ContainsOrigin reports true if this loop contains s2.OriginPoint().
func (*Loop) ContainsPoint ¶
ContainsPoint returns true if the loop contains the point.
func (*Loop) Equal ¶
Equal reports whether two loops have the same vertices in the same linear order (i.e., cyclic rotations are not allowed).
func (*Loop) Intersects ¶
Intersects reports whether the region contained by this loop intersects the region contained by the other loop.
func (*Loop) IntersectsCell ¶
IntersectsCell reports whether this Loop intersects the given cell.
func (*Loop) Invert ¶
func (l *Loop) Invert()
Invert reverses the order of the loop vertices, effectively complementing the region represented by the loop. For example, the loop ABCD (with edges AB, BC, CD, DA) becomes the loop DCBA (with edges DC, CB, BA, AD). Notice that the last edge is the same in both cases except that its direction has been reversed.
func (*Loop) IsEmpty ¶
IsEmpty reports true if this is the special empty loop that contains no points.
func (*Loop) IsFull ¶
IsFull reports true if this is the special full loop that contains all points.
func (*Loop) IsNormalized ¶
IsNormalized reports whether the loop area is at most 2*pi. Degenerate loops are handled consistently with Sign, i.e., if a loop can be expressed as the union of degenerate or nearlydegenerate CCW triangles, then it will always be considered normalized.
func (*Loop) Normalize ¶
func (l *Loop) Normalize()
Normalize inverts the loop if necessary so that the area enclosed by the loop is at most 2*pi.
func (*Loop) NumVertices ¶
NumVertices returns the number of vertices in this loop.
func (*Loop) OrientedVertex ¶
OrientedVertex returns the vertex in reverse order if the loop represents a polygon hole. For example, arguments 0, 1, 2 are mapped to vertices n1, n2, n3, where n == len(vertices). This ensures that the interior of the polygon is always to the left of the vertex chain.
This requires: 0 <= i < 2 * len(vertices)
func (*Loop) RectBound ¶
RectBound returns a tight bounding rectangle. If the loop contains the point, the bound also contains it.
func (*Loop) ReferencePoint ¶
func (l *Loop) ReferencePoint() ReferencePoint
ReferencePoint returns the reference point for this loop.
func (*Loop) Sign ¶
Sign returns 1 if this Loop represents a hole in its containing polygon, and +1 otherwise.
func (*Loop) TurningAngle ¶
TurningAngle returns the sum of the turning angles at each vertex. The return value is positive if the loop is counterclockwise, negative if the loop is clockwise, and zero if the loop is a great circle. Degenerate and nearlydegenerate loops are handled consistently with Sign. So for example, if a loop has zero area (i.e., it is a very small CCW loop) then the turning angle will always be negative.
This quantity is also called the "geodesic curvature" of the loop.
type MaxDistanceToCellTarget ¶
type MaxDistanceToCellTarget struct {
// contains filtered or unexported fields
}
MaxDistanceToCellTarget is used for computing the maximum distance to a Cell.
func NewMaxDistanceToCellTarget ¶
func NewMaxDistanceToCellTarget(cell Cell) *MaxDistanceToCellTarget
NewMaxDistanceToCellTarget returns a new target for the given Cell.
type MaxDistanceToEdgeTarget ¶
type MaxDistanceToEdgeTarget struct {
// contains filtered or unexported fields
}
MaxDistanceToEdgeTarget is used for computing the maximum distance to an Edge.
func NewMaxDistanceToEdgeTarget ¶
func NewMaxDistanceToEdgeTarget(e Edge) *MaxDistanceToEdgeTarget
NewMaxDistanceToEdgeTarget returns a new target for the given Edge.
type MaxDistanceToPointTarget ¶
type MaxDistanceToPointTarget struct {
// contains filtered or unexported fields
}
MaxDistanceToPointTarget is used for computing the maximum distance to a Point.
func NewMaxDistanceToPointTarget ¶
func NewMaxDistanceToPointTarget(point Point) *MaxDistanceToPointTarget
NewMaxDistanceToPointTarget returns a new target for the given Point.
type MaxDistanceToShapeIndexTarget ¶
type MaxDistanceToShapeIndexTarget struct {
// contains filtered or unexported fields
}
MaxDistanceToShapeIndexTarget is used for computing the maximum distance to a ShapeIndex.
func NewMaxDistanceToShapeIndexTarget ¶
func NewMaxDistanceToShapeIndexTarget(index *ShapeIndex) *MaxDistanceToShapeIndexTarget
NewMaxDistanceToShapeIndexTarget returns a new target for the given ShapeIndex.
type MercatorProjection ¶
type MercatorProjection struct {
// contains filtered or unexported fields
}
MercatorProjection defines the spherical Mercator projection. Google Maps uses this projection together with WGS84 coordinates, in which case it is known as the "Web Mercator" projection (see Wikipedia). This class makes no assumptions regarding the coordinate system of its input points, but simply applies the spherical Mercator projection to them.
The Mercator projection is finite in width (x) but infinite in height (y). "x" corresponds to longitude, and spans a finite range such as [180, 180] (with coordinate wrapping), while "y" is a function of latitude and spans an infinite range. (As "y" coordinates get larger, points get closer to the north pole but never quite reach it.) The north and south poles have infinite "y" values. (Note that this will cause problems if you tessellate a Mercator edge where one endpoint is a pole. If you need to do this, clip the edge first so that the "y" coordinate is no more than about 5 * maxX.)
func (*MercatorProjection) FromLatLng ¶
func (p *MercatorProjection) FromLatLng(ll LatLng) r2.Point
FromLatLng returns the LatLng projected into an R2 Point.
func (*MercatorProjection) Interpolate ¶
Interpolate returns the point obtained by interpolating the given fraction of the distance along the line from A to B.
func (*MercatorProjection) Project ¶
func (p *MercatorProjection) Project(pt Point) r2.Point
Project converts a point on the sphere to a projected 2D point.
func (*MercatorProjection) ToLatLng ¶
func (p *MercatorProjection) ToLatLng(pt r2.Point) LatLng
ToLatLng returns the LatLng projected from the given R2 Point.
func (*MercatorProjection) Unproject ¶
func (p *MercatorProjection) Unproject(pt r2.Point) Point
Unproject converts a projected 2D point to a point on the sphere.
func (*MercatorProjection) WrapDestination ¶
func (p *MercatorProjection) WrapDestination(a, b r2.Point) r2.Point
WrapDestination wraps the points if needed to get the shortest edge.
func (*MercatorProjection) WrapDistance ¶
func (p *MercatorProjection) WrapDistance() r2.Point
WrapDistance reports the coordinate wrapping distance along each axis.
type Metric ¶
type Metric struct { // Dim is either 1 or 2, for a 1D or 2D metric respectively. Dim int // Deriv is the scaling factor for the metric. Deriv float64 }
A Metric is a measure for cells. It is used to describe the shape and size of cells. They are useful for deciding which cell level to use in order to satisfy a given condition (e.g. that cell vertices must be no further than "x" apart). You can use the Value(level) method to compute the corresponding length or area on the unit sphere for cells at a given level. The minimum and maximum bounds are valid for cells at all levels, but they may be somewhat conservative for very large cells (e.g. face cells).
func (Metric) ClosestLevel ¶
ClosestLevel returns the level at which the metric has approximately the given value. The return value is always a valid level. For example, AvgEdgeMetric.ClosestLevel(0.1) returns the level at which the average cell edge length is approximately 0.1.
func (Metric) MaxLevel ¶
MaxLevel returns the maximum level such that the metric is at least the given value, or zero if there is no such level.
For example, MaxLevel(0.1) returns the maximum level such that all cells have a minimum width of 0.1 or larger. The returned value is always a valid level.
In C++, this is called GetLevelForMinValue.
func (Metric) MinLevel ¶
MinLevel returns the minimum level such that the metric is at most the given value, or MaxLevel (30) if there is no such level.
For example, MinLevel(0.1) returns the minimum level such that all cell diagonal lengths are 0.1 or smaller. The returned value is always a valid level.
In C++, this is called GetLevelForMaxValue.
type MinDistanceToCellTarget ¶
type MinDistanceToCellTarget struct {
// contains filtered or unexported fields
}
MinDistanceToCellTarget is a type for computing the minimum distance to a Cell.
func NewMinDistanceToCellTarget ¶
func NewMinDistanceToCellTarget(cell Cell) *MinDistanceToCellTarget
NewMinDistanceToCellTarget returns a new target for the given Cell.
type MinDistanceToEdgeTarget ¶
type MinDistanceToEdgeTarget struct {
// contains filtered or unexported fields
}
MinDistanceToEdgeTarget is a type for computing the minimum distance to an Edge.
func NewMinDistanceToEdgeTarget ¶
func NewMinDistanceToEdgeTarget(e Edge) *MinDistanceToEdgeTarget
NewMinDistanceToEdgeTarget returns a new target for the given Edge.
type MinDistanceToPointTarget ¶
type MinDistanceToPointTarget struct {
// contains filtered or unexported fields
}
MinDistanceToPointTarget is a type for computing the minimum distance to a Point.
func NewMinDistanceToPointTarget ¶
func NewMinDistanceToPointTarget(point Point) *MinDistanceToPointTarget
NewMinDistanceToPointTarget returns a new target for the given Point.
type MinDistanceToShapeIndexTarget ¶
type MinDistanceToShapeIndexTarget struct {
// contains filtered or unexported fields
}
MinDistanceToShapeIndexTarget is a type for computing the minimum distance to a ShapeIndex.
func NewMinDistanceToShapeIndexTarget ¶
func NewMinDistanceToShapeIndexTarget(index *ShapeIndex) *MinDistanceToShapeIndexTarget
NewMinDistanceToShapeIndexTarget returns a new target for the given ShapeIndex.
type PaddedCell ¶
type PaddedCell struct {
// contains filtered or unexported fields
}
PaddedCell represents a Cell whose (u,v)range has been expanded on all sides by a given amount of "padding". Unlike Cell, its methods and representation are optimized for clipping edges against Cell boundaries to determine which cells are intersected by a given set of edges.
func PaddedCellFromCellID ¶
func PaddedCellFromCellID(id CellID, padding float64) *PaddedCell
PaddedCellFromCellID constructs a padded cell with the given padding.
func PaddedCellFromParentIJ ¶
func PaddedCellFromParentIJ(parent *PaddedCell, i, j int) *PaddedCell
PaddedCellFromParentIJ constructs the child of parent with the given (i,j) index. The four child cells have indices of (0,0), (0,1), (1,0), (1,1), where the i and j indices correspond to increasing u and vvalues respectively.
func (PaddedCell) Bound ¶
func (p PaddedCell) Bound() r2.Rect
Bound returns the bounds for this cell in (u,v)space including padding.
func (PaddedCell) CellID ¶
func (p PaddedCell) CellID() CellID
CellID returns the CellID this padded cell represents.
func (PaddedCell) Center ¶
func (p PaddedCell) Center() Point
Center returns the center of this cell.
func (PaddedCell) ChildIJ ¶
func (p PaddedCell) ChildIJ(pos int) (i, j int)
ChildIJ returns the (i,j) coordinates for the child cell at the given traversal position. The traversal position corresponds to the order in which child cells are visited by the Hilbert curve.
func (PaddedCell) EntryVertex ¶
func (p PaddedCell) EntryVertex() Point
EntryVertex return the vertex where the spacefilling curve enters this cell.
func (PaddedCell) ExitVertex ¶
func (p PaddedCell) ExitVertex() Point
ExitVertex returns the vertex where the spacefilling curve exits this cell.
func (*PaddedCell) Middle ¶
func (p *PaddedCell) Middle() r2.Rect
Middle returns the rectangle in the middle of this cell that belongs to all four of its children in (u,v)space.
func (PaddedCell) Padding ¶
func (p PaddedCell) Padding() float64
Padding returns the amount of padding on this cell.
func (*PaddedCell) ShrinkToFit ¶
func (p *PaddedCell) ShrinkToFit(rect r2.Rect) CellID
ShrinkToFit returns the smallest CellID that contains all descendants of this padded cell whose bounds intersect the given rect. For algorithms that use recursive subdivision to find the cells that intersect a particular object, this method can be used to skip all of the initial subdivision steps where only one child needs to be expanded.
Note that this method is not the same as returning the smallest cell that contains the intersection of this cell with rect. Because of the padding, even if one child completely contains rect it is still possible that a neighboring child may also intersect the given rect.
The provided Rect must intersect the bounds of this cell.
type PlateCarreeProjection ¶
type PlateCarreeProjection struct {
// contains filtered or unexported fields
}
PlateCarreeProjection defines the "plate carree" (square plate) projection, which converts points on the sphere to (longitude, latitude) pairs. Coordinates can be scaled so that they represent radians, degrees, etc, but the projection is always centered around (latitude=0, longitude=0).
Note that (x, y) coordinates are backwards compared to the usual (latitude, longitude) ordering, in order to match the usual convention for graphs in which "x" is horizontal and "y" is vertical.
func (*PlateCarreeProjection) FromLatLng ¶
func (p *PlateCarreeProjection) FromLatLng(ll LatLng) r2.Point
FromLatLng returns the LatLng projected into an R2 Point.
func (*PlateCarreeProjection) Interpolate ¶
Interpolate returns the point obtained by interpolating the given fraction of the distance along the line from A to B.
func (*PlateCarreeProjection) Project ¶
func (p *PlateCarreeProjection) Project(pt Point) r2.Point
Project converts a point on the sphere to a projected 2D point.
func (*PlateCarreeProjection) ToLatLng ¶
func (p *PlateCarreeProjection) ToLatLng(pt r2.Point) LatLng
ToLatLng returns the LatLng projected from the given R2 Point.
func (*PlateCarreeProjection) Unproject ¶
func (p *PlateCarreeProjection) Unproject(pt r2.Point) Point
Unproject converts a projected 2D point to a point on the sphere.
func (*PlateCarreeProjection) WrapDestination ¶
func (p *PlateCarreeProjection) WrapDestination(a, b r2.Point) r2.Point
WrapDestination wraps the points if needed to get the shortest edge.
func (*PlateCarreeProjection) WrapDistance ¶
func (p *PlateCarreeProjection) WrapDistance() r2.Point
WrapDistance reports the coordinate wrapping distance along each axis.
type Point ¶
Point represents a point on the unit sphere as a normalized 3D vector. Fields should be treated as readonly. Use one of the factory methods for creation.
func EdgeTrueCentroid ¶
EdgeTrueCentroid returns the true centroid of the spherical geodesic edge AB multiplied by the length of the edge AB. As with triangles, the true centroid of a collection of line segments may be computed simply by summing the result of this method for each segment.
Note that the planar centroid of a line segment is simply 0.5 * (a + b), while the surface centroid is (a + b).Normalize(). However neither of these values is appropriate for computing the centroid of a collection of edges (such as a polyline).
Also note that the result of this function is defined to be Point(0, 0, 0) if the edge is degenerate.
func Interpolate ¶
Interpolate returns the point X along the line segment AB whose distance from A is the given fraction "t" of the distance AB. Does NOT require that "t" be between 0 and 1. Note that all distances are measured on the surface of the sphere, so this is more complicated than just computing (1t)*a + t*b and normalizing the result.
func InterpolateAtDistance ¶
InterpolateAtDistance returns the point X along the line segment AB whose distance from A is the angle ax.
func Intersection ¶
Intersection returns the intersection point of two edges AB and CD that cross (CrossingSign(a,b,c,d) == Crossing).
Useful properties of Intersection:
(1) Intersection(b,a,c,d) == Intersection(a,b,d,c) == Intersection(a,b,c,d) (2) Intersection(c,d,a,b) == Intersection(a,b,c,d)
The returned intersection point X is guaranteed to be very close to the true intersection point of AB and CD, even if the edges intersect at a very small angle.
func OriginPoint ¶
func OriginPoint() Point
OriginPoint returns a unique "origin" on the sphere for operations that need a fixed reference point. In particular, this is the "point at infinity" used for pointinpolygon testing (by counting the number of edge crossings).
It should *not* be a point that is commonly used in edge tests in order to avoid triggering code to handle degenerate cases (this rules out the north and south poles). It should also not be on the boundary of any lowlevel S2Cell for the same reason.
func Ortho ¶
Ortho returns a unitlength vector that is orthogonal to "a". Satisfies Ortho(a) = Ortho(a) for all a.
Note that Vector3 also defines an "Ortho" method, but this one is preferred for use in S2 code because it explicitly tries to avoid result coordinates that are zero. (This is a performance optimization that reduces the amount of time spent in functions that handle degeneracies.)
func PlanarCentroid ¶
PlanarCentroid returns the centroid of the planar triangle ABC. This can be normalized to unit length to obtain the "surface centroid" of the corresponding spherical triangle, i.e. the intersection of the three medians. However, note that for large spherical triangles the surface centroid may be nowhere near the intuitive "center".
func PointFromCoords ¶
PointFromCoords creates a new normalized point from coordinates.
This always returns a valid point. If the given coordinates can not be normalized the origin point will be returned.
This behavior is different from the C++ construction of a S2Point from coordinates (i.e. S2Point(x, y, z)) in that in C++ they do not Normalize.
func PointFromLatLng ¶
PointFromLatLng returns an Point for the given LatLng. The maximum error in the result is 1.5 * dblEpsilon. (This does not include the error of converting degrees, E5, E6, or E7 into radians.)
func Project ¶
Project returns the point along the edge AB that is closest to the point X. The fractional distance of this point along the edge AB can be obtained using DistanceFraction.
This requires that all points are unit length.
func Rotate ¶
Rotate the given point about the given axis by the given angle. p and axis must be unit length; angle has no restrictions (e.g., it can be positive, negative, greater than 360 degrees, etc).
func TrueCentroid ¶
TrueCentroid returns the true centroid of the spherical triangle ABC multiplied by the signed area of spherical triangle ABC. The reasons for multiplying by the signed area are (1) this is the quantity that needs to be summed to compute the centroid of a union or difference of triangles, and (2) it's actually easier to calculate this way. All points must have unit length.
Note that the result of this function is defined to be Point(0, 0, 0) if the triangle is degenerate.
func (Point) ApproxEqual ¶
ApproxEqual reports whether the two points are similar enough to be equal.
func (Point) CellUnionBound ¶
CellUnionBound computes a covering of the Point.
func (Point) Contains ¶
Contains reports if this Point contains the other Point. (This method matches all other s2 types where the reflexive Contains method does not contain the type's name.)
func (Point) ContainsCell ¶
ContainsCell returns false as Points do not contain any other S2 types.
func (Point) ContainsPoint ¶
ContainsPoint reports if this Point contains the other Point. (This method is named to satisfy the Region interface.)
func (Point) IntersectsCell ¶
IntersectsCell reports whether this Point intersects the given cell.
func (Point) PointCross ¶
PointCross returns a Point that is orthogonal to both p and op. This is similar to p.Cross(op) (the true cross product) except that it does a better job of ensuring orthogonality when the Point is nearly parallel to op, it returns a nonzero result even when p == op or p == op and the result is a Point.
It satisfies the following properties (f == PointCross):
(1) f(p, op) != 0 for all p, op (2) f(op,p) == f(p,op) unless p == op or p == op (3) f(p,op) == f(p,op) unless p == op or p == op (4) f(p,op) == f(p,op) unless p == op or p == op
type PointVector ¶
type PointVector []Point
PointVector is a Shape representing a set of Points. Each point is represented as a degenerate edge with the same starting and ending vertices.
This type is useful for adding a collection of points to an ShapeIndex.
Its methods are on *PointVector due to implementation details of ShapeIndex.
func (*PointVector) Chain ¶
func (p *PointVector) Chain(i int) Chain
func (*PointVector) ChainEdge ¶
func (p *PointVector) ChainEdge(i, j int) Edge
func (*PointVector) ChainPosition ¶
func (p *PointVector) ChainPosition(e int) ChainPosition
func (*PointVector) Dimension ¶
func (p *PointVector) Dimension() int
func (*PointVector) Edge ¶
func (p *PointVector) Edge(i int) Edge
func (*PointVector) IsEmpty ¶
func (p *PointVector) IsEmpty() bool
func (*PointVector) IsFull ¶
func (p *PointVector) IsFull() bool
func (*PointVector) NumChains ¶
func (p *PointVector) NumChains() int
func (*PointVector) NumEdges ¶
func (p *PointVector) NumEdges() int
func (*PointVector) ReferencePoint ¶
func (p *PointVector) ReferencePoint() ReferencePoint
type Polygon ¶
type Polygon struct {
// contains filtered or unexported fields
}
Polygon represents a sequence of zero or more loops; recall that the interior of a loop is defined to be its lefthand side (see Loop).
When the polygon is initialized, the given loops are automatically converted into a canonical form consisting of "shells" and "holes". Shells and holes are both oriented CCW, and are nested hierarchically. The loops are reordered to correspond to a preorder traversal of the nesting hierarchy.
Polygons may represent any region of the sphere with a polygonal boundary, including the entire sphere (known as the "full" polygon). The full polygon consists of a single full loop (see Loop), whereas the empty polygon has no loops at all.
Use FullPolygon() to construct a full polygon. The zero value of Polygon is treated as the empty polygon.
Polygons have the following restrictions:
Loops may not cross, i.e. the boundary of a loop may not intersect both the interior and exterior of any other loop.
Loops may not share edges, i.e. if a loop contains an edge AB, then no other loop may contain AB or BA.
Loops may share vertices, however no vertex may appear twice in a single loop (see Loop).
No loop may be empty. The full loop may appear only in the full polygon.
func PolygonFromCell ¶
PolygonFromCell returns a Polygon from a single loop created from the given Cell.
func PolygonFromLoops ¶
PolygonFromLoops constructs a polygon from the given set of loops. The polygon interior consists of the points contained by an odd number of loops. (Recall that a loop contains the set of points on its lefthand side.)
This method determines the loop nesting hierarchy and assigns every loop a depth. Shells have even depths, and holes have odd depths.
Note: The given set of loops are reordered by this method so that the hierarchy can be traversed using Parent, LastDescendant and the loops depths.
func PolygonFromOrientedLoops ¶
PolygonFromOrientedLoops returns a Polygon from the given set of loops, like PolygonFromLoops. It expects loops to be oriented such that the polygon interior is on the lefthand side of all loops. This implies that shells and holes should have opposite orientations in the input to this method. (During initialization, loops representing holes will automatically be inverted.)
Example ¶
package main import ( "fmt" "github.com/golang/geo/s2" ) func main() { // Let's define three loops, in format World Geodetic System 1984, // the format that geoJSON uses. The third loop is a hole in the second, // the first loop is remote from the others. Loops 1 and 2 are counterclockwise, // while loop 3 is clockwise. l1 := [][]float64{ {102.0, 2.0}, {103.0, 2.0}, {103.0, 3.0}, {102.0, 3.0}, } l2 := [][]float64{ {100.0, 0.0}, {101.0, 0.0}, {101.0, 1.0}, {100.0, 1.0}, } l3 := [][]float64{ {100.2, 0.2}, {100.2, 0.8}, {100.8, 0.8}, {100.8, 0.2}, } toLoop := func(points [][]float64) *s2.Loop { var pts []s2.Point for _, pt := range points { pts = append(pts, s2.PointFromLatLng(s2.LatLngFromDegrees(pt[1], pt[0]))) } return s2.LoopFromPoints(pts) } // We can combine all loops into a single polygon: p := s2.PolygonFromOrientedLoops([]*s2.Loop{toLoop(l1), toLoop(l2), toLoop(l3)}) for i, loop := range p.Loops() { fmt.Printf("loop %d is hole: %t\n", i, loop.IsHole()) } fmt.Printf("Combined area: %.7f\n", p.Area()) // Note how the area of the polygon is the area of l1 + l2  invert(l3), because l3 is a hole: p12 := s2.PolygonFromOrientedLoops([]*s2.Loop{toLoop(l1), toLoop(l2)}) p3 := s2.PolygonFromOrientedLoops([]*s2.Loop{toLoop(l3)}) p3.Invert() fmt.Printf("l1+l2 = %.7f, inv(l3) = %.7f; l1+l2  inv(l3) = %.7f\n", p12.Area(), p3.Area(), p12.Area()p3.Area()) }
Output: loop 0 is hole: false loop 1 is hole: false loop 2 is hole: true Combined area: 0.0004993 l1+l2 = 0.0006089, inv(l3) = 0.0001097; l1+l2  inv(l3) = 0.0004993
func (*Polygon) Area ¶
Area returns the area of the polygon interior, i.e. the region on the left side of an odd number of loops. The return value is between 0 and 4*Pi.
func (*Polygon) CellUnionBound ¶
CellUnionBound computes a covering of the Polygon.
func (*Polygon) Centroid ¶
Centroid returns the true centroid of the polygon multiplied by the area of the polygon. The result is not unit length, so you may want to normalize it. Also note that in general, the centroid may not be contained by the polygon.
We prescale by the polygon area for two reasons: (1) it is cheaper to compute this way, and (2) it makes it easier to compute the centroid of more complicated shapes (by splitting them into disjoint regions and adding their centroids).
func (*Polygon) ChainPosition ¶
func (p *Polygon) ChainPosition(edgeID int) ChainPosition
ChainPosition returns a pair (i, j) such that edgeID is the jth edge of the ith edge Chain.
func (*Polygon) Contains ¶
Contains reports whether this polygon contains the other polygon. Specifically, it reports whether all the points in the other polygon are also in this polygon.
func (*Polygon) ContainsCell ¶
ContainsCell reports whether the polygon contains the given cell.
func (*Polygon) ContainsPoint ¶
ContainsPoint reports whether the polygon contains the point.
func (*Polygon) Dimension ¶
Dimension returns the dimension of the geometry represented by this Polygon.
func (*Polygon) Intersects ¶
Intersects reports whether this polygon intersects the other polygon, i.e. if there is a point that is contained by both polygons.
func (*Polygon) IntersectsCell ¶
IntersectsCell reports whether the polygon intersects the given cell.
func (*Polygon) Invert ¶
func (p *Polygon) Invert()
Invert inverts the polygon (replaces it by its complement).
func (*Polygon) IsEmpty ¶
IsEmpty reports whether this is the special "empty" polygon (consisting of no loops).
func (*Polygon) IsFull ¶
IsFull reports whether this is the special "full" polygon (consisting of a single loop that encompasses the entire sphere).
func (*Polygon) LastDescendant ¶
LastDescendant returns the index of the last loop that is contained within loop k. If k is negative, it returns the last loop in the polygon. Note that loops are indexed according to a preorder traversal of the nesting hierarchy, so the immediate children of loop k can be found by iterating over the loops (k+1)..LastDescendant(k) and selecting those whose depth is equal to Loop(k).depth+1.
func (*Polygon) Loop ¶
Loop returns the loop at the given index. Note that during initialization, the given loops are reordered according to a preorder traversal of the loop nesting hierarchy. This implies that every loop is immediately followed by its descendants. This hierarchy can be traversed using the methods Parent, LastDescendant, and Loop.depth.
func (*Polygon) Parent ¶
Parent returns the index of the parent of loop k. If the loop does not have a parent, ok=false is returned.
func (*Polygon) ReferencePoint ¶
func (p *Polygon) ReferencePoint() ReferencePoint
ReferencePoint returns the reference point for this polygon.
type Polyline ¶
type Polyline []Point
Polyline represents a sequence of zero or more vertices connected by straight edges (geodesics). Edges of length 0 and 180 degrees are not allowed, i.e. adjacent vertices should not be identical or antipodal.
func PolylineFromLatLngs ¶
PolylineFromLatLngs creates a new Polyline from the given LatLngs.
func (*Polyline) ApproxEqual ¶
ApproxEqual reports whether two polylines have the same number of vertices, and corresponding vertex pairs are separated by no more the standard margin.
func (*Polyline) CellUnionBound ¶
CellUnionBound computes a covering of the Polyline.
func (*Polyline) Centroid ¶
Centroid returns the true centroid of the polyline multiplied by the length of the polyline. The result is not unit length, so you may wish to normalize it.
Scaling by the Polyline length makes it easy to compute the centroid of several Polylines (by simply adding up their centroids).
func (*Polyline) ChainPosition ¶
func (p *Polyline) ChainPosition(edgeID int) ChainPosition
ChainPosition returns a pair (i, j) such that edgeID is the jth edge
func (*Polyline) ContainsCell ¶
ContainsCell reports whether this Polyline contains the given Cell. Always returns false because "containment" is not numerically welldefined except at the Polyline vertices.
func (*Polyline) ContainsPoint ¶
ContainsPoint returns false since Polylines are not closed.
func (*Polyline) Dimension ¶
Dimension returns the dimension of the geometry represented by this Polyline.
func (*Polyline) Interpolate ¶
Interpolate returns the point whose distance from vertex 0 along the polyline is the given fraction of the polyline's total length, and the index of the next vertex after the interpolated point P. Fractions less than zero or greater than one are clamped. The return value is unit length. The cost of this function is currently linear in the number of vertices.
This method allows the caller to easily construct a given suffix of the polyline by concatenating P with the polyline vertices starting at that next vertex. Note that P is guaranteed to be different than the point at the next vertex, so this will never result in a duplicate vertex.
The polyline must not be empty. Note that if fraction >= 1.0, then the next vertex will be set to len(p) (indicating that no vertices from the polyline need to be appended). The value of the next vertex is always between 1 and len(p).
This method can also be used to construct a prefix of the polyline, by taking the polyline vertices up to next vertex1 and appending the returned point P if it is different from the last vertex (since in this case there is no guarantee of distinctness).
func (*Polyline) Intersects ¶
Intersects reports whether this polyline intersects the given polyline. If the polylines share a vertex they are considered to be intersecting. When a polyline endpoint is the only intersection with the other polyline, the function may return true or false arbitrarily.
The running time is quadratic in the number of vertices.
func (*Polyline) IntersectsCell ¶
IntersectsCell reports whether this Polyline intersects the given Cell.
func (*Polyline) IsOnRight ¶
IsOnRight reports whether the point given is on the right hand side of the polyline, using a naive definition of "righthandsideness" where the point is on the RHS of the polyline iff the point is on the RHS of the line segment in the polyline which it is closest to. The polyline must have at least 2 vertices.
func (*Polyline) NumChains ¶
NumChains reports the number of contiguous edge chains in this Polyline.
func (*Polyline) Project ¶
Project returns a point on the polyline that is closest to the given point, and the index of the next vertex after the projected point. The value of that index is always in the range [1, len(polyline)]. The polyline must not be empty.
func (*Polyline) ReferencePoint ¶
func (p *Polyline) ReferencePoint() ReferencePoint
ReferencePoint returns the default reference point with negative containment because Polylines are not closed.
func (*Polyline) Reverse ¶
func (p *Polyline) Reverse()
Reverse reverses the order of the Polyline vertices.
func (*Polyline) SubsampleVertices ¶
SubsampleVertices returns a subsequence of vertex indices such that the polyline connecting these vertices is never further than the given tolerance from the original polyline. Provided the first and last vertices are distinct, they are always preserved; if they are not, the subsequence may contain only a single index.
Some useful properties of the algorithm:
It runs in linear time.
The output always represents a valid polyline. In particular, adjacent output vertices are never identical or antipodal.
The method is not optimal, but it tends to produce 23% fewer vertices than the DouglasPeucker algorithm with the same tolerance.
The output is parametrically equivalent to the original polyline to within the given tolerance. For example, if a polyline backtracks on itself and then proceeds onwards, the backtracking will be preserved (to within the given tolerance). This is different than the DouglasPeucker algorithm which only guarantees geometric equivalence.
func (*Polyline) Uninterpolate ¶
Uninterpolate is the inverse operation of Interpolate. Given a point on the polyline, it returns the ratio of the distance to the point from the beginning of the polyline over the length of the polyline. The return value is always between 0 and 1 inclusive.
The polyline should not be empty. If it has fewer than 2 vertices, the return value is zero.
type Projection ¶
type Projection interface { // Project converts a point on the sphere to a projected 2D point. Project(p Point) r2.Point // Unproject converts a projected 2D point to a point on the sphere. // // If wrapping is defined for a given axis (see below), then this method // should accept any real number for the corresponding coordinate. Unproject(p r2.Point) Point // FromLatLng is a convenience function equivalent to Project(LatLngToPoint(ll)), // but the implementation is more efficient. FromLatLng(ll LatLng) r2.Point // ToLatLng is a convenience function equivalent to LatLngFromPoint(Unproject(p)), // but the implementation is more efficient. ToLatLng(p r2.Point) LatLng // Interpolate returns the point obtained by interpolating the given // fraction of the distance along the line from A to B. // Fractions < 0 or > 1 result in extrapolation instead. Interpolate(f float64, a, b r2.Point) r2.Point // WrapDistance reports the coordinate wrapping distance along each axis. // If this value is nonzero for a given axis, the coordinates are assumed // to "wrap" with the given period. For example, if WrapDistance.Y == 360 // then (x, y) and (x, y + 360) should map to the same Point. // // This information is used to ensure that edges takes the shortest path // between two given points. For example, if coordinates represent // (latitude, longitude) pairs in degrees and WrapDistance().Y == 360, // then the edge (5:179, 5:179) would be interpreted as spanning 2 degrees // of longitude rather than 358 degrees. // // If a given axis does not wrap, its WrapDistance should be set to zero. WrapDistance() r2.Point // WrapDestination that wraps the coordinates of B if necessary in order to // obtain the shortest edge AB. For example, suppose that A = [170, 20], // B = [170, 20], and the projection wraps so that [x, y] == [x + 360, y]. // Then this function would return [190, 20] for point B (reducing the edge // length in the "x" direction from 340 to 20). WrapDestination(a, b r2.Point) r2.Point // contains filtered or unexported methods }
Projection defines an interface for different ways of mapping between s2 and r2 Points. It can also define the coordinate wrapping behavior along each axis.
func NewMercatorProjection ¶
func NewMercatorProjection(maxLng float64) Projection
NewMercatorProjection constructs a Mercator projection with the given maximum longitude axis value corresponding to a range of [maxLng, maxLng]. The horizontal and vertical axes are scaled equally.
func NewPlateCarreeProjection ¶
func NewPlateCarreeProjection(xScale float64) Projection
NewPlateCarreeProjection constructs a plate carree projection where the xcoordinates (lng) span [xScale, xScale] and the y coordinates (lat) span [xScale/2, xScale/2]. For example if xScale==180 then the x range is [180, 180] and the y range is [90, 90].
By default coordinates are expressed in radians, i.e. the x range is [Pi, Pi] and the y range is [Pi/2, Pi/2].
type Rect ¶
Rect represents a closed latitudelongitude rectangle.
func ExpandForSubregions ¶
ExpandForSubregions expands a bounding Rect so that it is guaranteed to contain the bounds of any subregion whose bounds are computed using ComputeRectBound. For example, consider a loop L that defines a square. GetBound ensures that if a point P is contained by this square, then LatLngFromPoint(P) is contained by the bound. But now consider a diamond shaped loop S contained by L. It is possible that GetBound returns a *larger* bound for S than it does for L, due to rounding errors. This method expands the bound for L so that it is guaranteed to contain the bounds of any subregion S.
More precisely, if L is a loop that does not contain either pole, and S is a loop such that L.Contains(S), then
ExpandForSubregions(L.RectBound).Contains(S.RectBound).
func RectFromCenterSize ¶
RectFromCenterSize constructs a rectangle with the given size and center. center needs to be normalized, but size does not. The latitude interval of the result is clamped to [90,90] degrees, and the longitude interval of the result is FullRect() if and only if the longitude size is 360 degrees or more.
Examples of clamping (in degrees):
center=(80,170), size=(40,60) > lat=[60,90], lng=[140,160] center=(10,40), size=(210,400) > lat=[90,90], lng=[180,180] center=(90,180), size=(20,50) > lat=[90,80], lng=[155,155]
func RectFromLatLng ¶
RectFromLatLng constructs a rectangle containing a single point p.
func (Rect) ApproxEqual ¶
ApproxEqual reports whether the latitude and longitude intervals of the two rectangles are the same up to a small tolerance.
func (Rect) CellUnionBound ¶
CellUnionBound computes a covering of the Rect.
func (Rect) Centroid ¶
Centroid returns the true centroid of the given Rect multiplied by its surface area. The result is not unit length, so you may want to normalize it. Note that in general the centroid is *not* at the center of the rectangle, and in fact it may not even be contained by the rectangle. (It is the "center of mass" of the rectangle viewed as subset of the unit sphere, i.e. it is the point in space about which this curved shape would rotate.)
The reason for multiplying the result by the rectangle area is to make it easier to compute the centroid of more complicated shapes. The centroid of a union of disjoint regions can be computed simply by adding their Centroid results.
func (Rect) ContainsCell ¶
ContainsCell reports whether the given Cell is contained by this Rect.
func (Rect) ContainsLatLng ¶
ContainsLatLng reports whether the given LatLng is within the Rect.
func (Rect) ContainsPoint ¶
ContainsPoint reports whether the given Point is within the Rect.
func (Rect) DirectedHausdorffDistance ¶
DirectedHausdorffDistance returns the directed Hausdorff distance (measured along the surface of the sphere) to the given Rect. The directed Hausdorff distance from rectangle A to rectangle B is given by
h(A, B) = max_{p in A} min_{q in B} d(p, q).
func (Rect) DistanceToLatLng ¶
DistanceToLatLng returns the minimum distance (measured along the surface of the sphere) from a given point to the rectangle (both its boundary and its interior). If r is empty, the result is meaningless. The latlng must be valid.
Example ¶
package main import ( "fmt" "github.com/golang/geo/s1" "github.com/golang/geo/s2" ) func main() { r := s2.RectFromLatLng(s2.LatLngFromDegrees(1, 1)).AddPoint(s2.LatLngFromDegrees(1, 1)) printDist := func(lat, lng float64) { fmt.Printf("%f\n", r.DistanceToLatLng(s2.LatLngFromDegrees(lat, lng))/s1.Degree) } fmt.Println("Distances next to the rectangle.") printDist(2, 0) printDist(0, 2) printDist(2, 0) printDist(0, 2) fmt.Println("Distances beyond the corners of the rectangle.") printDist(2, 2) printDist(2, 2) printDist(2, 2) printDist(2, 2) fmt.Println("Distance within the rectangle.") printDist(0, 0) printDist(0.5, 0) printDist(0, 0.5) printDist(0.5, 0) printDist(0, 0.5) }
Output: Distances next to the rectangle. 1.000000 1.000000 1.000000 1.000000 Distances beyond the corners of the rectangle. 1.413962 1.413962 1.413962 1.413962 Distance within the rectangle. 0.000000 0.000000 0.000000 0.000000 0.000000
func (Rect) HausdorffDistance ¶
HausdorffDistance returns the undirected Hausdorff distance (measured along the surface of the sphere) to the given Rect. The Hausdorff distance between rectangle A and rectangle B is given by
H(A, B) = max{h(A, B), h(B, A)}.
func (Rect) Intersection ¶
Intersection returns the smallest rectangle containing the intersection of this rectangle and the given rectangle. Note that the region of intersection may consist of two disjoint rectangles, in which case a single rectangle spanning both of them is returned.
func (Rect) Intersects ¶
Intersects reports whether this rectangle and the other have any points in common.
func (Rect) IntersectsCell ¶
IntersectsCell reports whether this rectangle intersects the given cell. This is an exact test and may be fairly expensive.
func (Rect) IsValid ¶
IsValid returns true iff the rectangle is valid. This requires Lat ⊆ [π/2,π/2] and Lng ⊆ [π,π], and Lat = ∅ iff Lng = ∅
func (Rect) PolarClosure ¶
PolarClosure returns the rectangle unmodified if it does not include either pole. If it includes either pole, PolarClosure returns an expansion of the rectangle along the longitudinal range to include all possible representations of the contained poles.
type RectBounder ¶
type RectBounder struct {
// contains filtered or unexported fields
}
RectBounder is used to compute a bounding rectangle that contains all edges defined by a vertex chain (v0, v1, v2, ...). All vertices must be unit length. Note that the bounding rectangle of an edge can be larger than the bounding rectangle of its endpoints, e.g. consider an edge that passes through the North Pole.
The bounds are calculated conservatively to account for numerical errors when points are converted to LatLngs. More precisely, this function guarantees the following: Let L be a closed edge chain (Loop) such that the interior of the loop does not contain either pole. Now if P is any point such that L.ContainsPoint(P), then RectBound(L).ContainsPoint(LatLngFromPoint(P)).
func NewRectBounder ¶
func NewRectBounder() *RectBounder
NewRectBounder returns a new instance of a RectBounder.
func (*RectBounder) AddPoint ¶
func (r *RectBounder) AddPoint(b Point)
AddPoint adds the given point to the chain. The Point must be unit length.
func (*RectBounder) RectBound ¶
func (r *RectBounder) RectBound() Rect
RectBound returns the bounding rectangle of the edge chain that connects the vertices defined so far. This bound satisfies the guarantee made above, i.e. if the edge chain defines a Loop, then the bound contains the LatLng coordinates of all Points contained by the loop.
type ReferencePoint ¶
A ReferencePoint consists of a point and a boolean indicating whether the point is contained by a particular shape.
func OriginReferencePoint ¶
func OriginReferencePoint(contained bool) ReferencePoint
OriginReferencePoint returns a ReferencePoint with the given value for contained and the origin point. It should be used when all points or no points are contained.
type Region ¶
type Region interface { // CapBound returns a bounding spherical cap. This is not guaranteed to be exact. CapBound() Cap // RectBound returns a bounding latitudelongitude rectangle that contains // the region. The bounds are not guaranteed to be tight. RectBound() Rect // ContainsCell reports whether the region completely contains the given region. // It returns false if containment could not be determined. ContainsCell(c Cell) bool // IntersectsCell reports whether the region intersects the given cell or // if intersection could not be determined. It returns false if the region // does not intersect. IntersectsCell(c Cell) bool // ContainsPoint reports whether the region contains the given point or not. // The point should be unit length, although some implementations may relax // this restriction. ContainsPoint(p Point) bool // CellUnionBound returns a small collection of CellIDs whose union covers // the region. The cells are not sorted, may have redundancies (such as cells // that contain other cells), and may cover much more area than necessary. // // This method is not intended for direct use by client code. Clients // should typically use Covering, which has options to control the size and // accuracy of the covering. Alternatively, if you want a fast covering and // don't care about accuracy, consider calling FastCovering (which returns a // cleanedup version of the covering computed by this method). // // CellUnionBound implementations should attempt to return a small // covering (ideally 4 cells or fewer) that covers the region and can be // computed quickly. The result is used by RegionCoverer as a starting // point for further refinement. CellUnionBound() []CellID }
A Region represents a twodimensional region on the unit sphere.
The purpose of this interface is to allow complex regions to be approximated as simpler regions. The interface is restricted to methods that are useful for computing approximations.
type RegionCoverer ¶
type RegionCoverer struct { MinLevel int // the minimum cell level to be used. MaxLevel int // the maximum cell level to be used. LevelMod int // the LevelMod to be used. MaxCells int // the maximum desired number of cells in the approximation. }
RegionCoverer allows arbitrary regions to be approximated as unions of cells (CellUnion). This is useful for implementing various sorts of search and precomputation operations.
Typical usage:
rc := &s2.RegionCoverer{MaxLevel: 30, MaxCells: 5} r := s2.Region(CapFromCenterArea(center, area)) covering := rc.Covering(r)
This yields a CellUnion of at most 5 cells that is guaranteed to cover the given region (a discshaped region on the sphere).
For covering, only cells where (level  MinLevel) is a multiple of LevelMod will be used. This effectively allows the branching factor of the S2 CellID hierarchy to be increased. Currently the only parameter values allowed are 1, 2, or 3, corresponding to branching factors of 4, 16, and 64 respectively.
Note the following:
MinLevel takes priority over MaxCells, i.e. cells below the given level will never be used even if this causes a large number of cells to be returned.
For any setting of MaxCells, up to 6 cells may be returned if that is the minimum number of cells required (e.g. if the region intersects all six face cells). Up to 3 cells may be returned even for very tiny convex regions if they happen to be located at the intersection of three cube faces.
For any setting of MaxCells, an arbitrary number of cells may be returned if MinLevel is too high for the region being approximated.
If MaxCells is less than 4, the area of the covering may be arbitrarily large compared to the area of the original region even if the region is convex (e.g. a Cap or Rect).
The approximation algorithm is not optimal but does a pretty good job in practice. The output does not always use the maximum number of cells allowed, both because this would not always yield a better approximation, and because MaxCells is a limit on how much work is done exploring the possible covering as well as a limit on the final output size.
Because it is an approximation algorithm, one should not rely on the stability of the output. In particular, the output of the covering algorithm may change across different versions of the library.
One can also generate interior coverings, which are sets of cells which are entirely contained within a region. Interior coverings can be empty, even for nonempty regions, if there are no cells that satisfy the provided constraints and are contained by the region. Note that for performance reasons, it is wise to specify a MaxLevel when computing interior coverings  otherwise for regions with small or zero area, the algorithm may spend a lot of time subdividing cells all the way to leaf level to try to find contained cells.
func NewRegionCoverer ¶
func NewRegionCoverer() *RegionCoverer
NewRegionCoverer returns a region coverer with the appropriate defaults.
func (*RegionCoverer) CellUnion ¶
func (rc *RegionCoverer) CellUnion(region Region) CellUnion
CellUnion returns a normalized CellUnion that covers the given region and satisfies the restrictions except for minLevel and levelMod. These criteria cannot be satisfied using a cell union because cell unions are automatically normalized by replacing four child cells with their parent whenever possible. (Note that the list of cell ids passed to the CellUnion constructor does in fact satisfy all the given restrictions.)
func (*RegionCoverer) Covering ¶
func (rc *RegionCoverer) Covering(region Region) CellUnion
Covering returns a CellUnion that covers the given region and satisfies the various restrictions.
func (*RegionCoverer) FastCovering ¶
func (rc *RegionCoverer) FastCovering(region Region) CellUnion
FastCovering returns a CellUnion that covers the given region similar to Covering, except that this method is much faster and the coverings are not as tight. All of the usual parameters are respected (MaxCells, MinLevel, MaxLevel, and LevelMod), except that the implementation makes no attempt to take advantage of large values of MaxCells. (A small number of cells will always be returned.)
This function is useful as a starting point for algorithms that recursively subdivide cells.
func (*RegionCoverer) InteriorCellUnion ¶
func (rc *RegionCoverer) InteriorCellUnion(region Region) CellUnion
InteriorCellUnion returns a normalized CellUnion that is contained within the given region and satisfies the restrictions except for minLevel and levelMod. These criteria cannot be satisfied using a cell union because cell unions are automatically normalized by replacing four child cells with their parent whenever possible. (Note that the list of cell ids passed to the CellUnion constructor does in fact satisfy all the given restrictions.)
func (*RegionCoverer) InteriorCovering ¶
func (rc *RegionCoverer) InteriorCovering(region Region) CellUnion
InteriorCovering returns a CellUnion that is contained within the given region and satisfies the various restrictions.
func (*RegionCoverer) IsCanonical ¶
func (rc *RegionCoverer) IsCanonical(covering CellUnion) bool
IsCanonical reports whether the given CellUnion represents a valid covering that conforms to the current covering parameters. In particular:
All CellIDs must be valid.
CellIDs must be sorted and nonoverlapping.
CellID levels must satisfy MinLevel, MaxLevel, and LevelMod.
If the covering has more than MaxCells, there must be no two cells with a common ancestor at MinLevel or higher.
There must be no sequence of cells that could be replaced by an ancestor (i.e. with LevelMod == 1, the 4 child cells of a parent).
type RegionUnion ¶
type RegionUnion []Region
A RegionUnion represents a union of possibly overlapping regions. It is convenient for computing a covering of a set of regions. However, note that currently, using RegionCoverer to compute coverings of RegionUnions may produce coverings with considerably less than the requested number of cells in cases of overlapping or tiling regions. This occurs because the current RegionUnion.Contains implementation for Cells only returns true if the cell is fully contained by one of the regions. So, cells along internal boundaries in the region union will be subdivided by the coverer even though this is unnecessary, using up the maxSize cell budget. Then, when the coverer normalizes the covering, groups of 4 sibling cells along these internal borders will be replaced by parents, resulting in coverings that may have significantly fewer than maxSize cells, and so are less accurate. This is not a concern for unions of disjoint regions.
func (RegionUnion) CapBound ¶
func (ru RegionUnion) CapBound() Cap
CapBound returns a bounding cap for this RegionUnion.
func (RegionUnion) CellUnionBound ¶
func (ru RegionUnion) CellUnionBound() []CellID
CellUnionBound computes a covering of the RegionUnion.
func (RegionUnion) ContainsCell ¶
func (ru RegionUnion) ContainsCell(c Cell) bool
ContainsCell reports whether the given Cell is contained by this RegionUnion.
The current implementation only returns true if one of the regions in the union fully contains the cell.
func (RegionUnion) ContainsPoint ¶
func (ru RegionUnion) ContainsPoint(p Point) bool
ContainsPoint reports whether this RegionUnion contains the Point.
func (RegionUnion) IntersectsCell ¶
func (ru RegionUnion) IntersectsCell(c Cell) bool
IntersectsCell reports whether this RegionUnion intersects the given cell.
func (RegionUnion) RectBound ¶
func (ru RegionUnion) RectBound() Rect
RectBound returns a bounding latitudelongitude rectangle for this RegionUnion.
type Shape ¶
type Shape interface { // NumEdges returns the number of edges in this shape. NumEdges() int // Edge returns the edge for the given edge index. Edge(i int) Edge // ReferencePoint returns an arbitrary reference point for the shape. (The // containment boolean value must be false for shapes that do not have an interior.) // // This reference point may then be used to compute the containment of other // points by counting edge crossings. ReferencePoint() ReferencePoint // NumChains reports the number of contiguous edge chains in the shape. // For example, a shape whose edges are [AB, BC, CD, AE, EF] would consist // of two chains (AB,BC,CD and AE,EF). Every chain is assigned a chain Id // numbered sequentially starting from zero. // // Note that it is always acceptable to implement this method by returning // NumEdges, i.e. every chain consists of a single edge, but this may // reduce the efficiency of some algorithms. NumChains() int // Chain returns the range of edge IDs corresponding to the given edge chain. // Edge chains must form contiguous, nonoverlapping ranges that cover // the entire range of edge IDs. This is spelled out more formally below: // // 0 <= i < NumChains() // Chain(i).length > 0, for all i // Chain(0).start == 0 // Chain(i).start + Chain(i).length == Chain(i+1).start, for i < NumChains()1 // Chain(i).start + Chain(i).length == NumEdges(), for i == NumChains()1 Chain(chainID int) Chain // ChainEdgeReturns the edge at offset "offset" within edge chain "chainID". // Equivalent to "shape.Edge(shape.Chain(chainID).start + offset)" // but more efficient. ChainEdge(chainID, offset int) Edge // ChainPosition finds the chain containing the given edge, and returns the // position of that edge as a ChainPosition(chainID, offset) pair. // // shape.Chain(pos.chainID).start + pos.offset == edgeID // shape.Chain(pos.chainID+1).start > edgeID // // where pos == shape.ChainPosition(edgeID). ChainPosition(edgeID int) ChainPosition // Dimension returns the dimension of the geometry represented by this shape, // either 0, 1 or 2 for point, polyline and polygon geometry respectively. // // 0  Point geometry. Each point is represented as a degenerate edge. // // 1  Polyline geometry. Polyline edges may be degenerate. A shape may // represent any number of polylines. Polylines edges may intersect. // // 2  Polygon geometry. Edges should be oriented such that the polygon // interior is always on the left. In theory the edges may be returned // in any order, but typically the edges are organized as a collection // of edge chains where each chain represents one polygon loop. // Polygons may have degeneracies (e.g., degenerate edges or sibling // pairs consisting of an edge and its corresponding reversed edge). // A polygon loop may also be full (containing all points on the // sphere); by convention this is represented as a chain with no edges. // (See laxPolygon for details.) // // This method allows degenerate geometry of different dimensions // to be distinguished, e.g. it allows a point to be distinguished from a // polyline or polygon that has been simplified to a single point. Dimension() int // IsEmpty reports whether the Shape contains no points. (Note that the full // polygon is represented as a chain with zero edges.) IsEmpty() bool // IsFull reports whether the Shape contains all points on the sphere. IsFull() bool // contains filtered or unexported methods }
Shape represents polygonal geometry in a flexible way. It is organized as a collection of edges that optionally defines an interior. All geometry represented by a given Shape must have the same dimension, which means that an Shape can represent either a set of points, a set of polylines, or a set of polygons.
Shape is defined as an interface in order to give clients control over the underlying data representation. Sometimes an Shape does not have any data of its own, but instead wraps some other type.
Shape operations are typically defined on a ShapeIndex rather than individual shapes. An ShapeIndex is simply a collection of Shapes, possibly of different dimensions (e.g. 10 points and 3 polygons), organized into a data structure for efficient edge access.
The edges of a Shape are indexed by a contiguous range of edge IDs starting at 0. The edges are further subdivided into chains, where each chain consists of a sequence of edges connected endtoend (a polyline). For example, a Shape representing two polylines AB and CDE would have three edges (AB, CD, DE) grouped into two chains: (AB) and (CD, DE). Similarly, an Shape representing 5 points would have 5 chains consisting of one edge each.
Shape has methods that allow edges to be accessed either using the global numbering (edge ID) or within a particular chain. The global numbering is sufficient for most purposes, but the chain representation is useful for certain algorithms such as intersection (see BooleanOperation).
type ShapeEdge ¶
type ShapeEdge struct { ID ShapeEdgeID Edge Edge }
ShapeEdge represents a ShapeEdgeID with the two endpoints of that Edge.
type ShapeEdgeID ¶
ShapeEdgeID is a unique identifier for an Edge within an ShapeIndex, consisting of a (shapeID, edgeID) pair.
func (ShapeEdgeID) Cmp ¶
func (s ShapeEdgeID) Cmp(other ShapeEdgeID) int
Cmp compares the two ShapeEdgeIDs and returns
1 if s < other 0 if s == other +1 if s > other
The two are compared first by shape id and then by edge id.
type ShapeIndex ¶
type ShapeIndex struct {
// contains filtered or unexported fields
}
ShapeIndex indexes a set of Shapes, where a Shape is some collection of edges that optionally defines an interior. It can be used to represent a set of points, a set of polylines, or a set of polygons. For Shapes that have interiors, the index makes it very fast to determine which Shape(s) contain a given point or region.
The index can be updated incrementally by adding or removing shapes. It is designed to handle up to hundreds of millions of edges. All data structures are designed to be small, so the index is compact; generally it is smaller than the underlying data being indexed. The index is also fast to construct.
Polygon, Loop, and Polyline implement Shape which allows these objects to be indexed easily. You can find useful query methods in CrossingEdgeQuery and ClosestEdgeQuery (Not yet implemented in Go).
Example showing how to build an index of Polylines:
index := NewShapeIndex() for _, polyline := range polylines { index.Add(polyline); } // Now you can use a CrossingEdgeQuery or ClosestEdgeQuery here.
func (*ShapeIndex) Add ¶
func (s *ShapeIndex) Add(shape Shape) int32
Add adds the given shape to the index and returns the assigned ID..
func (*ShapeIndex) Begin ¶
func (s *ShapeIndex) Begin() *ShapeIndexIterator
Begin positions the iterator at the first cell in the index.
func (*ShapeIndex) Build ¶
func (s *ShapeIndex) Build()
Build triggers the update of the index. Calls to Add and Release are normally queued and processed on the first subsequent query. This has many advantages, the most important of which is that sometimes there *is* no subsequent query, which lets us avoid building the index completely.
This method forces any pending updates to be applied immediately.
func (*ShapeIndex) End ¶
func (s *ShapeIndex) End() *ShapeIndexIterator
End positions the iterator at the last cell in the index.
func (*ShapeIndex) IsFresh ¶
func (s *ShapeIndex) IsFresh() bool
IsFresh reports if there are no pending updates that need to be applied. This can be useful to avoid building the index unnecessarily, or for choosing between two different algorithms depending on whether the index is available.
The returned index status may be slightly out of date if the index was built in a different thread. This is fine for the intended use (as an efficiency hint), but it should not be used by internal methods.
func (*ShapeIndex) Iterator ¶
func (s *ShapeIndex) Iterator() *ShapeIndexIterator
Iterator returns an iterator for this index.
func (*ShapeIndex) Len ¶
func (s *ShapeIndex) Len() int
Len reports the number of Shapes in this index.
func (*ShapeIndex) NumEdges ¶
func (s *ShapeIndex) NumEdges() int
NumEdges returns the number of edges in this index.
func (*ShapeIndex) NumEdgesUpTo ¶
func (s *ShapeIndex) NumEdgesUpTo(limit int) int
NumEdgesUpTo returns the number of edges in the given index, up to the given limit. If the limit is encountered, the current running total is returned, which may be more than the limit.
func (*ShapeIndex) Region ¶
func (s *ShapeIndex) Region() *ShapeIndexRegion
Region returns a new ShapeIndexRegion for this ShapeIndex.
func (*ShapeIndex) Remove ¶
func (s *ShapeIndex) Remove(shape Shape)
Remove removes the given shape from the index.
func (*ShapeIndex) Reset ¶
func (s *ShapeIndex) Reset()
Reset resets the index to its original state.
func (*ShapeIndex) Shape ¶
func (s *ShapeIndex) Shape(id int32) Shape
Shape returns the shape with the given ID, or nil if the shape has been removed from the index.
type ShapeIndexCell ¶
type ShapeIndexCell struct {
// contains filtered or unexported fields
}
ShapeIndexCell stores the index contents for a particular CellID.
func NewShapeIndexCell ¶
func NewShapeIndexCell(numShapes int) *ShapeIndexCell
NewShapeIndexCell creates a new cell that is sized to hold the given number of shapes.
type ShapeIndexIterator ¶
type ShapeIndexIterator struct {
// contains filtered or unexported fields
}
ShapeIndexIterator is an iterator that provides lowlevel access to the cells of the index. Cells are returned in increasing order of CellID.
for it := index.Iterator(); !it.Done(); it.Next() { fmt.Print(it.CellID()) }
func NewShapeIndexIterator ¶
func NewShapeIndexIterator(index *ShapeIndex, pos ...ShapeIndexIteratorPos) *ShapeIndexIterator
NewShapeIndexIterator creates a new iterator for the given index. If a starting position is specified, the iterator is positioned at the given spot.
func (*ShapeIndexIterator) Begin ¶
func (s *ShapeIndexIterator) Begin()
Begin positions the iterator at the beginning of the index.
func (*ShapeIndexIterator) CellID ¶
func (s *ShapeIndexIterator) CellID() CellID
CellID returns the CellID of the current index cell. If s.Done() is true, a value larger than any valid CellID is returned.
func (*ShapeIndexIterator) Center ¶
func (s *ShapeIndexIterator) Center() Point
Center returns the Point at the center of the current position of the iterator.
func (*ShapeIndexIterator) Done ¶
func (s *ShapeIndexIterator) Done() bool
Done reports if the iterator is positioned at or after the last index cell.
func (*ShapeIndexIterator) End ¶
func (s *ShapeIndexIterator) End()
End positions the iterator at the end of the index.
func (*ShapeIndexIterator) IndexCell ¶
func (s *ShapeIndexIterator) IndexCell() *ShapeIndexCell
IndexCell returns the current index cell.
func (*ShapeIndexIterator) LocateCellID ¶
func (s *ShapeIndexIterator) LocateCellID(target CellID) CellRelation
LocateCellID attempts to position the iterator at the first matching index cell in the index that has some relation to the given CellID. Let T be the target CellID. If T is contained by (or equal to) some index cell I, then the iterator is positioned at I and returns Indexed. Otherwise if T contains one or more (smaller) index cells, then the iterator is positioned at the first such cell I and return Subdivided. Otherwise Disjoint is returned and the iterator position is undefined.
func (*ShapeIndexIterator) LocatePoint ¶
func (s *ShapeIndexIterator) LocatePoint(p Point) bool
LocatePoint positions the iterator at the cell that contains the given Point. If no such cell exists, the iterator position is unspecified, and false is returned. The cell at the matched position is guaranteed to contain all edges that might intersect the line segment between target and the cell's center.
func (*ShapeIndexIterator) Next ¶
func (s *ShapeIndexIterator) Next()
Next positions the iterator at the next index cell.
func (*ShapeIndexIterator) Prev ¶
func (s *ShapeIndexIterator) Prev() bool
Prev advances the iterator to the previous cell in the index and returns true to indicate it was not yet at the beginning of the index. If the iterator is at the first cell the call does nothing and returns false.
type ShapeIndexIteratorPos ¶
type ShapeIndexIteratorPos int
ShapeIndexIteratorPos defines the set of possible iterator starting positions. By default iterators are unpositioned, since this avoids an extra seek in this situation where one of the seek methods (such as Locate) is immediately called.
const ( // IteratorBegin specifies the iterator should be positioned at the beginning of the index. IteratorBegin ShapeIndexIteratorPos = iota // IteratorEnd specifies the iterator should be positioned at the end of the index. IteratorEnd )
type ShapeIndexRegion ¶
type ShapeIndexRegion struct {
// contains filtered or unexported fields
}
ShapeIndexRegion wraps a ShapeIndex and implements the Region interface. This allows RegionCoverer to work with ShapeIndexes as well as being able to be used by some of the Query types.
func (*ShapeIndexRegion) CapBound ¶
func (s *ShapeIndexRegion) CapBound() Cap
CapBound returns a bounding spherical cap for this collection of geometry. This is not guaranteed to be exact.
func (*ShapeIndexRegion) CellUnionBound ¶
func (s *ShapeIndexRegion) CellUnionBound() []CellID
CellUnionBound returns the bounding CellUnion for this collection of geometry. This method currently returns at most 4 cells, unless the index spans multiple faces in which case it may return up to 6 cells.
func (*ShapeIndexRegion) RectBound ¶
func (s *ShapeIndexRegion) RectBound() Rect
RectBound returns a bounding rectangle for this collection of geometry. The bounds are not guaranteed to be tight.
type Snapper ¶
type Snapper interface { // SnapRadius reports the maximum distance that vertices can move when snapped. // This requires that SnapRadius <= maxSnapRadius SnapRadius() s1.Angle // MaxEdgeDeviation returns the maximum distance that the center of an // edge can move when snapped. This is slightly larger than SnapRadius // because when a geodesic edge is snapped, the center of the edge moves // further than its endpoints. MaxEdgeDeviation() s1.Angle // MinVertexSeparation returns the guaranteed minimum distance between // vertices in the output. This is generally some fraction of SnapRadius. MinVertexSeparation() s1.Angle // MinEdgeVertexSeparation returns the guaranteed minimum spacing between // edges and nonincident vertices in the output. This is generally some // fraction of SnapRadius. MinEdgeVertexSeparation() s1.Angle // SnapPoint returns a candidate snap site for the given point. The final vertex // locations are a subset of the snap sites returned by this function // (spaced at least MinVertexSeparation apart). // // The only requirement is that SnapPoint(x) must return a point whose // distance from x is no greater than SnapRadius. SnapPoint(point Point) Point }
A Snapper restricts the locations of the output vertices. For example, there are predefined snap functions that require vertices to be located at CellID centers or at E5/E6/E7 coordinates. The Snapper can also specify a minimum spacing between vertices (i.e. the snap radius).
A Snapper defines the following methods:
1. The SnapPoint method, which snaps a point P to a nearby point (the
candidate snap site). Any point may be returned, including P itself (the identity snap function).
2. SnapRadius, the maximum distance that vertices can move when
snapped. The snapRadius must be at least as large as the maximum distance between P and SnapPoint(P) for any point P.
3. MaxEdgeDeviation, the maximum distance that edges can move when
snapped. It is slightly larger than snapRadius because when a geodesic edge is snapped, the center of the edge moves further than its endpoints. This value is computed automatically by Builder.
4. MinVertexSeparation, the guaranteed minimum distance between
vertices in the output. This is generally a fraction of snapRadius where the fraction depends on the snap function.
5. A MinEdgeVertexSeparation, the guaranteed minimum distance
between edges and nonincident vertices in the output. This is generally a fraction of snapRadius where the fraction depends on the snap function.
It is important to note that SnapPoint does not define the actual mapping from input vertices to output vertices, since the points it returns (the candidate snap sites) are further filtered to ensure that they are separated by at least the snap radius. For example, if you specify E7 coordinates (2cm resolution) and a snap radius of 10m, then a subset of points returned by SnapPoint will be chosen (the snap sites), and each input vertex will be mapped to the closest site. Therefore you cannot assume that P is necessarily snapped to SnapPoint(P).
Builder makes the following guarantees (within a small error margin):
1. Every vertex is at a location returned by SnapPoint.
2. Vertices are within snapRadius of the corresponding input vertex.
3. Edges are within maxEdgeDeviation of the corresponding input edge
(a distance slightly larger than snapRadius).
4. Vertices are separated by at least minVertexSeparation
(a fraction of snapRadius that depends on the snap function).
5. Edges and nonincident vertices are separated by at least
minEdgeVertexSeparation (a fraction of snapRadius).
6. Vertex and edge locations do not change unless one of the conditions
above is not already met (idempotency / stability).
7. The topology of the input geometry is preserved (up to the creation
of degeneracies). This means that there exists a continuous deformation from the input to the output such that no vertex crosses an edge.
type VertexModel ¶
type VertexModel int
VertexModel defines whether shapes are considered to contain their vertices. Note that these definitions differ from the ones used by BooleanOperation.
Note that points other than vertices are never contained by polylines. If you want need this behavior, use ClosestEdgeQuery's IsDistanceLess with a suitable distance threshold instead.
const ( // VertexModelOpen means no shapes contain their vertices (not even // points). Therefore Contains(Point) returns true if and only if the // point is in the interior of some polygon. VertexModelOpen VertexModel = iota // VertexModelSemiOpen means that polygon point containment is defined // such that if several polygons tile the region around a vertex, then // exactly one of those polygons contains that vertex. Points and // polylines still do not contain any vertices. VertexModelSemiOpen // VertexModelClosed means all shapes contain their vertices (including // points and polylines). VertexModelClosed )
type WedgeRel ¶
type WedgeRel int
WedgeRel enumerates the possible relation between two wedges A and B.
const ( WedgeEquals WedgeRel = iota // A and B are equal. WedgeProperlyContains // A is a strict superset of B. WedgeIsProperlyContained // A is a strict subset of B. WedgeProperlyOverlaps // AB, BA, and A intersect B are nonempty. WedgeIsDisjoint // A and B are disjoint. )
Define the different possible relationships between two wedges.
Given an edge chain (x0, x1, x2), the wedge at x1 is the region to the left of the edges. More precisely, it is the set of all rays from x1x0 (inclusive) to x1x2 (exclusive) in the *clockwise* direction.
func WedgeRelation ¶
WedgeRelation reports the relation between two nonempty wedges A=(a0, ab1, a2) and B=(b0, ab1, b2).
Source Files ¶
 bits_go19.go
 builder.go
 builder_snapper.go
 cap.go
 cell.go
 cell_index.go
 cellid.go
 cellunion.go
 centroids.go
 contains_point_query.go
 contains_vertex_query.go
 convex_hull_query.go
 crossing_edge_query.go
 distance_target.go
 doc.go
 edge_clipping.go
 edge_crosser.go
 edge_crossings.go
 edge_distances.go
 edge_query.go
 edge_tessellator.go
 encode.go
 interleave.go
 latlng.go
 lax_loop.go
 lax_polygon.go
 lax_polyline.go
 lexicon.go
 loop.go
 matrix3x3.go
 max_distance_targets.go
 metric.go
 min_distance_targets.go
 nthderivative.go
 paddedcell.go
 point.go
 point_measures.go
 point_vector.go
 pointcompression.go
 polygon.go
 polyline.go
 polyline_measures.go
 predicates.go
 projections.go
 query_entry.go
 query_options.go
 rect.go
 rect_bounder.go
 region.go
 regioncoverer.go
 regionunion.go
 shape.go
 shapeindex.go
 shapeindex_region.go
 shapeutil.go
 shapeutil_edge_iterator.go
 stuv.go
 util.go
 wedge_relations.go
Directories ¶
Path  Synopsis 

Package s2intersect efficiently finds common areas shared by sets of S2 CellUnions.

Package s2intersect efficiently finds common areas shared by sets of S2 CellUnions. 