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
- func CCW(a, b, c Point) bool
- func OrderedCCW(a, b, c, o Point) bool
- func PointArea(a, b, c Point) float64
- type Cap
- func (c Cap) ApproxEqual(other Cap) bool
- func (c Cap) Area() float64
- func (c Cap) CapBound() Cap
- func (c Cap) Complement() Cap
- func (c Cap) Contains(other Cap) 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) 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
- type CellID
- func (ci CellID) AllNeighbors() [8]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) RangeMax() CellID
- func (ci CellID) RangeMin() CellID
- func (ci CellID) String() string
- func (ci CellID) ToToken() string
- type CellUnion
- type Direction
- type LatLng
- type Point
- type Rect
- func (r Rect) AddPoint(ll LatLng) Rect
- func (r Rect) Area() float64
- func (r Rect) Center() LatLng
- func (r Rect) Hi() LatLng
- 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) Size() LatLng
- func (r Rect) String() string
- type Region
- Bugs
Constants ¶
const ( Clockwise Direction = -1 Indeterminate = 0 CounterClockwise = 1 )
These are the three options for the direction of a set of points.
Variables ¶
This section is empty.
Functions ¶
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 OrderedCCW ¶
OrderedCCW returns true if the edges OA, OB, and OC are encountered in that order while sweeping CCW around the point O.
You can think of this as testing whether A <= B <= C with respect to the CCW ordering around O that starts at A, or equivalently, whether B is contained in the range of angles (inclusive) that starts at A and extends CCW to C. Properties:
(1) If OrderedCCW(a,b,c,o) && OrderedCCW(b,a,c,o), then a == b (2) If OrderedCCW(a,b,c,o) && OrderedCCW(a,c,b,o), then b == c (3) If OrderedCCW(a,b,c,o) && OrderedCCW(c,b,a,o), then a == b == c (4) If a == b or b == c, then OrderedCCW(a,b,c,o) is true (5) Otherwise if a == c, then OrderedCCW(a,b,c,o) is false
func PointArea ¶
PointArea returns the area 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.
Types ¶
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) 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) 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) 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) 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).
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 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 CellIDFromToken ¶
CellIDFromToken returns a cell given a hex-encoded string of its uint64 ID.
func (CellID) AllNeighbors ¶
AllNeighbors returns the eights cells that are adjacent across and diagonal from the cell's four edges. Edges 0, 1, 2, 3, 4, 5, 6, 7 are in the down, down-right, right, right-up, up, up-left, left, down-left directions. All neighbors are guaranteed to be distinct.
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].
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.
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 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.
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 PointFromCoords ¶
PointFromCoords creates a new normalized point from coordinates.
This always returns a valid point. If the given coordinates can not be normalized the origin point will be returned.
This behavior is different from the C++ construction of a S2Point from coordinates (i.e. S2Point(x, y, z)) in that in C++ they do not Normalize.
func PointFromLatLng ¶
PointFromLatLng returns an Point for the given LatLng.
func (Point) ApproxEqual ¶
ApproxEqual reports if the two points are similar enough to be equal.
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 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.
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.
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