s2

package
v0.0.0-...-40ad1ac Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 19, 2015 License: Apache-2.0 Imports: 10 Imported by: 0

Documentation

Overview

Package s2 implements types and functions for working with geometry in S² (spherical geometry).

Its related packages, parallel to this one, are s1 (operates on S¹), r1 (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).

A presentation that gives an overview of S2 is https://docs.google.com/presentation/d/1Hl4KapfAENAOf4gv-pSngKwvS_jwNVHRPZTTDzXXn6Q/view.

Index

Constants

View Source 
const (
	Clockwise        Direction = -1
	Indeterminate              = 0
	CounterClockwise           = 1
)

These are the three options for the direction of a set of points.

View Source 
const EPSILON float64 = 1e-14
View Source 
const EXPONENT_MASK uint64 = 0x7ff0000000000000

Mask to extract the exponent from a double.

View Source 
const EXPONENT_SHIFT uint = 52

Number of bits in the mantissa of a double.

View Source 
const (
	MAX_LEVEL = 30
)

TODO(dsymonds): Some of these constants should probably be exported.

Variables

View Source 
var (
	DEFAULT_MAX_CELLS int = 8

	FACE_CELLS = []Cell{
		CellFromCellID(CellIDFromFace(0)),
		CellFromCellID(CellIDFromFace(1)),
		CellFromCellID(CellIDFromFace(2)),
		CellFromCellID(CellIDFromFace(3)),
		CellFromCellID(CellIDFromFace(4)),
		CellFromCellID(CellIDFromFace(5)),
	}
)
View Source 
var MAX_DET_ERROR float64 = 1e-14
View Source 
var MAX_ERROR float64 = 1.0 / (1 << 51)

We grow the bounds slightly to make sure that the bounding rectangle also contains the normalized versions of the vertices. Note that the maximum result magnitude is Pi, with a floating-point exponent of 1. Therefore adding or subtracting 2**-51 will always change the result.

View Source 
var POLE_MIN_LAT float64 = math.Asin(math.Sqrt(1.0/3.0)) - MAX_ERROR // 35.26 degrees

The 4 cells around the equator extend to +/-45 degrees latitude at the midpoints of their top and bottom edges. The two cells covering the poles extend down to +/-35.26 degrees at their vertices. adding kMaxError (as opposed to the C version) because of asin and atan2 roundoff errors

View Source 
var THICKENING float64 = 0.01

Functions

func Area 

func Area(a, b, c Point) float64

*

  • Return the area of triangle ABC. The method used is about twice as
  • expensive as Girard's formula, but it is numerically stable for both large
  • and very small triangles. The points do not need to be normalized. The area
  • is always positive. *
  • The triangle area is undefined if it contains two antipodal points, and
  • becomes numerically unstable as the length of any edge approaches 180
  • degrees.

func AverageArea 

func AverageArea(level int) float64

*

  • Return the average area for cells at the given level.

func CCW 

func CCW(a, b, c Point) bool

CCW 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 CCW(a,b,c), then !CCW(c,b,a) for all a,b,c.

func ExpensiveCCW 

func ExpensiveCCW(a, b, c Point) int

*

  • A relatively expensive calculation invoked by RobustCCW() if the sign of
  • the determinant is uncertain.

func GetSimpleCovering 

func GetSimpleCovering(region Region, start Point, level int, output *[]CellID)

*

  • Given a connected region and a starting point, return a set of cells at the
  • given level that cover the region.

func GirardArea 

func GirardArea(a, b, c Point) float64

*

  • Return the area of the triangle computed using Girard's formula. This is
  • slightly faster than the Area() method above is not accurate for very small
  • triangles.

func LoopIsValid 

func LoopIsValid(vertices []Point) bool

*

  • Static version of isValid(), to be used only when an S2Loop instance is not
  • available, but validity of the points must be checked. *
  • @return true if the given loop is valid. Creates an instance of S2Loop and
  • defers this call to {@link #isValid()}.

func OrderedCCW 

func OrderedCCW(a, b, c, o Point) bool

*

  • Return 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 a continuous CCW ordering around O. *
  • Properties:
  • <ol>
  • <li>If orderedCCW(a,b,c,o) && orderedCCW(b,a,c,o), then a == b</li>
  • <li>If orderedCCW(a,b,c,o) && orderedCCW(a,c,b,o), then b == c</li>
  • <li>If orderedCCW(a,b,c,o) && orderedCCW(c,b,a,o), then a == b == c</li>
  • <li>If a == b or b == c, then orderedCCW(a,b,c,o) is true</li>
  • <li>Otherwise if a == c, then orderedCCW(a,b,c,o) is false</li>
  • </ol>

func PlanarCCW 

func PlanarCCW(a, b r2.Vector) int

func PlanarOrderedCCW 

func PlanarOrderedCCW(a, b, c r2.Vector) int

func PointArea 

func PointArea(a, b, c Point) float64

PointArea returns the area on the unit sphere for the triangle defined by the given points.

This method is based on l'Huilier's theorem, 

tan(E/4) = sqrt(tan(s/2) tan((s-a)/2) tan((s-b)/2) tan((s-c)/2))

where E is the spherical excess of the triangle (i.e. its area), 

a, b, c are the side lengths, and
s is the semiperimeter (a + b + c) / 2.

The only significant source of error using l'Huilier's method is the cancellation error of the terms (s-a), (s-b), (s-c). This leads to a *relative* error of about 1e-16 * s / min(s-a, s-b, s-c). This compares to a relative error of about 1e-15 / E using Girard's formula, where E is the true area of the triangle. Girard's formula can be even worse than this for very small triangles, e.g. a triangle with a true area of 1e-30 might evaluate to 1e-5.

So, we prefer l'Huilier's formula unless dmin < s * (0.1 * E), where dmin = min(s-a, s-b, s-c). This basically includes all triangles except for extremely long and skinny ones.

Since we don't know E, we would like a conservative upper bound on the triangle area in terms of s and dmin. It's possible to show that E <= k1 * s * sqrt(s * dmin), where k1 = 2*sqrt(3)/Pi (about 1). Using this, it's easy to show that we should always use l'Huilier's method if dmin >= k2 * s^5, where k2 is about 1e-2. Furthermore, if dmin < k2 * s^5, the triangle area is at most k3 * s^4, where k3 is about 0.1. Since the best case error using Girard's formula is about 1e-15, this means that we shouldn't even consider it unless s >= 3e-4 or so.

func RobustCCW 

func RobustCCW(a, b, c Point) int

*

  • WARNING! This requires arbitrary precision arithmetic to be truly robust.
  • This means that for nearly colinear AB and AC, this function may return the
  • wrong answer. *
  • <p>
  • Like SimpleCCW(), but returns +1 if the points are counterclockwise and -1
  • if the points are clockwise. It satisfies the following conditions: *
  • (1) RobustCCW(a,b,c) == 0 if and only if a == b, b == c, or c == a (2)
  • RobustCCW(b,c,a) == RobustCCW(a,b,c) for all a,b,c (3) RobustCCW(c,b,a)
  • ==-RobustCCW(a,b,c) for all a,b,c *
  • In other words: *
  • (1) The result is zero 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. *
  • This function is essentially like taking the sign of the determinant of
  • a,b,c, except that it 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 floating-point arithmetic. *
  • Note: a, b and c are expected to be of unit length. Otherwise, the results
  • are undefined.

func RobustCCWWithCross 

func RobustCCWWithCross(a, b, c, aCrossB Point) int

*

  • A more efficient version of RobustCCW that allows the precomputed
  • cross-product of A and B to be specified. *
  • Note: a, b and c are expected to be of unit length. Otherwise, the results
  • are undefined

func SignedArea 

func SignedArea(a, b, c Point) float64

*

  • Like Area(), but returns a positive value for counterclockwise triangles
  • and a negative value otherwise.

func VertexCrossing 

func VertexCrossing(a, b, c, d Point) bool

*

  • Given two edges AB and CD where at least two vertices are identical (i.e.
  • robustCrossing(a,b,c,d) == 0), this function defines whether the two edges
  • "cross" in a such a way that point-in-polygon containment tests can be
  • implemented by counting the number of edge crossings. 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.

Types

type AreaCentroid 

type AreaCentroid struct {
	// contains filtered or unexported fields
}

*

  • The area of an interior, i.e. the region on the left side of an odd
  • number of loops and optionally a centroid.
  • The area is between 0 and 4*Pi. If it has a centroid, it is
  • the true centroid of the interiord multiplied by the area of the shape.
  • Note that the centroid may not be contained by the shape. *
  • @author dbentley@google.com (Daniel Bentley)

func NewAreaCentroid 

func NewAreaCentroid(area float64, centroid *Point) AreaCentroid

func (AreaCentroid) GetArea 

func (ac AreaCentroid) GetArea() float64

func (AreaCentroid) GetCentroid 

func (ac AreaCentroid) GetCentroid() Point

type ByCellThenEdge 

type ByCellThenEdge struct {
	// contains filtered or unexported fields
}

func (ByCellThenEdge) Len 

func (s ByCellThenEdge) Len() int

func (ByCellThenEdge) Less 

func (s ByCellThenEdge) Less(i, j int) bool

func (ByCellThenEdge) Swap 

func (s ByCellThenEdge) Swap(i, j int)

type Cap 

type Cap struct {
	// contains filtered or unexported fields
}

Cap represents a disc-shaped 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 straight-line 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.)

Internally, the cap is represented by its center and "height". The height is the distance from the center point to the cutoff plane. This representation is much more efficient for containment tests than the (center, radius) representation. There is also support for "empty" and "full" caps, which contain no points and all points respectively.

The zero value of Cap is an invalid cap. Use EmptyCap to get a valid empty cap.

func CapFromCenterAngle 

func CapFromCenterAngle(center Point, angle s1.Angle) Cap

CapFromCenterAngle constructs a cap with the given center and angle.

func CapFromCenterArea 

func CapFromCenterArea(center Point, area float64) Cap

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 CapFromCenterHeight 

func CapFromCenterHeight(center Point, height float64) Cap

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.

func CapFromPoint 

func CapFromPoint(p Point) Cap

CapFromPoint constructs a cap containing a single point.

func EmptyCap 

func EmptyCap() Cap

EmptyCap returns a cap that contains no points.

func FullCap 

func FullCap() Cap

FullCap returns a cap that contains all points.

func (Cap) AddCap 

func (c Cap) AddCap(other Cap) Cap

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 

func (c Cap) AddPoint(p Point) Cap

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 unit-length.

func (Cap) ApproxEqual 

func (c Cap) ApproxEqual(other Cap) bool

ApproxEqual reports if this caps' center and height are within a reasonable epsilon from the other cap.

func (Cap) Area 

func (c Cap) Area() float64

Area returns the surface area of the Cap on the unit sphere.

func (Cap) CapBound 

func (c Cap) CapBound() Cap

CapBound returns a bounding spherical cap. This is not guaranteed to be exact.

func (Cap) Center 

func (c Cap) Center() Point

Center returns the cap's center or axis.

func (Cap) Complement 

func (c Cap) Complement() Cap

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) Contains 

func (c Cap) Contains(other Cap) bool

Contains reports whether this cap contains the other.

func (Cap) ContainsCell 

func (c Cap) ContainsCell(cell Cell) bool

ContainsCell reports whether the region completely contains the given region. It returns false if containment could not be determined.

func (Cap) ContainsPoint 

func (c Cap) ContainsPoint(p Point) bool

ContainsPoint reports whether this cap contains the point.

func (Cap) Expanded 

func (c Cap) Expanded(distance s1.Angle) Cap

Expanded returns a new cap expanded by the given angle. If the cap is empty, it returns an empty cap.

func (Cap) InteriorContainsPoint 

func (c Cap) InteriorContainsPoint(p Point) bool

InteriorContainsPoint reports whether the point is within the interior of this cap.

func (Cap) InteriorIntersects 

func (c Cap) InteriorIntersects(other Cap) bool

InteriorIntersects reports whether this caps interior intersects the other cap.

func (Cap) Intersects 

func (c Cap) Intersects(other Cap) bool

Intersects reports whether this cap intersects the other cap. i.e. whether they have any points in common.

func (Cap) IntersectsCell 

func (c Cap) IntersectsCell(cell 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.

func (Cap) IsEmpty 

func (c Cap) IsEmpty() bool

IsEmpty reports whether the cap is empty, i.e. it contains no points.

func (Cap) IsFull 

func (c Cap) IsFull() bool

IsFull reports whether the cap is full, i.e. it contains all points.

func (Cap) IsValid 

func (c Cap) IsValid() bool

IsValid reports whether the Cap is considered valid. Heights are normalized so that they do not exceed 2.

func (Cap) Radius 

func (c Cap) Radius() s1.Angle

Radius returns the cap's radius.

func (Cap) RectBound 

func (c Cap) RectBound() Rect

RectBound returns a bounding latitude-longitude rectangle. The bounds are not guaranteed to be tight.

func (Cap) String 

func (c Cap) String() string

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 

func CellFromCellID(id CellID) Cell

CellFromCellID constructs a Cell corresponding to the given CellID.

func CellFromLatLng 

func CellFromLatLng(ll LatLng) Cell

CellFromLatLng constructs a cell for the given LatLng.

func CellFromPoint 

func CellFromPoint(p Point) Cell

CellFromPoint constructs a cell for the given Point.

func (Cell) AverageArea 

func (c Cell) AverageArea() float64

*

  • Return the average area of cells at this level. This is accurate to within
  • a factor of 1.7 (for S2_QUADRATIC_PROJECTION) and is extremely cheap to
  • compute.

func (Cell) CapBound 

func (c Cell) CapBound() Cap

CapBound returns a bounding spherical cap. This is not guaranteed to be exact.

func (Cell) ContainsCell 

func (c Cell) ContainsCell(other Cell) bool

ContainsCell reports whether the region completely contains the given region. It returns false if containment could not be determined.

func (Cell) ContainsPoint 

func (c Cell) ContainsPoint(point Point) bool

func (Cell) Edge 

func (c Cell) Edge(k int) Point

Edge returns the inward-facing normal of the great circle passing through the CCW ordered edge from vertex k to vertex k+1 (mod 4).

func (Cell) EdgeRaw 

func (c Cell) EdgeRaw(k int) Point

func (Cell) ExactArea 

func (c Cell) ExactArea() float64

ExactArea return the area of this cell as accurately as possible.

func (Cell) Face 

func (c Cell) Face() int8

func (Cell) Id 

func (c Cell) Id() CellID

func (Cell) IntersectsCell 

func (c Cell) IntersectsCell(other 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.

func (Cell) IsLeaf 

func (c Cell) IsLeaf() bool

IsLeaf returns whether this Cell is a leaf or not.

func (Cell) Level 

func (c Cell) Level() int8

func (Cell) Orientation 

func (c Cell) Orientation() int8

func (Cell) RectBound 

func (c Cell) RectBound() Rect

RectBound returns a bounding latitude-longitude rectangle that contains the region. The bounds are not guaranteed to be tight.

func (Cell) SizeIJ 

func (c Cell) SizeIJ() int

SizeIJ returns the CellID value for the cells level.

func (Cell) Vertex 

func (c Cell) Vertex(k int) Point

Vertex returns the k-th vertex of the cell (k = [0,3]) in CCW order (lower left, lower right, upper right, upper left in the UV plane).

type CellID 

type CellID uint64

CellID uniquely identifies a cell in the S2 cell decomposition. The most significant 3 bits encode the face number (0-5). 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.

func CellIDBegin 

func CellIDBegin(level int) CellID

func CellIDEnd 

func CellIDEnd(level int) CellID

func CellIDFromFace 

func CellIDFromFace(face int) CellID

CellIDFromFace returns the cell corresponding to a given S2 cube face.

func CellIDFromFacePosLevel 

func CellIDFromFacePosLevel(face int, pos uint64, level int) CellID

CellIDFromFacePosLevel returns a cell given its face in the range [0,5], the 61-bit 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 

func CellIDFromLatLng(ll LatLng) CellID

CellIDFromLatLng returns the leaf cell containing ll.

func CellIDFromPoint 

func CellIDFromPoint(p Point) CellID

CellIDFromPoint returns the leaf cell containing point p.

func CellIDFromToken 

func CellIDFromToken(s string) CellID

CellIDFromToken returns a cell given a hex-encoded string of its uint64 ID.

func CellIDNone 

func CellIDNone() CellID

func CellIDSentinel 

func CellIDSentinel() CellID

func (CellID) ChildBegin 

func (ci CellID) ChildBegin() CellID

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 

func (ci CellID) ChildBeginAtLevel(level int) CellID

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.

func (CellID) ChildEnd 

func (ci CellID) ChildEnd() CellID

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 

func (ci CellID) ChildEndAtLevel(level int) CellID

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 

func (ci CellID) ChildPosition(level int) int

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 level-1 ancestor within its top-level face cell.

func (CellID) Children 

func (ci CellID) Children() [4]CellID

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) Contains 

func (ci CellID) Contains(oci CellID) bool

Contains returns true iff the CellID contains oci.

func (CellID) EdgeNeighbors 

func (ci CellID) EdgeNeighbors() [4]CellID

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) Face 

func (ci CellID) Face() int

Face returns the cube face for this cell ID, in the range [0,5].

func (CellID) Intersects 

func (ci CellID) Intersects(oci CellID) bool

Intersects returns true iff the CellID intersects oci.

func (CellID) IsLeaf 

func (ci CellID) IsLeaf() bool

IsLeaf returns whether this cell ID is at the deepest level; that is, the level at which the cells are smallest.

func (CellID) IsValid 

func (ci CellID) IsValid() bool

IsValid reports whether ci represents a valid cell.

func (CellID) LatLng 

func (ci CellID) LatLng() LatLng

LatLng returns the center of the s2 cell on the sphere as a LatLng.

func (CellID) Level 

func (ci CellID) Level() int

Level returns the subdivision level of this cell ID, in the range [0, maxLevel].

func (CellID) Next 

func (ci CellID) Next() CellID

Next returns the next cell along the Hilbert curve. This is expected to be used with ChildStart and ChildEnd.

func (CellID) Parent 

func (ci CellID) Parent(level int) CellID

Parent returns the cell at the given level, which must be no greater than the current level.

func (CellID) Point 

func (ci CellID) Point() Point

Point returns the center of the s2 cell on the sphere as a Point.

func (CellID) Pos 

func (ci CellID) Pos() uint64

Pos returns the position along the Hilbert curve of this cell ID, in the range [0,2^posBits-1].

func (CellID) Prev 

func (ci CellID) Prev() CellID

Prev returns the previous cell along the Hilbert curve.

func (CellID) RangeMax 

func (ci CellID) RangeMax() CellID

RangeMax returns the maximum CellID that is contained within this cell.

func (CellID) RangeMin 

func (ci CellID) RangeMin() CellID

RangeMin returns the minimum CellID that is contained within this cell.

func (CellID) String 

func (ci CellID) String() string

String returns the string representation of the cell ID in the form "1/3210".

func (CellID) ToString 

func (ci CellID) ToString() string

func (CellID) ToToken 

func (ci CellID) ToToken() string

ToToken returns a hex-encoded string of the uint64 cell id, with leading zeros included but trailing zeros stripped.

func (CellID) VertexNeighbors 

func (ci CellID) VertexNeighbors(level int) []CellID

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 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.

func CellUnionFromArrayAndSwap 

func CellUnionFromArrayAndSwap(ids *[]CellID) *CellUnion

func CellUnionFromCellIDs 

func CellUnionFromCellIDs(ids []CellID) *CellUnion

func (*CellUnion) Contains 

func (cu *CellUnion) Contains(id CellID) bool

*

  • Return true if the cell union contains the given cell id. Containment is
  • defined with respect to regions, e.g. a cell contains its 4 children. This
  • is a fast operation (logarithmic in the size of the cell union).

func (*CellUnion) DeNormalize 

func (cu *CellUnion) DeNormalize(minLevel, levelMod int, output *[]CellID)

func (*CellUnion) Intersects 

func (cu *CellUnion) Intersects(id CellID) bool

Intersects reports whether this cell union intersects the given cell ID.

This method assumes that the CellUnion has been normalized.

func (*CellUnion) Normalize 

func (cu *CellUnion) Normalize()

Normalize normalizes the CellUnion.

type DataEdgeIterator 

type DataEdgeIterator struct {
	// contains filtered or unexported fields
}

* An iterator on data edges that may cross a query edge (a,b). Create the * iterator, call getCandidates(), then hasNext()/next() repeatedly. * * The current edge in the iteration has index index(), goes between from() * and to().

func NewDataEdgeIterator 

func NewDataEdgeIterator(edgeIndex *EdgeIndex) *DataEdgeIterator

func (*DataEdgeIterator) GetCandidates 

func (d *DataEdgeIterator) GetCandidates(a, b Point)

*

  • Initializes the iterator to iterate over a set of candidates that may
  • cross the edge (a,b).

func (*DataEdgeIterator) HasNext 

func (d *DataEdgeIterator) HasNext() bool

*

  • False if there are no more candidates; true otherwise.

func (*DataEdgeIterator) Index 

func (d *DataEdgeIterator) Index() int

*

  • Index of the current edge in the iteration.

func (*DataEdgeIterator) Next 

func (d *DataEdgeIterator) Next()

*

  • Iterate to the next available candidate.

type Direction 

type Direction int

Direction is an indication of the ordering of a set of points

func RobustSign 

func RobustSign(a, b, c Point) Direction

RobustSign returns a Direction representing the ordering of the points. CounterClockwise is returned if the points are in counter-clockwise 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 floating-point arithmetic.

RobustSign satisfies the following conditions: 

(1) RobustSign(a,b,c) == 0 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 zero 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.

C++ Equivalent: RobustCCW()

type Edge 

type Edge struct {
	// contains filtered or unexported fields
}

func NewEdgeFromStartEnd 

func NewEdgeFromStartEnd(start, end Point) Edge

func (Edge) End 

func (e Edge) End() Point

func (Edge) Equals 

func (e Edge) Equals(other Edge) bool

func (Edge) Start 

func (e Edge) Start() Point

func (Edge) String 

func (e Edge) String() string

type EdgeCrosser 

type EdgeCrosser struct {
	// contains filtered or unexported fields
}

func NewEdgeCrosser 

func NewEdgeCrosser(a, b, c Point) *EdgeCrosser

func (*EdgeCrosser) EdgeOrVertexCrossing 

func (ec *EdgeCrosser) EdgeOrVertexCrossing(d Point) bool

*

  • This method is equivalent to the S2EdgeUtil.edgeOrVertexCrossing() method
  • defined below. It is similar to robustCrossing, but handles cases where
  • two vertices are identical in a way that makes it easy to implement
  • point-in-polygon containment tests.

func (*EdgeCrosser) RestartAt 

func (ec *EdgeCrosser) RestartAt(c Point)

func (*EdgeCrosser) RobustCrossing 

func (ec *EdgeCrosser) RobustCrossing(d Point) int

*

  • This method is equivalent to calling the S2EdgeUtil.robustCrossing()
  • function (defined below) on the edges AB and CD. It returns +1 if there
  • is a crossing, -1 if there is no crossing, and 0 if two points from
  • different edges are the same. Returns 0 or -1 if either edge is
  • degenerate. As a side effect, it saves vertex D to be used as the next
  • vertex C.

type EdgeIndex 

type EdgeIndex struct {
	// contains filtered or unexported fields
}

func NewEdgeIndex 

func NewEdgeIndex(getNumEdges func() int, edgeFrom func(int) Point, edgeTo func(int) Point) *EdgeIndex

func (*EdgeIndex) ComputeIndex 

func (e *EdgeIndex) ComputeIndex()

* Computes the index (if it has not been previously done).

func (*EdgeIndex) IsIndexComputed 

func (e *EdgeIndex) IsIndexComputed() bool

func (*EdgeIndex) PredictAdditionalCalls 

func (e *EdgeIndex) PredictAdditionalCalls(n int)

*

  • If the index hasn't been computed yet, looks at how much work has gone into
  • iterating using the brute force method, and how much more work is planned
  • as defined by 'cost'. If it were to have been cheaper to use a quad tree
  • from the beginning, then compute it now. This guarantees that we will never
  • use more than twice the time we would have used had we known in advance
  • exactly how many edges we would have wanted to test. It is the theoretical
  • best. *
  • The value 'n' is the number of iterators we expect to request from this
  • edge index. *
  • If we have m data edges and n query edges, then the brute force cost is m
  • * n * testCost where testCost is taken to be the cost of
  • EdgeCrosser.robustCrossing, measured to be about 30ns at the time of this
  • writing. *
  • If we compute the index, the cost becomes: m * costInsert + n *
  • costFind(m) *
  • - costInsert can be expected to be reasonably stable, and was measured at
  • 1200ns with the BM_QuadEdgeInsertionCost benchmark. *
  • - costFind depends on the length of the edge . For m=1000 edges, we got
  • timings ranging from 1ms (edge the length of the polygon) to 40ms. The
  • latter is for very long query edges, and needs to be optimized. We will
  • assume for the rest of the discussion that costFind is roughly 3ms. *
  • When doing one additional query, the differential cost is m * testCost -
  • costFind(m) With the numbers above, it is better to use the quad tree (if
  • we have it) if m >= 100. *
  • If m = 100, 30 queries will give m*n*testCost = m * costInsert = 100ms,
  • while the marginal cost to find is 3ms. Thus, this is a reasonable thing to
  • do.

func (*EdgeIndex) Reset 

func (e *EdgeIndex) Reset()

*

  • Empties the index in case it already contained something.

type LatLng 

type LatLng struct {
	Lat, Lng s1.Angle
}

LatLng represents a point on the unit sphere as a pair of angles.

func LatLngFromDegrees 

func LatLngFromDegrees(lat, lng float64) LatLng

LatLngFromDegrees returns a LatLng for the coordinates given in degrees.

func LatLngFromPoint 

func LatLngFromPoint(p Point) LatLng

LatLngFromPoint returns an LatLng for a given Point.

func (LatLng) Distance 

func (ll LatLng) Distance(ll2 LatLng) s1.Angle

Distance returns the angle between two LatLngs.

func (LatLng) IsValid 

func (ll LatLng) IsValid() bool

IsValid returns true iff the LatLng is normalized, with Lat ∈ [-π/2,π/2] and Lng ∈ [-π,π].

func (LatLng) String 

func (ll LatLng) String() string

func (LatLng) StringDegrees 

func (ll LatLng) StringDegrees() string

type Loop 

type Loop struct {
	// contains filtered or unexported fields
}

* 

*
* An S2Loop represents a simple spherical polygon. It consists of a single
* chain 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
* polygon 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), and non-adjacent edges are not allowed to intersect. Loops must have at
* least 3 vertices. Although these restrictions are not enforced in optimized
* code, you may get unexpected results if they are violated.
*
*  Point containment is defined such that if the sphere is subdivided into
* faces (loops), every point is contained by exactly one face. This implies
* that loops do not necessarily contain all (or any) of their vertices An
* S2LatLngRect represents a latitude-longitude rectangle. It is capable of
* representing the empty and full rectangles as well as single points.
*

func LoopFromCell 

func LoopFromCell(cell Cell) *Loop

func LoopFromCellAndRect 

func LoopFromCellAndRect(cell Cell, bound Rect) *Loop

func LoopFromPoints 

func LoopFromPoints(points []Point) *Loop

func (*Loop) BoundaryApproxEquals 

func (l *Loop) BoundaryApproxEquals(b *Loop, maxError float64) bool

*

  • Returns true if two loops have the same boundary except for vertex
  • perturbations. More precisely, the vertices in the two loops must be in the
  • same cyclic order, and corresponding vertex pairs must be separated by no
  • more than maxError. Note: This method mostly useful only for testing
  • purposes.

func (*Loop) CapBound 

func (l *Loop) CapBound() Cap

CapBound returns a bounding spherical cap. This is not guaranteed to be exact.

func (*Loop) CompareTo 

func (l *Loop) CompareTo(other *Loop) int

func (*Loop) ContainsCell 

func (l *Loop) ContainsCell(cell Cell) bool

*

  • If this method returns true, the region completely contains the given cell.
  • Otherwise, either the region does not contain the cell or the containment
  • relationship could not be determined.

func (*Loop) ContainsLoop 

func (l *Loop) ContainsLoop(b *Loop) bool

func (*Loop) ContainsNested 

func (l *Loop) ContainsNested(b *Loop) bool

*

  • Given two loops of a polygon, return true if A contains B. This version of
  • contains() is much cheaper since it does not need to check whether the
  • boundaries of the two loops cross.

func (*Loop) ContainsOrCrosses 

func (l *Loop) ContainsOrCrosses(b *Loop) int

*

  • Return +1 if A contains B (i.e. the interior of B is a subset of the
  • interior of A), -1 if the boundaries of A and B cross, and 0 otherwise.
  • Requires that A does not properly contain the complement of B, i.e. A and B
  • do not contain each other's boundaries. This method is used for testing
  • whether multi-loop polygons contain each other.

func (*Loop) ContainsPoint 

func (l *Loop) ContainsPoint(p Point) bool

*

  • The point 'p' does not need to be normalized.

func (*Loop) Depth 

func (l *Loop) Depth() int

func (*Loop) GetArea 

func (l *Loop) GetArea() float64

*

  • Return 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 (*Loop) GetAreaAndCentroid 

func (l *Loop) GetAreaAndCentroid() AreaCentroid

*

  • Return 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 and the true centroid of
  • the loop multiplied by the area of the loop (see S2.java for details on
  • centroids). Note that the centroid may not be contained by the loop.

func (*Loop) GetCentroid 

func (l *Loop) GetCentroid() Point

*

  • Return the true centroid of the polygon multiplied by the area of the
  • polygon (see {@link S2} for details on centroids). Note that the centroid
  • may not be contained by the polygon.

func (*Loop) GetDistance 

func (l *Loop) GetDistance(p Point) s1.Angle

*

  • Returns the shortest distance from a point P to this loop, given as the
  • angle formed between P, the origin and the nearest point on the loop to P.
  • This angle in radians is equivalent to the arclength along the unit sphere.

func (*Loop) IntersectsCell 

func (l *Loop) IntersectsCell(cell Cell) bool

*

  • If this method returns false, the region does not intersect the given cell.
  • Otherwise, either region intersects the cell, or the intersection
  • relationship could not be determined.

func (*Loop) IntersectsLoop 

func (l *Loop) IntersectsLoop(b *Loop) bool

*

  • Return true if the region contained by this loop intersects the region
  • contained by the given other loop.

func (*Loop) Invert 

func (l *Loop) Invert()

*

  • Reverse the order of the loop vertices, effectively complementing the
  • region represented by the loop.

func (*Loop) IsHole 

func (l *Loop) IsHole() bool

*

  • Return true if this loop represents a hole in its containing polygon.

func (*Loop) IsNormalized 

func (l *Loop) IsNormalized() bool

*

  • Return true if the loop area is at most 2*Pi.

func (*Loop) IsValid 

func (l *Loop) IsValid() bool

* Return true if this loop is valid.

func (*Loop) Normalize 

func (l *Loop) Normalize()

*

  • Invert the loop if necessary so that the area enclosed by the loop is at
  • most 2*Pi.

func (*Loop) NumVertices 

func (l *Loop) NumVertices() int

func (*Loop) RectBound 

func (l *Loop) RectBound() Rect

RectBound returns a bounding latitude-longitude rectangle that contains the region. The bounds are not guaranteed to be tight.

func (*Loop) SetDepth 

func (l *Loop) SetDepth(depth int)

*

  • The depth of a loop is defined as its nesting level within its containing
  • polygon. "Outer shell" loops have depth 0, holes within those loops have
  • depth 1, shells within those holes have depth 2, etc. This field is only
  • used by the S2Polygon implementation. *
  • @param depth

func (*Loop) Sign 

func (l *Loop) Sign() int

*

  • The sign of a loop is -1 if the loop represents a hole in its containing
  • polygon, and +1 otherwise.

func (*Loop) ToString 

func (l *Loop) ToString() string

func (*Loop) Vertex 

func (l *Loop) Vertex(i int) Point

*

  • For convenience, we make two entire copies of the vertex list available:
  • vertex(n..2*n-1) is mapped to vertex(0..n-1), where n == numVertices().

type Metric 

type Metric struct {
	// contains filtered or unexported fields
}

Defines an area or a length cell metric.

func NewMetric 

func NewMetric(dim uint, deriv float64) Metric

Defines a cell metric of the given dimension (1 == length, 2 == area).

func (Metric) Deriv 

func (m Metric) Deriv() float64

The "deriv" value of a metric is a derivative, and must be multiplied by a length or area in (s,t)-space to get a useful value.

func (Metric) GetValue 

func (m Metric) GetValue(level int) float64

Return the value of a metric for cells at the given level.

type Point 

type Point struct {
	r3.Vector
}

Point represents a point on the unit sphere as a normalized 3D vector.

Points are guaranteed to be close to normal in the sense that the norm of any points will be very close to 1.

Fields should be treated as read-only. Use one of the factory methods for creation.

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 point-in-polygon 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 low-level S2Cell for the same reason.

func PlanarCentroid 

func PlanarCentroid(a, b, c Point) Point

*

  • Return 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" (see example above).

func PointFromCoords 

func PointFromCoords(x, y, z float64) Point

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 PointFromCoordsRaw 

func PointFromCoordsRaw(x, y, z float64) Point

func PointFromLatLng 

func PointFromLatLng(ll LatLng) Point

PointFromLatLng returns an Point for the given LatLng.

func TrueCentroid 

func TrueCentroid(a, b, c Point) Point

*

  • 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.

func (Point) ApproxEquals 

func (p Point) ApproxEquals(other Point, maxError float64) bool

ApproxEqual reports if the two points are similar enough to be equal.

func (Point) CompareTo 

func (p Point) CompareTo(other Point) int

func (Point) DegreesString 

func (p Point) DegreesString() string

func (Point) Distance 

func (p Point) Distance(b Point) s1.Angle

Distance returns the angle between two points.

func (Point) Equals 

func (p Point) Equals(other Point) bool

func (Point) LessThan 

func (p Point) LessThan(vb Point) bool

func (Point) PointCross 

func (p Point) PointCross(op Point) Point

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 non-zero result even when p == op or p == -op and the result is a Point, so it will have norm 1.

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 Polyline 

type Polyline struct {
	Vertices []Point
}

*

  • A 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. *
  • <p>Note: Polylines do not have a Contains(S2Point) method, because
  • "containment" is not numerically well-defined except at the polyline
  • vertices.

func PolylineFromPoints 

func PolylineFromPoints(points []Point) Polyline

func (Polyline) CapBound 

func (p Polyline) CapBound() Cap

CapBound returns a bounding spherical cap. This is not guaranteed to be exact.

func (Polyline) ContainsCell 

func (p Polyline) ContainsCell(cell Cell) bool

ContainsCell reports whether the region completely contains the given region. It returns false if containment could not be determined.

func (Polyline) GetArclengthAngle 

func (p Polyline) GetArclengthAngle() s1.Angle

Return the angle corresponding to the total arclength of the polyline on a unit sphere.

func (Polyline) IntersectsCell 

func (p Polyline) IntersectsCell(cell 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.

func (Polyline) IsValid 

func (p Polyline) IsValid() bool

Return true if the given vertices form a valid polyline.

func (Polyline) NumVertices 

func (p Polyline) NumVertices() int

func (Polyline) RectBound 

func (p Polyline) RectBound() Rect

RectBound returns a bounding latitude-longitude rectangle that contains the region. The bounds are not guaranteed to be tight.

func (Polyline) Vertex 

func (p Polyline) Vertex(k int) Point

type PriorityQueue 

type PriorityQueue []*queueEntry

A PriorityQueue implements heap.Interface and holds Items.

func (PriorityQueue) Len 

func (pq PriorityQueue) Len() int

func (*PriorityQueue) Pop 

func (pq *PriorityQueue) Pop() interface{}

func (*PriorityQueue) Push 

func (pq *PriorityQueue) Push(x interface{})

type Projections 

type Projections interface {
	MIN_AREA() Metric
	MAX_AREA() Metric
	AVG_AREA() Metric

	MIN_ANGLE_SPAN() Metric
	MAX_ANGLE_SPAN() Metric
	AVG_ANGLE_SPAN() Metric

	MIN_WIDTH() Metric
	MAX_WIDTH() Metric
	AVG_WIDTH() Metric

	MIN_EDGE() Metric
	MAX_EDGE() Metric
	AVG_EDGE() Metric

	MIN_DIAG() Metric
	MAX_DIAG() Metric
	AVG_DIAG() Metric

	MAX_EDGE_ASPECT() float64
	MAX_DIAG_ASPECT() float64
}
var (

	// Uncomment the desirect projection type
	// S2_PROJECTION Projections = S2_LINEAR_PROJECTION{}
	// S2_PROJECTION Projections = S2_TAN_PROJECTION{}
	S2_PROJECTION Projections = S2_QUADRATIC_PROJECTION{}
)

type Rect 

type Rect struct {
	Lat r1.Interval
	Lng s1.Interval
}

Rect represents a closed latitude-longitude rectangle.

func EmptyRect 

func EmptyRect() Rect

EmptyRect returns the empty rectangle.

func FullRect 

func FullRect() Rect

FullRect returns the full rectangle.

func RectFromCenterSize 

func RectFromCenterSize(center, size LatLng) Rect

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 

func RectFromLatLng(p LatLng) Rect

RectFromLatLng constructs a rectangle containing a single point p.

func RectFromLatLngLoHi 

func RectFromLatLngLoHi(lo, hi LatLng) Rect

func RectFromLatLngPointPair 

func RectFromLatLngPointPair(p1, p2 LatLng) Rect

*

  • Convenience method to construct the minimal bounding rectangle containing
  • the two given points. This is equivalent to starting with an empty
  • rectangle and calling AddPoint() twice. Note that it is different than the
  • S2LatLngRect(lo, hi) constructor, where the first point is always used as
  • the lower-left corner of the resulting rectangle.

func (Rect) AddPoint 

func (r Rect) AddPoint(ll LatLng) Rect

AddPoint increases the size of the rectangle to include the given point.

func (Rect) Area 

func (r Rect) Area() float64

Area returns the surface area of the Rect.

func (Rect) CapBound 

func (r Rect) CapBound() Cap

CapBound returns a bounding spherical cap. This is not guaranteed to be exact.

func (Rect) Center 

func (r Rect) Center() LatLng

Center returns the center of the rectangle.

func (Rect) ContainsCell 

func (r Rect) ContainsCell(c Cell) bool

func (Rect) ContainsLatLng 

func (r Rect) ContainsLatLng(ll LatLng) bool

ContainsLatLng reports whether the given LatLng is within the Rect.

func (Rect) ContainsRect 

func (r Rect) ContainsRect(other Rect) bool

Return true if and only if the rectangle contains the given other rectangle.

func (Rect) Hi 

func (r Rect) Hi() LatLng

Hi returns the other corner of the rectangle.

func (Rect) IntersectsCell 

func (r Rect) IntersectsCell(c Cell) bool

*

  • This test is cheap but is NOT exact. Use Intersects() if you want a more
  • accurate and more expensive test. Note that when this method is used by an
  • S2RegionCoverer, the accuracy isn't all that important since if a cell may
  • intersect the region then it is subdivided, and the accuracy of this method
  • goes up as the cells get smaller.

func (Rect) IntersectsRect 

func (r Rect) IntersectsRect(other Rect) bool

Return true if this rectangle and the given other rectangle have any points in common.

func (Rect) IsEmpty 

func (r Rect) IsEmpty() bool

IsEmpty reports whether the rectangle is empty.

func (Rect) IsFull 

func (r Rect) IsFull() bool

IsFull reports whether the rectangle is full.

func (Rect) IsPoint 

func (r Rect) IsPoint() bool

IsPoint reports whether the rectangle is a single point.

func (Rect) IsValid 

func (r Rect) IsValid() bool

IsValid returns true iff the rectangle is valid. This requires Lat ⊆ [-π/2,π/2] and Lng ⊆ [-π,π], and Lat = ∅ iff Lng = ∅

func (Rect) Lo 

func (r Rect) Lo() LatLng

Lo returns one corner of the rectangle.

func (Rect) RectBound 

func (r Rect) RectBound() Rect

RectBound returns a bounding latitude-longitude rectangle that contains the region. The bounds are not guaranteed to be tight.

func (Rect) Size 

func (r Rect) Size() LatLng

Size returns the size of the Rect.

func (Rect) String 

func (r Rect) String() string

func (Rect) Union 

func (r Rect) Union(other Rect) Rect

Return the smallest rectangle containing the union of this rectangle and the given rectangle.

func (Rect) Vertex 

func (r Rect) Vertex(k int) LatLng

Return the k-th vertex of the rectangle (k = 0,1,2,3) in CCW order.

type RectBounder 

type RectBounder struct {
	// contains filtered or unexported fields
}

func NewRectBounder 

func NewRectBounder() *RectBounder

func (*RectBounder) AddPoint 

func (rb *RectBounder) AddPoint(b Point)

func (*RectBounder) GetBound 

func (rb *RectBounder) GetBound() Rect

type Region 

type Region interface {
	// CapBound returns a bounding spherical cap. This is not guaranteed to be exact.
	CapBound() Cap

	// RectBound returns a bounding latitude-longitude 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
}

A Region represents a two-dimensional 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 {
	// contains filtered or unexported fields
}

func NewRegionCoverer 

func NewRegionCoverer() *RegionCoverer

func (*RegionCoverer) GetCovering 

func (rc *RegionCoverer) GetCovering(region Region, covering *[]CellID)

*

  • Computes a list of cell ids that covers the given region and satisfies the
  • various restrictions specified above. *
  • @param region The region to cover
  • @param covering The list filled in by this method

func (*RegionCoverer) GetCoveringAsUnion 

func (rc *RegionCoverer) GetCoveringAsUnion(region Region) *CellUnion

*

  • Return a normalized cell union that covers the given region and satisfies
  • the restrictions *EXCEPT* for min_level() and level_mod(). 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 cell union
  • constructor does in fact satisfy all the given restrictions.)

func (*RegionCoverer) GetCoveringInternal 

func (rc *RegionCoverer) GetCoveringInternal(region Region)

* Generates a covering and stores it in result.

func (*RegionCoverer) GetInteriorCovering 

func (rc *RegionCoverer) GetInteriorCovering(region Region, interior *[]CellID)

*

  • Computes a list of cell ids that is contained within the given region and
  • satisfies the various restrictions specified above. *
  • @param region The region to fill
  • @param interior The list filled in by this method

func (*RegionCoverer) GetInteriorCoveringAsUnion 

func (rc *RegionCoverer) GetInteriorCoveringAsUnion(region Region) *CellUnion

*

  • Return a normalized cell union that is contained within the given region
  • and satisfies the restrictions *EXCEPT* for min_level() and level_mod().

func (*RegionCoverer) LevelMod 

func (rc *RegionCoverer) LevelMod() int

func (*RegionCoverer) MaxCells 

func (rc *RegionCoverer) MaxCells() int

func (*RegionCoverer) MaxLevel 

func (rc *RegionCoverer) MaxLevel() int

func (*RegionCoverer) MinLevel 

func (rc *RegionCoverer) MinLevel() int

func (*RegionCoverer) SetLevelMod 

func (rc *RegionCoverer) SetLevelMod(levelMod int)

func (*RegionCoverer) SetMaxCells 

func (rc *RegionCoverer) SetMaxCells(maxCells int)

func (*RegionCoverer) SetMaxLevel 

func (rc *RegionCoverer) SetMaxLevel(maxLevel int)

func (*RegionCoverer) SetMinLevel 

func (rc *RegionCoverer) SetMinLevel(minLevel int)

type S2_PROJECTION_COMMON 

type S2_PROJECTION_COMMON struct{}

func (S2_PROJECTION_COMMON) AVG_ANGLE_SPAN 

func (m S2_PROJECTION_COMMON) AVG_ANGLE_SPAN() Metric

func (S2_PROJECTION_COMMON) AVG_AREA 

func (m S2_PROJECTION_COMMON) AVG_AREA() Metric

func (S2_PROJECTION_COMMON) MAX_DIAG_ASPECT 

func (m S2_PROJECTION_COMMON) MAX_DIAG_ASPECT() float64

type S2_QUADRATIC_PROJECTION 

type S2_QUADRATIC_PROJECTION struct{ S2_PROJECTION_COMMON }

func (S2_QUADRATIC_PROJECTION) AVG_DIAG 

func (m S2_QUADRATIC_PROJECTION) AVG_DIAG() Metric

func (S2_QUADRATIC_PROJECTION) AVG_EDGE 

func (m S2_QUADRATIC_PROJECTION) AVG_EDGE() Metric

func (S2_QUADRATIC_PROJECTION) AVG_WIDTH 

func (m S2_QUADRATIC_PROJECTION) AVG_WIDTH() Metric

func (S2_QUADRATIC_PROJECTION) MAX_ANGLE_SPAN 

func (m S2_QUADRATIC_PROJECTION) MAX_ANGLE_SPAN() Metric

func (S2_QUADRATIC_PROJECTION) MAX_AREA 

func (m S2_QUADRATIC_PROJECTION) MAX_AREA() Metric

func (S2_QUADRATIC_PROJECTION) MAX_DIAG 

func (m S2_QUADRATIC_PROJECTION) MAX_DIAG() Metric

func (S2_QUADRATIC_PROJECTION) MAX_EDGE 

func (m S2_QUADRATIC_PROJECTION) MAX_EDGE() Metric

func (S2_QUADRATIC_PROJECTION) MAX_EDGE_ASPECT 

func (m S2_QUADRATIC_PROJECTION) MAX_EDGE_ASPECT() float64

func (S2_QUADRATIC_PROJECTION) MAX_WIDTH 

func (m S2_QUADRATIC_PROJECTION) MAX_WIDTH() Metric

func (S2_QUADRATIC_PROJECTION) MIN_ANGLE_SPAN 

func (m S2_QUADRATIC_PROJECTION) MIN_ANGLE_SPAN() Metric

func (S2_QUADRATIC_PROJECTION) MIN_AREA 

func (m S2_QUADRATIC_PROJECTION) MIN_AREA() Metric

func (S2_QUADRATIC_PROJECTION) MIN_DIAG 

func (m S2_QUADRATIC_PROJECTION) MIN_DIAG() Metric

func (S2_QUADRATIC_PROJECTION) MIN_EDGE 

func (m S2_QUADRATIC_PROJECTION) MIN_EDGE() Metric

func (S2_QUADRATIC_PROJECTION) MIN_WIDTH 

func (m S2_QUADRATIC_PROJECTION) MIN_WIDTH() Metric

type WedgeContains 

type WedgeContains struct{}

*

  • Given two edge chains (see WedgeRelation above), this function returns +1
  • if the region to the left of A contains the region to the left of B, and
  • 0 otherwise.

func (WedgeContains) Test 

func (w WedgeContains) Test(a0, ab1, a2, b0, b2 Point) int

type WedgeContainsOrCrosses 

type WedgeContainsOrCrosses struct{}

*

  • Given two edge chains (see WedgeRelation above), this function returns +1
  • if A contains B, 0 if B contains A or the two wedges do not intersect,
  • and -1 if the edge chains A and B cross each other (i.e. if A intersects
  • both the interior and exterior of the region to the left of B). In
  • degenerate cases where more than one of these conditions is satisfied,
  • the maximum possible result is returned. For example, if A == B then the
  • result is +1.

func (WedgeContainsOrCrosses) Test 

func (w WedgeContainsOrCrosses) Test(a0, ab1, a2, b0, b2 Point) int

type WedgeContainsOrIntersects 

type WedgeContainsOrIntersects struct{}

*

  • Given two edge chains (see WedgeRelation above), this function returns +1
  • if A contains B, 0 if A and B are disjoint, and -1 if A intersects but
  • does not contain B.

func (WedgeContainsOrIntersects) Test 

func (w WedgeContainsOrIntersects) Test(a0, ab1, a2, b0, b2 Point) int

type WedgeIntersects 

type WedgeIntersects struct{}

*

  • Given two edge chains (see WedgeRelation above), this function returns -1
  • if the region to the left of A intersects the region to the left of B,
  • and 0 otherwise. Note that regions are defined such that points along a
  • boundary are contained by one side or the other, not both. So for
  • example, if A,B,C are distinct points ordered CCW around a vertex O, then
  • the wedges BOA, AOC, and COB do not intersect.

func (WedgeIntersects) Test 

func (w WedgeIntersects) Test(a0, ab1, a2, b0, b2 Point) int

type WedgeRelation 

type WedgeRelation interface {
	Test(a0, ab1, a2, b0, b2 Point) int
}

*

  • A wedge relation's test method accepts two edge chains A=(a0,a1,a2) and
  • B=(b0,b1,b2) where a1==b1, and returns either -1, 0, or 1 to indicate the
  • relationship between the region to the left of A and the region to the left
  • of B. Wedge relations are used to determine the local relationship between
  • two polygons that share a common vertex. *
  • All wedge relations require that a0 != a2 and b0 != b2. Other degenerate
  • cases (such as a0 == b2) are handled as expected. The parameter "ab1"
  • denotes the common vertex a1 == b1.

Notes

Bugs

  • The major differences from the C++ version is that barely anything is implemented.

  • The major differences from the C++ version are:

    • normalization

  • The major differences from the C++ version are:

    • almost everything

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.