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
- Variables
- func Area(a, b, c Point) float64
- func AverageArea(level int) float64
- func CCW(a, b, c Point) bool
- func ExpensiveCCW(a, b, c Point) int
- func GetSimpleCovering(region Region, start Point, level int, output *[]CellID)
- func GirardArea(a, b, c Point) float64
- func LoopIsValid(vertices []Point) bool
- func OrderedCCW(a, b, c, o Point) bool
- func PlanarCCW(a, b r2.Vector) int
- func PlanarOrderedCCW(a, b, c r2.Vector) int
- func PointArea(a, b, c Point) float64
- func RobustCCW(a, b, c Point) int
- func RobustCCWWithCross(a, b, c, aCrossB Point) int
- func SignedArea(a, b, c Point) float64
- func VertexCrossing(a, b, c, d Point) bool
- type AreaCentroid
- type ByCellThenEdge
- type 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) Center() 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) Expanded(distance s1.Angle) Cap
- 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
- type Cell
- func (c Cell) AverageArea() float64
- func (c Cell) CapBound() Cap
- func (c Cell) ContainsCell(other Cell) bool
- func (c Cell) ContainsPoint(point Point) bool
- func (c Cell) Edge(k int) Point
- func (c Cell) EdgeRaw(k int) Point
- func (c Cell) ExactArea() float64
- func (c Cell) Face() int8
- func (c Cell) Id() CellID
- func (c Cell) IntersectsCell(other Cell) bool
- func (c Cell) IsLeaf() bool
- func (c Cell) Level() int8
- func (c Cell) Orientation() int8
- func (c Cell) RectBound() Rect
- func (c Cell) SizeIJ() int
- func (c Cell) Vertex(k int) Point
- type CellID
- func CellIDBegin(level int) CellID
- func CellIDEnd(level int) CellID
- func CellIDFromFace(face int) CellID
- func CellIDFromFacePosLevel(face int, pos uint64, level int) CellID
- func CellIDFromLatLng(ll LatLng) CellID
- func CellIDFromPoint(p Point) CellID
- func CellIDFromToken(s string) CellID
- func CellIDNone() CellID
- func CellIDSentinel() 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) Contains(oci CellID) bool
- func (ci CellID) EdgeNeighbors() [4]CellID
- 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) Next() 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) RangeMax() CellID
- func (ci CellID) RangeMin() CellID
- func (ci CellID) String() string
- func (ci CellID) ToString() string
- func (ci CellID) ToToken() string
- func (ci CellID) VertexNeighbors(level int) []CellID
- type CellUnion
- type DataEdgeIterator
- type Direction
- type Edge
- type EdgeCrosser
- type EdgeIndex
- type LatLng
- type Loop
- func (l *Loop) BoundaryApproxEquals(b *Loop, maxError float64) bool
- func (l *Loop) CapBound() Cap
- func (l *Loop) CompareTo(other *Loop) int
- func (l *Loop) ContainsCell(cell Cell) bool
- func (l *Loop) ContainsLoop(b *Loop) bool
- func (l *Loop) ContainsNested(b *Loop) bool
- func (l *Loop) ContainsOrCrosses(b *Loop) int
- func (l *Loop) ContainsPoint(p Point) bool
- func (l *Loop) Depth() int
- func (l *Loop) GetArea() float64
- func (l *Loop) GetAreaAndCentroid() AreaCentroid
- func (l *Loop) GetCentroid() Point
- func (l *Loop) GetDistance(p Point) s1.Angle
- func (l *Loop) IntersectsCell(cell Cell) bool
- func (l *Loop) IntersectsLoop(b *Loop) bool
- func (l *Loop) Invert()
- func (l *Loop) IsHole() bool
- func (l *Loop) IsNormalized() bool
- func (l *Loop) IsValid() bool
- func (l *Loop) Normalize()
- func (l *Loop) NumVertices() int
- func (l *Loop) RectBound() Rect
- func (l *Loop) SetDepth(depth int)
- func (l *Loop) Sign() int
- func (l *Loop) ToString() string
- func (l *Loop) Vertex(i int) Point
- type Metric
- type Point
- func (p Point) ApproxEquals(other Point, maxError float64) bool
- func (p Point) CompareTo(other Point) int
- func (p Point) DegreesString() string
- func (p Point) Distance(b Point) s1.Angle
- func (p Point) Equals(other Point) bool
- func (p Point) LessThan(vb Point) bool
- func (p Point) PointCross(op Point) Point
- type Polyline
- func (p Polyline) CapBound() Cap
- func (p Polyline) ContainsCell(cell Cell) bool
- func (p Polyline) GetArclengthAngle() s1.Angle
- func (p Polyline) IntersectsCell(cell Cell) bool
- func (p Polyline) IsValid() bool
- func (p Polyline) NumVertices() int
- func (p Polyline) RectBound() Rect
- func (p Polyline) Vertex(k int) Point
- type PriorityQueue
- type Projections
- type Rect
- func (r Rect) AddPoint(ll LatLng) Rect
- func (r Rect) Area() float64
- func (r Rect) CapBound() Cap
- func (r Rect) Center() LatLng
- func (r Rect) ContainsCell(c Cell) bool
- func (r Rect) ContainsLatLng(ll LatLng) bool
- func (r Rect) ContainsRect(other Rect) bool
- func (r Rect) Hi() LatLng
- func (r Rect) IntersectsCell(c Cell) bool
- func (r Rect) IntersectsRect(other Rect) 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) RectBound() Rect
- func (r Rect) Size() LatLng
- func (r Rect) String() string
- func (r Rect) Union(other Rect) Rect
- func (r Rect) Vertex(k int) LatLng
- type RectBounder
- type Region
- type RegionCoverer
- func (rc *RegionCoverer) GetCovering(region Region, covering *[]CellID)
- func (rc *RegionCoverer) GetCoveringAsUnion(region Region) *CellUnion
- func (rc *RegionCoverer) GetCoveringInternal(region Region)
- func (rc *RegionCoverer) GetInteriorCovering(region Region, interior *[]CellID)
- func (rc *RegionCoverer) GetInteriorCoveringAsUnion(region Region) *CellUnion
- func (rc *RegionCoverer) LevelMod() int
- func (rc *RegionCoverer) MaxCells() int
- func (rc *RegionCoverer) MaxLevel() int
- func (rc *RegionCoverer) MinLevel() int
- func (rc *RegionCoverer) SetLevelMod(levelMod int)
- func (rc *RegionCoverer) SetMaxCells(maxCells int)
- func (rc *RegionCoverer) SetMaxLevel(maxLevel int)
- func (rc *RegionCoverer) SetMinLevel(minLevel int)
- type S2_PROJECTION_COMMON
- type S2_QUADRATIC_PROJECTION
- func (m S2_QUADRATIC_PROJECTION) AVG_DIAG() Metric
- func (m S2_QUADRATIC_PROJECTION) AVG_EDGE() Metric
- func (m S2_QUADRATIC_PROJECTION) AVG_WIDTH() Metric
- func (m S2_QUADRATIC_PROJECTION) MAX_ANGLE_SPAN() Metric
- func (m S2_QUADRATIC_PROJECTION) MAX_AREA() Metric
- func (m S2_QUADRATIC_PROJECTION) MAX_DIAG() Metric
- func (m S2_QUADRATIC_PROJECTION) MAX_EDGE() Metric
- func (m S2_QUADRATIC_PROJECTION) MAX_EDGE_ASPECT() float64
- func (m S2_QUADRATIC_PROJECTION) MAX_WIDTH() Metric
- func (m S2_QUADRATIC_PROJECTION) MIN_ANGLE_SPAN() Metric
- func (m S2_QUADRATIC_PROJECTION) MIN_AREA() Metric
- func (m S2_QUADRATIC_PROJECTION) MIN_DIAG() Metric
- func (m S2_QUADRATIC_PROJECTION) MIN_EDGE() Metric
- func (m S2_QUADRATIC_PROJECTION) MIN_WIDTH() Metric
- type WedgeContains
- type WedgeContainsOrCrosses
- type WedgeContainsOrIntersects
- type WedgeIntersects
- type WedgeRelation
- Bugs
Constants ¶
const ( Clockwise Direction = -1 Indeterminate = 0 CounterClockwise = 1 )
These are the three options for the direction of a set of points.
const EPSILON float64 = 1e-14
const EXPONENT_MASK uint64 = 0x7ff0000000000000
Mask to extract the exponent from a double.
const EXPONENT_SHIFT uint = 52
Number of bits in the mantissa of a double.
const (
MAX_LEVEL = 30
)
TODO(dsymonds): Some of these constants should probably be exported.
Variables ¶
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)), } )
var MAX_DET_ERROR float64 = 1e-14
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.
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
var THICKENING float64 = 0.01
Functions ¶
func Area ¶
*
- 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 CCW ¶
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 ¶
*
- A relatively expensive calculation invoked by RobustCCW() if the sign of
- the determinant is uncertain.
func GetSimpleCovering ¶
*
- Given a connected region and a starting point, return a set of cells at the
- given level that cover the region.
func GirardArea ¶
*
- 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 ¶
*
- 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 ¶
*
- 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 PlanarOrderedCCW ¶
func PointArea ¶
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 ¶
*
- 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 ¶
*
- 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 ¶
*
- Like Area(), but returns a positive value for counterclockwise triangles
- and a negative value otherwise.
func VertexCrossing ¶
*
- 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 ¶
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 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.
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 unit-length.
func (Cap) ApproxEqual ¶
ApproxEqual reports if this caps' center and height are within a reasonable epsilon from the other cap.
func (Cap) CapBound ¶
CapBound returns a bounding spherical cap. This is not guaranteed to be exact.
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 region completely contains the given region. It returns false if containment could not be determined.
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) 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 region intersects the given cell or if intersection could not be determined. It returns false if the region does not intersect.
func (Cap) IsValid ¶
IsValid reports whether the Cap is considered valid. Heights are normalized so that they do not exceed 2.
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) AverageArea ¶
*
- 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 ¶
CapBound returns a bounding spherical cap. This is not guaranteed to be exact.
func (Cell) ContainsCell ¶
ContainsCell reports whether the region completely contains the given region. It returns false if containment could not be determined.
func (Cell) ContainsPoint ¶
func (Cell) Edge ¶
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) IntersectsCell ¶
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) Orientation ¶
func (Cell) RectBound ¶
RectBound returns a bounding latitude-longitude rectangle that contains the region. The bounds are not guaranteed to be tight.
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 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 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 ¶
CellIDFromLatLng returns the leaf cell containing ll.
func CellIDFromPoint ¶
CellIDFromPoint returns the leaf cell containing point p.
func CellIDFromToken ¶
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 ¶
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.
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 level-1 ancestor within its top-level 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) 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) Next ¶
Next returns the next cell along the Hilbert curve. This is expected to be used with ChildStart and ChildEnd.
func (CellID) Parent ¶
Parent returns the cell at the given level, which must be no greater than the current level.
func (CellID) Pos ¶
Pos returns the position along the Hilbert curve of this cell ID, in the range [0,2^posBits-1].
func (CellID) String ¶
String returns the string representation of the cell ID in the form "1/3210".
func (CellID) ToToken ¶
ToToken returns a hex-encoded 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 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 CellUnionFromCellIDs ¶
func (*CellUnion) Contains ¶
*
- 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 (*CellUnion) Intersects ¶
Intersects reports whether this cell union intersects the given cell ID.
This method assumes that the CellUnion has been normalized.
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 ¶
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 ¶
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 (*EdgeIndex) ComputeIndex ¶
func (e *EdgeIndex) ComputeIndex()
* Computes the index (if it has not been previously done).
func (*EdgeIndex) IsIndexComputed ¶
func (*EdgeIndex) PredictAdditionalCalls ¶
*
- 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.
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) IsValid ¶
IsValid returns true iff the LatLng is normalized, with Lat ∈ [-π/2,π/2] and Lng ∈ [-π,π].
func (LatLng) StringDegrees ¶
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 LoopFromCellAndRect ¶
func LoopFromPoints ¶
func (*Loop) BoundaryApproxEquals ¶
*
- 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 ¶
CapBound returns a bounding spherical cap. This is not guaranteed to be exact.
func (*Loop) ContainsCell ¶
*
- 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 (*Loop) ContainsNested ¶
*
- 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 ¶
*
- 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) GetArea ¶
*
- 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 ¶
*
- 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 ¶
*
- 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 ¶
*
- 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 ¶
*
- 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) 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 (*Loop) RectBound ¶
RectBound returns a bounding latitude-longitude rectangle that contains the region. The bounds are not guaranteed to be tight.
func (*Loop) SetDepth ¶
*
- 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
type Metric ¶
type Metric struct {
// contains filtered or unexported fields
}
Defines an area or a length cell metric.
type Point ¶
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 ¶
*
- 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 ¶
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 PointFromLatLng ¶
PointFromLatLng returns an Point for the given LatLng.
func 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.
func (Point) ApproxEquals ¶
ApproxEqual reports if the two points are similar enough to be equal.
func (Point) DegreesString ¶
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 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 (Polyline) CapBound ¶
CapBound returns a bounding spherical cap. This is not guaranteed to be exact.
func (Polyline) ContainsCell ¶
ContainsCell reports whether the region completely contains the given region. It returns false if containment could not be determined.
func (Polyline) GetArclengthAngle ¶
Return the angle corresponding to the total arclength of the polyline on a unit sphere.
func (Polyline) IntersectsCell ¶
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) NumVertices ¶
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 ¶
Rect represents a closed latitude-longitude rectangle.
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 RectFromLatLngLoHi ¶
func RectFromLatLngPointPair ¶
*
- 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) CapBound ¶
CapBound returns a bounding spherical cap. This is not guaranteed to be exact.
func (Rect) ContainsCell ¶
func (Rect) ContainsLatLng ¶
ContainsLatLng reports whether the given LatLng is within the Rect.
func (Rect) ContainsRect ¶
Return true if and only if the rectangle contains the given other rectangle.
func (Rect) IntersectsCell ¶
*
- 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 ¶
Return true if this rectangle and the given other rectangle have any points in common.
func (Rect) IsValid ¶
IsValid returns true iff the rectangle is valid. This requires Lat ⊆ [-π/2,π/2] and Lng ⊆ [-π,π], and Lat = ∅ iff Lng = ∅
func (Rect) RectBound ¶
RectBound returns a bounding latitude-longitude rectangle that contains the region. The bounds are not guaranteed to be tight.
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 ¶
*
- 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