s2

package
v0.0.0-...-5ae134c Latest Latest
Warning

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

 Go to latest Published: Dec 16, 2021 License: Apache-2.0 Imports: 17 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.

Variables

View Source 
var (
	MinAngleSpanMetric = Metric{1, 4.0 / 3}
	AvgAngleSpanMetric = Metric{1, math.Pi / 2}
	MaxAngleSpanMetric = Metric{1, 1.704897179199218452}
)

Each cell is bounded by four planes passing through its four edges and the center of the sphere. These metrics relate to the angle between each pair of opposite bounding planes, or equivalently, between the planes corresponding to two different s-values or two different t-values.

View Source 
var (
	MinWidthMetric = Metric{1, 2 * math.Sqrt2 / 3}
	AvgWidthMetric = Metric{1, 1.434523672886099389}
	MaxWidthMetric = Metric{1, MaxAngleSpanMetric.Deriv}
)

The width of geometric figure is defined as the distance between two parallel bounding lines in a given direction. For cells, the minimum width is always attained between two opposite edges, and the maximum width is attained between two opposite vertices. However, for our purposes we redefine the width of a cell as the perpendicular distance between a pair of opposite edges. A cell therefore has two widths, one in each direction. The minimum width according to this definition agrees with the classic geometric one, but the maximum width is different. (The maximum geometric width corresponds to MaxDiag defined below.)

The average width in both directions for all cells at level k is approximately AvgWidthMetric.Value(k).

The width is useful for bounding the minimum or maximum distance from a point on one edge of a cell to the closest point on the opposite edge. For example, this is useful when growing regions by a fixed distance.

View Source 
var (
	MinEdgeMetric = Metric{1, 2 * math.Sqrt2 / 3}
	AvgEdgeMetric = Metric{1, 1.459213746386106062}
	MaxEdgeMetric = Metric{1, MaxAngleSpanMetric.Deriv}

	// MaxEdgeAspect is the maximum edge aspect ratio over all cells at any level,
	// where the edge aspect ratio of a cell is defined as the ratio of its longest
	// edge length to its shortest edge length.
	MaxEdgeAspect = 1.442615274452682920

	MinAreaMetric = Metric{2, 8 * math.Sqrt2 / 9}
	AvgAreaMetric = Metric{2, 4 * math.Pi / 6}
	MaxAreaMetric = Metric{2, 2.635799256963161491}
)

The edge length metrics can be used to bound the minimum, maximum, or average distance from the center of one cell to the center of one of its edge neighbors. In particular, it can be used to bound the distance between adjacent cell centers along the space-filling Hilbert curve for cells at any given level.

View Source 
var (
	MinDiagMetric = Metric{1, 8 * math.Sqrt2 / 9}
	AvgDiagMetric = Metric{1, 2.060422738998471683}
	MaxDiagMetric = Metric{1, 2.438654594434021032}

	// MaxDiagAspect is the maximum diagonal aspect ratio over all cells at any
	// level, where the diagonal aspect ratio of a cell is defined as the ratio
	// of its longest diagonal length to its shortest diagonal length.
	MaxDiagAspect = math.Sqrt(3)
)

The maximum diagonal is also the maximum diameter of any cell, and also the maximum geometric width (see the comment for widths). For example, the distance from an arbitrary point to the closest cell center at a given level is at most half the maximum diagonal length.

Functions

func Angle 

func Angle(a, b, c Point) s1.Angle

Angle returns the interior angle at the vertex B in the triangle ABC. The return value is always in the range [0, pi]. All points should be normalized. Ensures that Angle(a,b,c) == Angle(c,b,a) for all a,b,c.

The angle is undefined if A or C is diametrically opposite from B, and becomes numerically unstable as the length of edge AB or BC approaches 180 degrees.

func ChordAngleBetweenPoints 

func ChordAngleBetweenPoints(x, y Point) s1.ChordAngle

ChordAngleBetweenPoints constructs a ChordAngle corresponding to the distance between the two given points. The points must be unit length.

func ClipEdge 

func ClipEdge(a, b r2.Point, clip r2.Rect) (aClip, bClip r2.Point, intersects bool)

ClipEdge returns the portion of the edge defined by AB that is contained by the given rectangle. If there is no intersection, false is returned and aClip and bClip are undefined.

func ClipToFace 

func ClipToFace(a, b Point, face int) (aUV, bUV r2.Point, intersects bool)

ClipToFace returns the (u,v) coordinates for the portion of the edge AB that intersects the given face, or false if the edge AB does not intersect. This method guarantees that the clipped vertices lie within the [-1,1]x[-1,1] cube face rectangle and are within faceClipErrorUVDist of the line AB, but the results may differ from those produced by FaceSegments.

func ClipToPaddedFace 

func ClipToPaddedFace(a, b Point, f int, padding float64) (aUV, bUV r2.Point, intersects bool)

ClipToPaddedFace returns the (u,v) coordinates for the portion of the edge AB that intersects the given face, but rather than clipping to the square [-1,1]x[-1,1] in (u,v) space, this method clips to [-R,R]x[-R,R] where R=(1+padding). Padding must be non-negative.

func DistanceFraction 

func DistanceFraction(x, a, b Point) float64

DistanceFraction returns the distance ratio of the point X along an edge AB. If X is on the line segment AB, this is the fraction T such that X == Interpolate(T, A, B).

This requires that A and B are distinct.

func DistanceFromSegment 

func DistanceFromSegment(x, a, b Point) s1.Angle

DistanceFromSegment returns the distance of point X from line segment AB. The points are expected to be normalized. The result is very accurate for small distances but may have some numerical error if the distance is large (approximately pi/2 or greater). The case A == B is handled correctly.

func EdgeOrVertexCrossing 

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

EdgeOrVertexCrossing is a convenience function that calls CrossingSign to handle cases where all four vertices are distinct, and VertexCrossing to handle cases where two or more vertices are the same. This defines a crossing function such that point-in-polygon containment tests can be implemented by simply counting edge crossings.

func GirardArea 

func GirardArea(a, b, c Point) float64

GirardArea returns the area of the triangle computed using Girard's formula. All points should be unit length, and no two points should be antipodal.

This method is about twice as fast as PointArea() but has poor relative accuracy for small triangles. The maximum error is about 5e-15 (about 0.25 square meters on the Earth's surface) and the average error is about 1e-15. These bounds apply to triangles of any size, even as the maximum edge length of the triangle approaches 180 degrees. But note that for such triangles, tiny perturbations of the input points can change the true mathematical area dramatically.

func IsDistanceLess 

func IsDistanceLess(x, a, b Point, limit s1.ChordAngle) bool

IsDistanceLess reports whether the distance from X to the edge AB is less than limit. This method is faster than DistanceFromSegment(). If you want to compare against a fixed s1.Angle, you should convert it to an s1.ChordAngle once and save the value, since this conversion is relatively expensive.

func IsInteriorDistanceLess 

func IsInteriorDistanceLess(x, a, b Point, limit s1.ChordAngle) bool

IsInteriorDistanceLess reports whether the minimum distance from X to the edge AB is attained at an interior point of AB (i.e., not an endpoint), and that distance is less than limit.

func OrderedCCW 

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

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 

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 Sign 

func Sign(a, b, c Point) bool

Sign returns true if the points A, B, C are strictly counterclockwise, and returns false if the points are clockwise or collinear (i.e. if they are all contained on some great circle).

Due to numerical errors, situations may arise that are mathematically impossible, e.g. ABC may be considered strictly CCW while BCA is not. However, the implementation guarantees the following:

If Sign(a,b,c), then !Sign(c,b,a) for all a,b,c.

func SignedArea 

func SignedArea(a, b, c Point) float64

SignedArea returns a positive value for counterclockwise triangles and a negative value otherwise (similar to PointArea).

func SimpleCrossing 

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

SimpleCrossing reports whether edge AB crosses CD at a point that is interior to both edges. Properties: 

(1) SimpleCrossing(b,a,c,d) == SimpleCrossing(a,b,c,d)
(2) SimpleCrossing(c,d,a,b) == SimpleCrossing(a,b,c,d)

DEPRECATED: Use CrossingSign(a,b,c,d) == Cross instead.

func TurnAngle 

func TurnAngle(a, b, c Point) s1.Angle

TurnAngle returns the exterior angle at vertex B in the triangle ABC. The return value is positive if ABC is counterclockwise and negative otherwise. If you imagine an ant walking from A to B to C, this is the angle that the ant turns at vertex B (positive = left = CCW, negative = right = CW). This quantity is also known as the "geodesic curvature" at B.

Ensures that TurnAngle(a,b,c) == -TurnAngle(c,b,a) for all distinct a,b,c. The result is undefined if (a == b || b == c), but is either -Pi or Pi if (a == c). All points should be normalized.

func UpdateMinDistance 

func UpdateMinDistance(x, a, b Point, minDist s1.ChordAngle) (s1.ChordAngle, bool)

UpdateMinDistance checks if the distance from X to the edge AB is less then minDist, and if so, returns the updated value and true. The case A == B is handled correctly.

Use this method when you want to compute many distances and keep track of the minimum. It is significantly faster than using DistanceFromSegment because (1) using s1.ChordAngle is much faster than s1.Angle, and (2) it can save a lot of work by not actually computing the distance when it is obviously larger than the current minimum.

func UpdateMinInteriorDistance 

func UpdateMinInteriorDistance(x, a, b Point, minDist s1.ChordAngle) (s1.ChordAngle, bool)

UpdateMinInteriorDistance reports whether the minimum distance from X to AB is attained at an interior point of AB (i.e., not an endpoint), and that distance is less than minDist. If so, the value of minDist is updated and true is returned. Otherwise it is unchanged and returns false.

func VertexCrossing 

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

VertexCrossing reports whether two edges "cross" in such a way that point-in-polygon containment tests can be implemented by counting the number of edge crossings.

Given two edges AB and CD where at least two vertices are identical (i.e. CrossingSign(a,b,c,d) == 0), the basic rule is that a "crossing" occurs if AB is encountered after CD during a CCW sweep around the shared vertex starting from a fixed reference point.

Note that according to this rule, if AB crosses CD then in general CD does not cross AB. However, this leads to the correct result when counting polygon edge crossings. For example, suppose that A,B,C are three consecutive vertices of a CCW polygon. If we now consider the edge crossings of a segment BP as P sweeps around B, the crossing number changes parity exactly when BP crosses BA or BC.

Useful properties of VertexCrossing (VC): 

(1) VC(a,a,c,d) == VC(a,b,c,c) == false
(2) VC(a,b,a,b) == VC(a,b,b,a) == true
(3) VC(a,b,c,d) == VC(a,b,d,c) == VC(b,a,c,d) == VC(b,a,d,c)
(3) If exactly one of a,b equals one of c,d, then exactly one of
    VC(a,b,c,d) and VC(c,d,a,b) is true

It is an error to call this method with 4 distinct vertices.

func WedgeContains 

func WedgeContains(a0, ab1, a2, b0, b2 Point) bool

WedgeContains reports whether non-empty wedge A=(a0, ab1, a2) contains B=(b0, ab1, b2). Equivalent to WedgeRelation == WedgeProperlyContains || WedgeEquals.

func WedgeIntersects 

func WedgeIntersects(a0, ab1, a2, b0, b2 Point) bool

WedgeIntersects reports whether non-empty wedge A=(a0, ab1, a2) intersects B=(b0, ab1, b2). Equivalent but faster than WedgeRelation != WedgeIsDisjoint

Types

type Cap 

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

Cap represents a 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.)

A cap can also be defined by its center point and height. The height is the distance from the center point to the cutoff plane. There is also support for "empty" and "full" caps, which contain no points and all points respectively.

Here are some useful relationships between the cap height (h), the cap radius (r), the maximum chord length from the cap's center (d), and the radius of cap's base (a). 

  h = 1 - cos(r)
    = 2 * sin^2(r/2)
d^2 = 2 * h
    = a^2 + h^2

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

func CapFromCenterAngle 

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 CapFromCenterChordAngle 

func CapFromCenterChordAngle(center Point, radius s1.ChordAngle) Cap

CapFromCenterChordAngle constructs a cap where the angle is expressed as an s1.ChordAngle. This constructor is more efficient than using an s1.Angle.

func CapFromCenterHeight 

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. The center should be unit length.

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 whether this cap is equal to the other cap within the given tolerance.

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

func (c Cap) CellUnionBound() []CellID

CellUnionBound computes a covering of the Cap. In general the covering consists of at most 4 cells except for very large caps, which may need up to 6 cells. The output is not sorted.

func (Cap) Center 

func (c Cap) Center() Point

Center returns the cap's center point.

func (Cap) Centroid 

func (c Cap) Centroid() Point

Centroid returns the true centroid of the cap multiplied by its surface area The result lies on the ray from the origin through the cap's center, but it is not unit length. Note that if you just want the "surface centroid", i.e. the normalized result, then it is simpler to call Center.

The reason for multiplying the result by the cap area is to make it easier to compute the centroid of more complicated shapes. The centroid of a union of disjoint regions can be computed simply by adding their Centroid() results. Caveat: for caps that contain a single point (i.e., zero radius), this method always returns the origin (0, 0, 0). This is because shapes with no area don't affect the centroid of a union whose total area is positive.

func (Cap) Complement 

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 cap contains the given cell.

func (Cap) ContainsPoint 

func (c Cap) ContainsPoint(p Point) bool

ContainsPoint reports whether this cap contains the point.

func (Cap) Encode 

func (c Cap) Encode(w io.Writer) error

Encode encodes the Cap.

func (Cap) Equal 

func (c Cap) Equal(other Cap) bool

Equal reports whether this cap is equal to the other cap.

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

func (c Cap) Height() float64

Height returns the height of the cap. This is the distance from the center point to the cutoff plane.

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 cap intersects the cell.

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.

func (Cap) Radius 

func (c Cap) Radius() s1.Angle

Radius returns the cap radius as an s1.Angle. (Note that the cap angle is stored internally as a ChordAngle, so this method requires a trigonometric operation and may yield a slightly different result than the value passed to CapFromCenterAngle).

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

func (Cap) Union 

func (c Cap) Union(other Cap) Cap

Union returns the smallest cap which encloses this cap and other.

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

func (c Cell) ApproxArea() float64

ApproxArea returns the approximate area of this cell. This method is accurate to within 3% percent for all cell sizes and accurate to within 0.1% for cells at level 5 or higher (i.e. squares 350km to a side or smaller on the Earth's surface). It is moderately cheap to compute.

func (Cell) AverageArea 

func (c Cell) AverageArea() float64

AverageArea returns the average area of cells at the level of this cell. This is accurate to within a factor of 1.7.

func (Cell) BoundUV 

func (c Cell) BoundUV() r2.Rect

BoundUV returns the bounds of this cell in (u,v)-space.

func (Cell) BoundaryDistance 

func (c Cell) BoundaryDistance(target Point) s1.ChordAngle

BoundaryDistance reports the distance from the cell boundary to the given point.

func (Cell) CapBound 

func (c Cell) CapBound() Cap

CapBound returns the bounding cap of this cell.

func (Cell) CellUnionBound 

func (c Cell) CellUnionBound() []CellID

CellUnionBound computes a covering of the Cell.

func (Cell) Center 

func (c Cell) Center() Point

Center returns the direction vector corresponding to the center in (s,t)-space of the given cell. This is the point at which the cell is divided into four subcells; it is not necessarily the centroid of the cell in (u,v)-space or (x,y,z)-space

func (Cell) Children 

func (c Cell) Children() ([4]Cell, bool)

Children returns the four direct children of this cell in traversal order and returns true. If this is a leaf cell, or the children could not be created, false is returned. The C++ method is called Subdivide.

func (Cell) ContainsCell 

func (c Cell) ContainsCell(oc Cell) bool

ContainsCell reports whether this cell contains the other cell.

func (Cell) ContainsPoint 

func (c Cell) ContainsPoint(p Point) bool

ContainsPoint reports whether this cell contains the given point. Note that unlike Loop/Polygon, a Cell is considered to be a closed set. This means that a point on a Cell's edge or vertex belong to the Cell and the relevant adjacent Cells too.

If you want every point to be contained by exactly one Cell, you will need to convert the Cell to a Loop.

func (Cell) Distance 

func (c Cell) Distance(target Point) s1.ChordAngle

Distance reports the distance from the cell to the given point. Returns zero if the point is inside the cell.

func (Cell) DistanceToEdge 

func (c Cell) DistanceToEdge(a, b Point) s1.ChordAngle

DistanceToEdge returns the minimum distance from the cell to the given edge AB. Returns zero if the edge intersects the cell interior.

func (Cell) Edge 

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) (for k = 0,1,2,3).

func (Cell) Encode 

func (c Cell) Encode(w io.Writer) error

Encode encodes the Cell.

func (Cell) ExactArea 

func (c Cell) ExactArea() float64

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

func (Cell) Face 

func (c Cell) Face() int

Face returns the face this cell is on.

func (Cell) ID 

func (c Cell) ID() CellID

ID returns the CellID this cell represents.

func (Cell) IntersectsCell 

func (c Cell) IntersectsCell(oc Cell) bool

IntersectsCell reports whether the intersection of this cell and the other cell is not nil.

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() int

Level returns the level of this cell.

func (Cell) RectBound 

func (c Cell) RectBound() Rect

RectBound returns the bounding rectangle of this cell.

func (Cell) SizeIJ 

func (c Cell) SizeIJ() int

SizeIJ returns the edge length of this cell in (i,j)-space.

func (Cell) SizeST 

func (c Cell) SizeST() float64

SizeST returns the edge length of this cell in (s,t)-space.

func (Cell) Vertex 

func (c Cell) Vertex(k int) Point

Vertex returns the k-th vertex of the cell (k = 0,1,2,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.

Sequentially increasing cell IDs follow a continuous space-filling curve over the entire sphere. They have the following properties:

  • The ID of a cell at level k consists of a 3-bit face number followed by k bit pairs that recursively select one of the four children of each cell. The next bit is always 1, and all other bits are 0. Therefore, the level of a cell is determined by the position of its lowest-numbered bit that is turned on (for a cell at level k, this position is 2 * (maxLevel - k)).

  • The ID of a parent cell is at the midpoint of the range of IDs spanned by its children (or by its descendants at any level).

Leaf cells are often used to represent points on the unit sphere, and this type provides methods for converting directly between these two representations. For cells that represent 2D regions rather than discrete point, it is better to use Cells.

func CellIDFromFace 

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 CellIDFromToken 

func CellIDFromToken(s string) CellID

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

func (CellID) Advance 

func (ci CellID) Advance(steps int64) CellID

Advance advances or retreats the indicated number of steps along the Hilbert curve at the current level, and returns the new position. The position is never advanced past End() or before Begin().

func (CellID) AdvanceWrap 

func (ci CellID) AdvanceWrap(steps int64) CellID

AdvanceWrap advances or retreats the indicated number of steps along the Hilbert curve at the current level and returns the new position. The position wraps between the first and last faces as necessary.

func (CellID) AllNeighbors 

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

AllNeighbors returns all neighbors of this cell at the given level. Two cells X and Y are neighbors if their boundaries intersect but their interiors do not. In particular, two cells that intersect at a single point are neighbors. Note that for cells adjacent to a face vertex, the same neighbor may be returned more than once. There could be up to eight neighbors including the diagonal ones that share the vertex.

This requires level >= ci.Level().

func (CellID) ChildBegin 

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. See ChildBegin for example use.

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

func (ci CellID) CommonAncestorLevel(other CellID) (level int, ok bool)

CommonAncestorLevel returns the level of the common ancestor of the two S2 CellIDs.

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

func (ci CellID) Encode(w io.Writer) error

Encode encodes the CellID.

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

func (ci CellID) MaxTile(limit CellID) CellID

MaxTile returns the largest cell with the same RangeMin such that RangeMax < limit.RangeMin. It returns limit if no such cell exists. This method can be used to generate a small set of CellIDs that covers a given range (a tiling). This example shows how to generate a tiling for a semi-open range of leaf cells [start, limit): 

for id := start.MaxTile(limit); id != limit; id = id.Next().MaxTile(limit)) { ... }

Note that in general the cells in the tiling will be of different sizes; they gradually get larger (near the middle of the range) and then gradually get smaller as limit is approached.

func (CellID) Next 

func (ci CellID) Next() CellID

Next returns the next cell along the Hilbert curve. This is expected to be used with ChildBegin and ChildEnd, or ChildBeginAtLevel and ChildEndAtLevel.

func (CellID) NextWrap 

func (ci CellID) NextWrap() CellID

NextWrap returns the next cell along the Hilbert curve, wrapping from last to first as necessary. This should not be used with ChildBegin and ChildEnd.

func (CellID) Parent 

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. The maximum directional error in Point (compared to the exact mathematical result) is 1.5 * dblEpsilon radians, and the maximum length error is 2 * dblEpsilon (the same as Normalize).

func (CellID) Pos 

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

func (ci CellID) PrevWrap() CellID

PrevWrap returns the previous cell along the Hilbert curve, wrapping around from first to last as necessary. This should not be used with ChildBegin and ChildEnd.

func (CellID) 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) 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 CellRelation 

type CellRelation int

CellRelation describes the possible relationships between a target cell and the cells of the ShapeIndex. If the target is an index cell or is contained by an index cell, it is Indexed. If the target is subdivided into one or more index cells, it is Subdivided. Otherwise it is Disjoint. 

const (
	Indexed CellRelation = iota
	Subdivided
	Disjoint
)

The possible CellRelations for a ShapeIndex.

type CellUnion 

type CellUnion []CellID

A CellUnion is a collection of CellIDs.

It is normalized if it is sorted, and does not contain redundancy. Specifically, it may not contain the same CellID twice, nor a CellID that is contained by another, nor the four sibling CellIDs that are children of a single higher level CellID.

CellUnions are not required to be normalized, but certain operations will return different results if they are not (e.g. Contains).

func CellUnionFromRange 

func CellUnionFromRange(begin, end CellID) CellUnion

CellUnionFromRange creates a CellUnion that covers the half-open range of leaf cells [begin, end). If begin == end the resulting union is empty. This requires that begin and end are both leaves, and begin <= end. To create a closed-ended range, pass in end.Next().

func (*CellUnion) CapBound 

func (cu *CellUnion) CapBound() Cap

CapBound returns a Cap that bounds this entity.

func (*CellUnion) CellUnionBound 

func (cu *CellUnion) CellUnionBound() []CellID

CellUnionBound computes a covering of the CellUnion.

func (*CellUnion) ContainsCell 

func (cu *CellUnion) ContainsCell(c Cell) bool

ContainsCell reports whether this cell union contains the given cell.

func (*CellUnion) ContainsCellID 

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

ContainsCellID reports whether the cell union contains the given cell ID. Containment is defined with respect to regions, e.g. a cell contains its 4 children.

CAVEAT: If you have constructed a non-normalized CellUnion, note that groups of 4 child cells are *not* considered to contain their parent cell. To get this behavior you must use one of the call Normalize() explicitly.

func (*CellUnion) ContainsPoint 

func (cu *CellUnion) ContainsPoint(p Point) bool

ContainsPoint reports whether this cell union contains the given point.

func (*CellUnion) Denormalize 

func (cu *CellUnion) Denormalize(minLevel, levelMod int)

Denormalize replaces this CellUnion with an expanded version of the CellUnion where any cell whose level is less than minLevel or where (level - minLevel) is not a multiple of levelMod is replaced by its children, until either both of these conditions are satisfied or the maximum level is reached.

func (*CellUnion) Encode 

func (cu *CellUnion) Encode(w io.Writer) error

Encode encodes the CellUnion.

func (*CellUnion) IntersectsCell 

func (cu *CellUnion) IntersectsCell(c Cell) bool

IntersectsCell reports whether this cell union intersects the given cell.

func (*CellUnion) IntersectsCellID 

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

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

func (*CellUnion) IsNormalized 

func (cu *CellUnion) IsNormalized() bool

IsNormalized reports whether the cell union is normalized, meaning that it is satisfies IsValid and that no four cells have a common parent. Certain operations such as Contains will return a different result if the cell union is not normalized.

func (*CellUnion) IsValid 

func (cu *CellUnion) IsValid() bool

IsValid reports whether the cell union is valid, meaning that the CellIDs are valid, non-overlapping, and sorted in increasing order.

func (*CellUnion) LeafCellsCovered 

func (cu *CellUnion) LeafCellsCovered() int64

LeafCellsCovered reports the number of leaf cells covered by this cell union. This will be no more than 6*2^60 for the whole sphere.

func (*CellUnion) Normalize 

func (cu *CellUnion) Normalize()

Normalize normalizes the CellUnion.

func (*CellUnion) RectBound 

func (cu *CellUnion) RectBound() Rect

RectBound returns a Rect that bounds this entity.

type Chain 

type Chain struct {
	Start, Length int
}

Chain represents a range of edge IDs corresponding to a chain of connected edges, specified as a (start, length) pair. The chain is defined to consist of edge IDs {start, start + 1, ..., start + length - 1}.

type ChainPosition 

type ChainPosition struct {
	ChainID, Offset int
}

ChainPosition represents the position of an edge within a given edge chain, specified as a (chainID, offset) pair. Chains are numbered sequentially starting from zero, and offsets are measured from the start of each chain.

type ContainsVertexQuery 

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

ContainsVertexQuery is used to track the edges entering and leaving the given vertex of a Polygon in order to be able to determine if the point is contained by the Polygon.

Point containment is defined according to the semi-open boundary model which means that if several polygons tile the region around a vertex, then exactly one of those polygons contains that vertex.

func NewContainsVertexQuery 

func NewContainsVertexQuery(target Point) *ContainsVertexQuery

NewContainsVertexQuery returns a new query for the given vertex whose containment will be determined.

func (*ContainsVertexQuery) AddEdge 

func (q *ContainsVertexQuery) AddEdge(v Point, direction int)

AddEdge adds the edge between target and v with the given direction. (+1 = outgoing, -1 = incoming, 0 = degenerate).

func (*ContainsVertexQuery) ContainsVertex 

func (q *ContainsVertexQuery) ContainsVertex() int

ContainsVertex reports a +1 if the target vertex is contained, -1 if it is not contained, and 0 if the incident edges consisted of matched sibling pairs.

type Crossing 

type Crossing int

A Crossing indicates how edges cross. 

const (
	// Cross means the edges cross.
	Cross Crossing = iota
	// MaybeCross means two vertices from different edges are the same.
	MaybeCross
	// DoNotCross means the edges do not cross.
	DoNotCross
)

func CrossingSign 

func CrossingSign(a, b, c, d Point) Crossing

CrossingSign reports whether the edge AB intersects the edge CD. If AB crosses CD at a point that is interior to both edges, Cross is returned. If any two vertices from different edges are the same it returns MaybeCross. Otherwise it returns DoNotCross. If either edge is degenerate (A == B or C == D), the return value is MaybeCross if two vertices from different edges are the same and DoNotCross otherwise.

Properties of CrossingSign: 

(1) CrossingSign(b,a,c,d) == CrossingSign(a,b,c,d)
(2) CrossingSign(c,d,a,b) == CrossingSign(a,b,c,d)
(3) CrossingSign(a,b,c,d) == MaybeCross if a==c, a==d, b==c, b==d
(3) CrossingSign(a,b,c,d) == DoNotCross or MaybeCross if a==b or c==d

This method implements an exact, consistent perturbation model such that no three points are ever considered to be collinear. This means that even if you have 4 points A, B, C, D that lie exactly in a line (say, around the equator), C and D will be treated as being slightly to one side or the other of AB. This is done in a way such that the results are always consistent (see RobustSign).

type CrossingType 

type CrossingType int

CrossingType defines different ways of reporting edge intersections. 

const (
	// CrossingTypeInterior reports intersections that occur at a point
	// interior to both edges (i.e., not at a vertex).
	CrossingTypeInterior CrossingType = iota

	// CrossingTypeAll reports all intersections, even those where two edges
	// intersect only because they share a common vertex.
	CrossingTypeAll

	// CrossingTypeNonAdjacent reports all intersections except for pairs of
	// the form (AB, BC) where both edges are from the same ShapeIndex.
	CrossingTypeNonAdjacent
)

type Direction 

type Direction int

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

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) == Indeterminate if and only if a == b, b == c, or c == a
(2) RobustSign(b,c,a) == RobustSign(a,b,c) for all a,b,c
(3) RobustSign(c,b,a) == -RobustSign(a,b,c) for all a,b,c

In other words: 

(1) The result is Indeterminate if and only if two points are the same.
(2) Rotating the order of the arguments does not affect the result.
(3) Exchanging any two arguments inverts the result.

On the other hand, note that it is not true in general that RobustSign(-a,b,c) == -RobustSign(a,b,c), or any similar identities involving antipodal points.

type Edge 

type Edge struct {
	V0, V1 Point
}

Edge represents a geodesic edge consisting of two vertices. Zero-length edges are allowed, and can be used to represent points.

func (Edge) Cmp 

func (e Edge) Cmp(other Edge) int

Cmp compares the two edges using the underlying Points Cmp method and returns 

-1 if e <  other
 0 if e == other
+1 if e >  other

The two edges are compared by first vertex, and then by the second vertex.

type EdgeCrosser 

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

EdgeCrosser allows edges to be efficiently tested for intersection with a given fixed edge AB. It is especially efficient when testing for intersection with an edge chain connecting vertices v0, v1, v2, ...

Example usage: 

func CountIntersections(a, b Point, edges []Edge) int {
	count := 0
	crosser := NewEdgeCrosser(a, b)
	for _, edge := range edges {
		if crosser.CrossingSign(&edge.First, &edge.Second) != DoNotCross {
			count++
		}
	}
	return count
}

func NewChainEdgeCrosser 

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

NewChainEdgeCrosser is a convenience constructor that uses AB as the fixed edge, and C as the first vertex of the vertex chain (equivalent to calling RestartAt(c)).

You don't need to use this or any of the chain functions unless you're trying to squeeze out every last drop of performance. Essentially all you are saving is a test whether the first vertex of the current edge is the same as the second vertex of the previous edge.

func NewEdgeCrosser 

func NewEdgeCrosser(a, b Point) *EdgeCrosser

NewEdgeCrosser returns an EdgeCrosser with the fixed edge AB.

func (*EdgeCrosser) ChainCrossingSign 

func (e *EdgeCrosser) ChainCrossingSign(d Point) Crossing

ChainCrossingSign is like CrossingSign, but uses the last vertex passed to one of the crossing methods (or RestartAt) as the first vertex of the current edge.

func (*EdgeCrosser) CrossingSign 

func (e *EdgeCrosser) CrossingSign(c, d Point) Crossing

CrossingSign reports whether the edge AB intersects the edge CD. If any two vertices from different edges are the same, returns MaybeCross. If either edge is degenerate (A == B or C == D), returns either DoNotCross or MaybeCross.

Properties of CrossingSign: 

(1) CrossingSign(b,a,c,d) == CrossingSign(a,b,c,d)
(2) CrossingSign(c,d,a,b) == CrossingSign(a,b,c,d)
(3) CrossingSign(a,b,c,d) == MaybeCross if a==c, a==d, b==c, b==d
(3) CrossingSign(a,b,c,d) == DoNotCross or MaybeCross if a==b or c==d

Note that if you want to check an edge against a chain of other edges, it is slightly more efficient to use the single-argument version ChainCrossingSign below.

func (*EdgeCrosser) EdgeOrVertexChainCrossing 

func (e *EdgeCrosser) EdgeOrVertexChainCrossing(d Point) bool

EdgeOrVertexChainCrossing is like EdgeOrVertexCrossing, but uses the last vertex passed to one of the crossing methods (or RestartAt) as the first vertex of the current edge.

func (*EdgeCrosser) EdgeOrVertexCrossing 

func (e *EdgeCrosser) EdgeOrVertexCrossing(c, d Point) bool

EdgeOrVertexCrossing reports whether if CrossingSign(c, d) > 0, or AB and CD share a vertex and VertexCrossing(a, b, c, d) is true.

This method extends the concept of a "crossing" to the case where AB and CD have a vertex in common. The two edges may or may not cross, according to the rules defined in VertexCrossing above. The rules are designed so that point containment tests can be implemented simply by counting edge crossings. Similarly, determining whether one edge chain crosses another edge chain can be implemented by counting.

func (*EdgeCrosser) RestartAt 

func (e *EdgeCrosser) RestartAt(c Point)

RestartAt sets the current point of the edge crosser to be c. Call this method when your chain 'jumps' to a new place. The argument must point to a value that persists until the next call.

type FaceSegment 

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

FaceSegment represents an edge AB clipped to an S2 cube face. It is represented by a face index and a pair of (u,v) coordinates.

func FaceSegments 

func FaceSegments(a, b Point) []FaceSegment

FaceSegments subdivides the given edge AB at every point where it crosses the boundary between two S2 cube faces and returns the corresponding FaceSegments. The segments are returned in order from A toward B. The input points must be unit length.

This function guarantees that the returned segments form a continuous path from A to B, and that all vertices are within faceClipErrorUVDist of the line AB. All vertices lie within the [-1,1]x[-1,1] cube face rectangles. The results are consistent with Sign, i.e. the edge is well-defined even its endpoints are antipodal. TODO(roberts): Extend the implementation of PointCross so that this is true.

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

func (ll LatLng) Normalized() LatLng

Normalized returns the normalized version of the LatLng, with Lat clamped to [-π/2,π/2] and Lng wrapped in [-π,π].

func (LatLng) String 

func (ll LatLng) String() string

type Loop 

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

Loop represents a simple spherical polygon. It consists of a sequence of vertices where the first vertex is implicitly connected to the last. All loops are defined to have a CCW orientation, i.e. the interior of the loop is on the left side of the edges. This implies that a clockwise loop enclosing a small area is interpreted to be a CCW loop enclosing a very large area.

Loops are not allowed to have any duplicate vertices (whether adjacent or not), and non-adjacent edges are not allowed to intersect. Loops must have at least 3 vertices (except for the "empty" and "full" loops discussed below).

There are two special loops: the "empty" loop contains no points and the "full" loop contains all points. These loops do not have any edges, but to preserve the invariant that every loop can be represented as a vertex chain, they are defined as having exactly one vertex each (see EmptyLoop and FullLoop).

func EmptyLoop 

func EmptyLoop() *Loop

EmptyLoop returns a special "empty" loop.

func FullLoop 

func FullLoop() *Loop

FullLoop returns a special "full" loop.

func LoopFromCell 

func LoopFromCell(c Cell) *Loop

LoopFromCell constructs a loop corresponding to the given cell.

Note that the loop and cell *do not* contain exactly the same set of points, because Loop and Cell have slightly different definitions of point containment. For example, a Cell vertex is contained by all four neighboring Cells, but it is contained by exactly one of four Loops constructed from those cells. As another example, the cell coverings of cell and LoopFromCell(cell) will be different, because the loop contains points on its boundary that actually belong to other cells (i.e., the covering will include a layer of neighboring cells).

func LoopFromPoints 

func LoopFromPoints(pts []Point) *Loop

LoopFromPoints constructs a loop from the given points.

func RegularLoop 

func RegularLoop(center Point, radius s1.Angle, numVertices int) *Loop

RegularLoop creates a loop with the given number of vertices, all located on a circle of the specified radius around the given center.

func RegularLoopForFrame 

func RegularLoopForFrame(frame matrix3x3, radius s1.Angle, numVertices int) *Loop

RegularLoopForFrame creates a loop centered around the z-axis of the given coordinate frame, with the first vertex in the direction of the positive x-axis.

func (*Loop) Area 

func (l *Loop) Area() float64

Area returns the area of the loop interior, i.e. the region on the left side of the loop. The return value is between 0 and 4*pi. (Note that the return value is not affected by whether this loop is a "hole" or a "shell".)

func (*Loop) CanonicalFirstVertex 

func (l *Loop) CanonicalFirstVertex() (firstIdx, direction int)

CanonicalFirstVertex returns a first index and a direction (either +1 or -1) such that the vertex sequence (first, first+dir, ..., first+(n-1)*dir) does not change when the loop vertex order is rotated or inverted. This allows the loop vertices to be traversed in a canonical order. The return values are chosen such that (first, ..., first+n*dir) are in the range [0, 2*n-1] as expected by the Vertex method.

func (*Loop) CapBound 

func (l *Loop) CapBound() Cap

CapBound returns a bounding cap that may have more padding than the corresponding RectBound. The bound is conservative such that if the loop contains a point P, the bound also contains it.

func (*Loop) CellUnionBound 

func (l *Loop) CellUnionBound() []CellID

CellUnionBound computes a covering of the Loop.

func (*Loop) Centroid 

func (l *Loop) Centroid() Point

Centroid returns the true centroid of the loop multiplied by the area of the loop. The result is not unit length, so you may want to normalize it. Also note that in general, the centroid may not be contained by the loop.

We prescale by the loop area for two reasons: (1) it is cheaper to compute this way, and (2) it makes it easier to compute the centroid of more complicated shapes (by splitting them into disjoint regions and adding their centroids).

Note that the return value is not affected by whether this loop is a "hole" or a "shell".

func (*Loop) Chain 

func (l *Loop) Chain(chainID int) Chain

Chain returns the i-th edge chain in the Shape.

func (*Loop) ChainEdge 

func (l *Loop) ChainEdge(chainID, offset int) Edge

ChainEdge returns the j-th edge of the i-th edge chain.

func (*Loop) ChainPosition 

func (l *Loop) ChainPosition(edgeID int) ChainPosition

ChainPosition returns a ChainPosition pair (i, j) such that edgeID is the j-th edge of the Loop.

func (*Loop) ContainsCell 

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

ContainsCell reports whether the given Cell is contained by this Loop.

func (*Loop) ContainsNested 

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

ContainsNested reports whether the given loops is contained within this loop. This function does not test for edge intersections. The two loops must meet all of the Polygon requirements; for example this implies that their boundaries may not cross or have any shared edges (although they may have shared vertices).

func (*Loop) ContainsOrigin 

func (l *Loop) ContainsOrigin() bool

ContainsOrigin reports true if this loop contains s2.OriginPoint().

func (*Loop) ContainsPoint 

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

ContainsPoint returns true if the loop contains the point.

func (*Loop) Decode 

func (l *Loop) Decode(r io.Reader) error

Decode decodes a loop.

func (*Loop) Edge 

func (l *Loop) Edge(i int) Edge

Edge returns the endpoints for the given edge index.

func (Loop) Encode 

func (l Loop) Encode(w io.Writer) error

Encode encodes the Loop.

func (*Loop) HasInterior 

func (l *Loop) HasInterior() bool

HasInterior returns true because all loops have an interior.

func (*Loop) IntersectsCell 

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

IntersectsCell reports whether this Loop intersects the given cell.

func (*Loop) Invert 

func (l *Loop) Invert()

Invert reverses the order of the loop vertices, effectively complementing the region represented by the loop. For example, the loop ABCD (with edges AB, BC, CD, DA) becomes the loop DCBA (with edges DC, CB, BA, AD). Notice that the last edge is the same in both cases except that its direction has been reversed.

func (*Loop) IsEmpty 

func (l *Loop) IsEmpty() bool

IsEmpty reports true if this is the special "empty" loop that contains no points.

func (*Loop) IsFull 

func (l *Loop) IsFull() bool

IsFull reports true if this is the special "full" loop that contains all points.

func (*Loop) IsHole 

func (l *Loop) IsHole() bool

IsHole reports whether this loop represents a hole in its containing polygon.

func (*Loop) IsNormalized 

func (l *Loop) IsNormalized() bool

IsNormalized reports whether the loop area is at most 2*pi. Degenerate loops are handled consistently with Sign, i.e., if a loop can be expressed as the union of degenerate or nearly-degenerate CCW triangles, then it will always be considered normalized.

func (*Loop) IsValid 

func (l *Loop) IsValid() bool

IsValid reports whether this is a valid loop or not.

func (*Loop) Normalize 

func (l *Loop) Normalize()

Normalize inverts the loop if necessary so that the area enclosed by the loop is at most 2*pi.

func (*Loop) NumChains 

func (l *Loop) NumChains() int

NumChains reports the number of contiguous edge chains in the Loop.

func (*Loop) NumEdges 

func (l *Loop) NumEdges() int

NumEdges returns the number of edges in this shape.

func (*Loop) NumVertices 

func (l *Loop) NumVertices() int

NumVertices returns the number of vertices in this loop.

func (*Loop) OrientedVertex 

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

OrientedVertex returns the vertex in reverse order if the loop represents a polygon hole. For example, arguments 0, 1, 2 are mapped to vertices n-1, n-2, n-3, where n == len(vertices). This ensures that the interior of the polygon is always to the left of the vertex chain.

This requires: 0 <= i < 2 * len(vertices)

func (*Loop) RectBound 

func (l *Loop) RectBound() Rect

RectBound returns a tight bounding rectangle. If the loop contains the point, the bound also contains it.

func (*Loop) ReferencePoint 

func (l *Loop) ReferencePoint() ReferencePoint

ReferencePoint returns the reference point for this loop.

func (*Loop) Sign 

func (l *Loop) Sign() int

Sign returns -1 if this Loop represents a hole in its containing polygon, and +1 otherwise.

func (*Loop) TurningAngle 

func (l *Loop) TurningAngle() float64

TurningAngle returns the sum of the turning angles at each vertex. The return value is positive if the loop is counter-clockwise, negative if the loop is clockwise, and zero if the loop is a great circle. Degenerate and nearly-degenerate loops are handled consistently with Sign. So for example, if a loop has zero area (i.e., it is a very small CCW loop) then the turning angle will always be negative.

This quantity is also called the "geodesic curvature" of the loop.

func (*Loop) Vertex 

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

Vertex returns the vertex for the given index. For convenience, the vertex indices wrap automatically for methods that do index math such as Edge. i.e., Vertex(NumEdges() + n) is the same as Vertex(n).

func (*Loop) Vertices 

func (l *Loop) Vertices() []Point

Vertices returns the vertices in the loop.

type Metric 

type Metric struct {
	// Dim is either 1 or 2, for a 1D or 2D metric respectively.
	Dim int
	// Deriv is the scaling factor for the metric.
	Deriv float64
}

A Metric is a measure for cells. It is used to describe the shape and size of cells. They are useful for deciding which cell level to use in order to satisfy a given condition (e.g. that cell vertices must be no further than "x" apart). You can use the Value(level) method to compute the corresponding length or area on the unit sphere for cells at a given level. The minimum and maximum bounds are valid for cells at all levels, but they may be somewhat conservative for very large cells (e.g. face cells).

func (Metric) ClosestLevel 

func (m Metric) ClosestLevel(val float64) int

ClosestLevel returns the level at which the metric has approximately the given value. The return value is always a valid level. For example, AvgEdgeMetric.ClosestLevel(0.1) returns the level at which the average cell edge length is approximately 0.1.

func (Metric) MaxLevel 

func (m Metric) MaxLevel(val float64) int

MaxLevel returns the maximum level such that the metric is at least the given value, or zero if there is no such level.

For example, MaxLevel(0.1) returns the maximum level such that all cells have a minimum width of 0.1 or larger. The returned value is always a valid level.

In C++, this is called GetLevelForMinValue.

func (Metric) MinLevel 

func (m Metric) MinLevel(val float64) int

MinLevel returns the minimum level such that the metric is at most the given value, or maxLevel (30) if there is no such level.

For example, MinLevel(0.1) returns the minimum level such that all cell diagonal lengths are 0.1 or smaller. The returned value is always a valid level.

In C++, this is called GetLevelForMaxValue.

func (Metric) Value 

func (m Metric) Value(level int) float64

Value returns the value of the metric at the given level.

type PaddedCell 

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

PaddedCell represents a Cell whose (u,v)-range has been expanded on all sides by a given amount of "padding". Unlike Cell, its methods and representation are optimized for clipping edges against Cell boundaries to determine which cells are intersected by a given set of edges.

func PaddedCellFromCellID 

func PaddedCellFromCellID(id CellID, padding float64) *PaddedCell

PaddedCellFromCellID constructs a padded cell with the given padding.

func PaddedCellFromParentIJ 

func PaddedCellFromParentIJ(parent *PaddedCell, i, j int) *PaddedCell

PaddedCellFromParentIJ constructs the child of parent with the given (i,j) index. The four child cells have indices of (0,0), (0,1), (1,0), (1,1), where the i and j indices correspond to increasing u- and v-values respectively.

func (PaddedCell) Bound 

func (p PaddedCell) Bound() r2.Rect

Bound returns the bounds for this cell in (u,v)-space including padding.

func (PaddedCell) CellID 

func (p PaddedCell) CellID() CellID

CellID returns the CellID this padded cell represents.

func (PaddedCell) Center 

func (p PaddedCell) Center() Point

Center returns the center of this cell.

func (PaddedCell) ChildIJ 

func (p PaddedCell) ChildIJ(pos int) (i, j int)

ChildIJ returns the (i,j) coordinates for the child cell at the given traversal position. The traversal position corresponds to the order in which child cells are visited by the Hilbert curve.

func (PaddedCell) EntryVertex 

func (p PaddedCell) EntryVertex() Point

EntryVertex return the vertex where the space-filling curve enters this cell.

func (PaddedCell) ExitVertex 

func (p PaddedCell) ExitVertex() Point

ExitVertex returns the vertex where the space-filling curve exits this cell.

func (PaddedCell) Level 

func (p PaddedCell) Level() int

Level returns the level this cell is at.

func (*PaddedCell) Middle 

func (p *PaddedCell) Middle() r2.Rect

Middle returns the rectangle in the middle of this cell that belongs to all four of its children in (u,v)-space.

func (PaddedCell) Padding 

func (p PaddedCell) Padding() float64

Padding returns the amount of padding on this cell.

func (*PaddedCell) ShrinkToFit 

func (p *PaddedCell) ShrinkToFit(rect r2.Rect) CellID

ShrinkToFit returns the smallest CellID that contains all descendants of this padded cell whose bounds intersect the given rect. For algorithms that use recursive subdivision to find the cells that intersect a particular object, this method can be used to skip all of the initial subdivision steps where only one child needs to be expanded.

Note that this method is not the same as returning the smallest cell that contains the intersection of this cell with rect. Because of the padding, even if one child completely contains rect it is still possible that a neighboring child may also intersect the given rect.

The provided Rect must intersect the bounds of this cell.

type Point 

type Point struct {
	r3.Vector
}

Point represents a point on the unit sphere as a normalized 3D vector. Fields should be treated as read-only. Use one of the factory methods for creation.

func Interpolate 

func Interpolate(t float64, a, b Point) Point

Interpolate returns the point X along the line segment AB whose distance from A is the given fraction "t" of the distance AB. Does NOT require that "t" be between 0 and 1. Note that all distances are measured on the surface of the sphere, so this is more complicated than just computing (1-t)*a + t*b and normalizing the result.

func InterpolateAtDistance 

func InterpolateAtDistance(ax s1.Angle, a, b Point) Point

InterpolateAtDistance returns the point X along the line segment AB whose distance from A is the angle ax.

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

PlanarCentroid returns the centroid of the planar triangle ABC, which is not normalized. It 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 in TrueCentroid comments).

Note that the surface centroid may be nowhere near the intuitive "center" of a spherical triangle. For example, consider the triangle with vertices A=(1,eps,0), B=(0,0,1), C=(-1,eps,0) (a quarter-sphere). The surface centroid of this triangle is at S=(0, 2*eps, 1), which is within a distance of 2*eps of the vertex B. Note that the median from A (the segment connecting A to the midpoint of BC) passes through S, since this is the shortest path connecting the two endpoints. On the other hand, the true centroid is at M=(0, 0.5, 0.5), which when projected onto the surface is a much more reasonable interpretation of the "center" of this triangle.

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 PointFromLatLng 

func PointFromLatLng(ll LatLng) Point

PointFromLatLng returns an Point for the given LatLng. The maximum error in the result is 1.5 * dblEpsilon. (This does not include the error of converting degrees, E5, E6, or E7 into radians.)

func Project 

func Project(x, a, b Point) Point

Project returns the point along the edge AB that is closest to the point X. The fractional distance of this point along the edge AB can be obtained using DistanceFraction.

This requires that all points are unit length.

func Rotate 

func Rotate(p, axis Point, angle s1.Angle) Point

Rotate the given point about the given axis by the given angle. p and axis must be unit length; angle has no restrictions (e.g., it can be positive, negative, greater than 360 degrees, etc).

func TrueCentroid 

func TrueCentroid(a, b, c Point) Point

TrueCentroid returns the true centroid of the spherical triangle ABC multiplied by the signed area of spherical triangle ABC. The result is not normalized. The reasons for multiplying by the signed area are (1) this is the quantity that needs to be summed to compute the centroid of a union or difference of triangles, and (2) it's actually easier to calculate this way. All points must have unit length.

The true centroid (mass centroid) is defined as the surface integral over the spherical triangle of (x,y,z) divided by the triangle area. This is the point that the triangle would rotate around if it was spinning in empty space.

The best centroid for most purposes is the true centroid. Unlike the planar and surface centroids, the true centroid behaves linearly as regions are added or subtracted. That is, if you split a triangle into pieces and compute the average of their centroids (weighted by triangle area), the result equals the centroid of the original triangle. This is not true of the other centroids.

func (Point) ApproxEqual 

func (p Point) ApproxEqual(other Point) bool

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

func (Point) CapBound 

func (p Point) CapBound() Cap

CapBound returns a bounding cap for this point.

func (Point) CellUnionBound 

func (p Point) CellUnionBound() []CellID

CellUnionBound computes a covering of the Point.

func (Point) Contains 

func (p Point) Contains(other Point) bool

Contains reports if this Point contains the other Point. (This method matches all other s2 types where the reflexive Contains method does not contain the type's name.)

func (Point) ContainsCell 

func (p Point) ContainsCell(c Cell) bool

ContainsCell returns false as Points do not contain any other S2 types.

func (Point) ContainsPoint 

func (p Point) ContainsPoint(other Point) bool

ContainsPoint reports if this Point contains the other Point. (This method is named to satisfy the Region interface.)

func (Point) Distance 

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

Distance returns the angle between two points.

func (Point) Encode 

func (p Point) Encode(w io.Writer) error

Encode encodes the Point.

func (Point) IntersectsCell 

func (p Point) IntersectsCell(c Cell) bool

IntersectsCell reports whether this Point intersects the given cell.

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.

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

func (Point) RectBound 

func (p Point) RectBound() Rect

RectBound returns a bounding latitude-longitude rectangle from this point.

type Polygon 

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

Polygon represents a sequence of zero or more loops; recall that the interior of a loop is defined to be its left-hand side (see Loop).

When the polygon is initialized, the given loops are automatically converted into a canonical form consisting of "shells" and "holes". Shells and holes are both oriented CCW, and are nested hierarchically. The loops are reordered to correspond to a pre-order traversal of the nesting hierarchy.

Polygons may represent any region of the sphere with a polygonal boundary, including the entire sphere (known as the "full" polygon). The full polygon consists of a single full loop (see Loop), whereas the empty polygon has no loops at all.

Use FullPolygon() to construct a full polygon. The zero value of Polygon is treated as the empty polygon.

Polygons have the following restrictions:

  • Loops may not cross, i.e. the boundary of a loop may not intersect both the interior and exterior of any other loop.

  • Loops may not share edges, i.e. if a loop contains an edge AB, then no other loop may contain AB or BA.

  • Loops may share vertices, however no vertex may appear twice in a single loop (see Loop).

  • No loop may be empty. The full loop may appear only in the full polygon.

func FullPolygon 

func FullPolygon() *Polygon

FullPolygon returns a special "full" polygon.

func PolygonFromCell 

func PolygonFromCell(cell Cell) *Polygon

PolygonFromCell returns a Polygon from a single loop created from the given Cell.

func PolygonFromLoops 

func PolygonFromLoops(loops []*Loop) *Polygon

PolygonFromLoops constructs a polygon from the given set of loops. The polygon interior consists of the points contained by an odd number of loops. (Recall that a loop contains the set of points on its left-hand side.)

This method determines the loop nesting hierarchy and assigns every loop a depth. Shells have even depths, and holes have odd depths.

Note: The given set of loops are reordered by this method so that the hierarchy can be traversed using Parent, LastDescendant and the loops depths.

func (*Polygon) CapBound 

func (p *Polygon) CapBound() Cap

CapBound returns a bounding spherical cap.

func (*Polygon) CellUnionBound 

func (p *Polygon) CellUnionBound() []CellID

CellUnionBound computes a covering of the Polygon.

func (*Polygon) Chain 

func (p *Polygon) Chain(chainID int) Chain

Chain returns the i-th edge Chain (loop) in the Shape.

func (*Polygon) ChainEdge 

func (p *Polygon) ChainEdge(i, j int) Edge

ChainEdge returns the j-th edge of the i-th edge Chain (loop).

func (*Polygon) ChainPosition 

func (p *Polygon) ChainPosition(edgeID int) ChainPosition

ChainPosition returns a pair (i, j) such that edgeID is the j-th edge of the i-th edge Chain.

func (*Polygon) ContainsCell 

func (p *Polygon) ContainsCell(cell Cell) bool

ContainsCell reports whether the polygon contains the given cell.

func (*Polygon) ContainsPoint 

func (p *Polygon) ContainsPoint(point Point) bool

ContainsPoint reports whether the polygon contains the point.

func (*Polygon) Decode 

func (p *Polygon) Decode(r io.Reader) error

Decode decodes the Polygon.

func (*Polygon) Edge 

func (p *Polygon) Edge(e int) Edge

Edge returns endpoints for the given edge index.

func (*Polygon) Encode 

func (p *Polygon) Encode(w io.Writer) error

Encode encodes the Polygon

func (*Polygon) HasInterior 

func (p *Polygon) HasInterior() bool

HasInterior reports whether this Polygon has an interior.

func (*Polygon) IntersectsCell 

func (p *Polygon) IntersectsCell(cell Cell) bool

IntersectsCell reports whether the polygon intersects the given cell.

func (*Polygon) IsEmpty 

func (p *Polygon) IsEmpty() bool

IsEmpty reports whether this is the special "empty" polygon (consisting of no loops).

func (*Polygon) IsFull 

func (p *Polygon) IsFull() bool

IsFull reports whether this is the special "full" polygon (consisting of a single loop that encompasses the entire sphere).

func (*Polygon) LastDescendant 

func (p *Polygon) LastDescendant(k int) int

LastDescendant returns the index of the last loop that is contained within loop k. If k is negative, it returns the last loop in the polygon. Note that loops are indexed according to a pre-order traversal of the nesting hierarchy, so the immediate children of loop k can be found by iterating over the loops (k+1)..LastDescendant(k) and selecting those whose depth is equal to Loop(k).depth+1.

func (*Polygon) Loop 

func (p *Polygon) Loop(k int) *Loop

Loop returns the loop at the given index. Note that during initialization, the given loops are reordered according to a pre-order traversal of the loop nesting hierarchy. This implies that every loop is immediately followed by its descendants. This hierarchy can be traversed using the methods Parent, LastDescendant, and Loop.depth.

func (*Polygon) Loops 

func (p *Polygon) Loops() []*Loop

Loops returns the loops in this polygon.

func (*Polygon) NumChains 

func (p *Polygon) NumChains() int

NumChains reports the number of contiguous edge chains in the Polygon.

func (*Polygon) NumEdges 

func (p *Polygon) NumEdges() int

NumEdges returns the number of edges in this shape.

func (*Polygon) NumLoops 

func (p *Polygon) NumLoops() int

NumLoops returns the number of loops in this polygon.

func (*Polygon) Parent 

func (p *Polygon) Parent(k int) (index int, ok bool)

Parent returns the index of the parent of loop k. If the loop does not have a parent, ok=false is returned.

func (*Polygon) RectBound 

func (p *Polygon) RectBound() Rect

RectBound returns a bounding latitude-longitude rectangle.

func (*Polygon) ReferencePoint 

func (p *Polygon) ReferencePoint() ReferencePoint

ReferencePoint returns the reference point for this polygon.

type Polyline 

type Polyline []Point

Polyline represents a sequence of zero or more vertices connected by straight edges (geodesics). Edges of length 0 and 180 degrees are not allowed, i.e. adjacent vertices should not be identical or antipodal.

func PolylineFromLatLngs 

func PolylineFromLatLngs(points []LatLng) *Polyline

PolylineFromLatLngs creates a new Polyline from the given LatLngs.

func (*Polyline) CapBound 

func (p *Polyline) CapBound() Cap

CapBound returns the bounding Cap for this Polyline.

func (*Polyline) CellUnionBound 

func (p *Polyline) CellUnionBound() []CellID

CellUnionBound computes a covering of the Polyline.

func (*Polyline) Centroid 

func (p *Polyline) Centroid() Point

Centroid returns the true centroid of the polyline multiplied by the length of the polyline. The result is not unit length, so you may wish to normalize it.

Scaling by the Polyline length makes it easy to compute the centroid of several Polylines (by simply adding up their centroids).

func (*Polyline) Chain 

func (p *Polyline) Chain(chainID int) Chain

Chain returns the i-th edge Chain in the Shape.

func (*Polyline) ChainEdge 

func (p *Polyline) ChainEdge(chainID, offset int) Edge

ChainEdge returns the j-th edge of the i-th edge Chain.

func (*Polyline) ChainPosition 

func (p *Polyline) ChainPosition(edgeID int) ChainPosition

ChainPosition returns a pair (i, j) such that edgeID is the j-th edge

func (*Polyline) ContainsCell 

func (p *Polyline) ContainsCell(cell Cell) bool

ContainsCell reports whether this Polyline contains the given Cell. Always returns false because "containment" is not numerically well-defined except at the Polyline vertices.

func (*Polyline) ContainsPoint 

func (p *Polyline) ContainsPoint(point Point) bool

ContainsPoint returns false since Polylines are not closed.

func (*Polyline) Decode 

func (p *Polyline) Decode(r io.Reader) error

Decode decodes the polyline.

func (*Polyline) Edge 

func (p *Polyline) Edge(i int) Edge

Edge returns endpoints for the given edge index.

func (Polyline) Encode 

func (p Polyline) Encode(w io.Writer) error

Encode encodes the Polyline.

func (*Polyline) Equals 

func (p *Polyline) Equals(b *Polyline) bool

Equals reports whether the given Polyline is exactly the same as this one.

func (*Polyline) HasInterior 

func (p *Polyline) HasInterior() bool

HasInterior returns false as Polylines are not closed.

func (*Polyline) IntersectsCell 

func (p *Polyline) IntersectsCell(cell Cell) bool

IntersectsCell reports whether this Polyline intersects the given Cell.

func (*Polyline) Length 

func (p *Polyline) Length() s1.Angle

Length returns the length of this Polyline.

func (*Polyline) NumChains 

func (p *Polyline) NumChains() int

NumChains reports the number of contiguous edge chains in this Polyline.

func (*Polyline) NumEdges 

func (p *Polyline) NumEdges() int

NumEdges returns the number of edges in this shape.

func (*Polyline) RectBound 

func (p *Polyline) RectBound() Rect

RectBound returns the bounding Rect for this Polyline.

func (*Polyline) ReferencePoint 

func (p *Polyline) ReferencePoint() ReferencePoint

ReferencePoint returns the default reference point with negative containment because Polylines are not closed.

func (*Polyline) Reverse 

func (p *Polyline) Reverse()

Reverse reverses the order of the Polyline vertices.

func (*Polyline) SubsampleVertices 

func (p *Polyline) SubsampleVertices(tolerance s1.Angle) []int

SubsampleVertices returns a subsequence of vertex indices such that the polyline connecting these vertices is never further than the given tolerance from the original polyline. Provided the first and last vertices are distinct, they are always preserved; if they are not, the subsequence may contain only a single index.

Some useful properties of the algorithm:

  • It runs in linear time.

  • The output always represents a valid polyline. In particular, adjacent output vertices are never identical or antipodal.

  • The method is not optimal, but it tends to produce 2-3% fewer vertices than the Douglas-Peucker algorithm with the same tolerance.

  • The output is parametrically equivalent to the original polyline to within the given tolerance. For example, if a polyline backtracks on itself and then proceeds onwards, the backtracking will be preserved (to within the given tolerance). This is different than the Douglas-Peucker algorithm which only guarantees geometric equivalence.

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 ExpandForSubregions 

func ExpandForSubregions(bound Rect) Rect

ExpandForSubregions expands a bounding Rect so that it is guaranteed to contain the bounds of any subregion whose bounds are computed using ComputeRectBound. For example, consider a loop L that defines a square. GetBound ensures that if a point P is contained by this square, then LatLngFromPoint(P) is contained by the bound. But now consider a diamond shaped loop S contained by L. It is possible that GetBound returns a *larger* bound for S than it does for L, due to rounding errors. This method expands the bound for L so that it is guaranteed to contain the bounds of any subregion S.

More precisely, if L is a loop that does not contain either pole, and S is a loop such that L.Contains(S), then 

ExpandForSubregions(L.RectBound).Contains(S.RectBound).

func 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 (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 cap that countains Rect.

func (Rect) CellUnionBound 

func (r Rect) CellUnionBound() []CellID

CellUnionBound computes a covering of the Rect.

func (Rect) Center 

func (r Rect) Center() LatLng

Center returns the center of the rectangle.

func (Rect) Contains 

func (r Rect) Contains(other Rect) bool

Contains reports whether this Rect contains the other Rect.

func (Rect) ContainsCell 

func (r Rect) ContainsCell(c Cell) bool

ContainsCell reports whether the given Cell is contained by this Rect.

func (Rect) ContainsLatLng 

func (r Rect) ContainsLatLng(ll LatLng) bool

ContainsLatLng reports whether the given LatLng is within the Rect.

func (Rect) ContainsPoint 

func (r Rect) ContainsPoint(p Point) bool

ContainsPoint reports whether the given Point is within the Rect.

func (*Rect) Decode 

func (r *Rect) Decode(rd io.Reader) error

Decode decodes a rectangle.

func (Rect) Encode 

func (r Rect) Encode(w io.Writer) error

Encode encodes the Rect.

func (Rect) Hi 

func (r Rect) Hi() LatLng

Hi returns the other corner of the rectangle.

func (Rect) Intersection 

func (r Rect) Intersection(other Rect) Rect

Intersection returns the smallest rectangle containing the intersection of this rectangle and the given rectangle. Note that the region of intersection may consist of two disjoint rectangles, in which case a single rectangle spanning both of them is returned.

func (Rect) Intersects 

func (r Rect) Intersects(other Rect) bool

Intersects reports whether this rectangle and the other have any points in common.

func (Rect) IntersectsCell 

func (r Rect) IntersectsCell(c Cell) bool

IntersectsCell reports whether this rectangle intersects the given cell. This is an exact test and may be fairly expensive.

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

func (r Rect) PolarClosure() Rect

PolarClosure returns the rectangle unmodified if it does not include either pole. If it includes either pole, PolarClosure returns an expansion of the rectangle along the longitudinal range to include all possible representations of the contained poles.

func (Rect) RectBound 

func (r Rect) RectBound() Rect

RectBound returns itself.

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

Union returns the smallest Rect containing the union of this rectangle and the given rectangle.

func (Rect) Vertex 

func (r Rect) Vertex(i int) LatLng

Vertex returns the i-th vertex of the rectangle (i = 0,1,2,3) in CCW order (lower left, lower right, upper right, upper left).

type RectBounder 

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

RectBounder is used to compute a bounding rectangle that contains all edges defined by a vertex chain (v0, v1, v2, ...). All vertices must be unit length. Note that the bounding rectangle of an edge can be larger than the bounding rectangle of its endpoints, e.g. consider an edge that passes through the North Pole.

The bounds are calculated conservatively to account for numerical errors when points are converted to LatLngs. More precisely, this function guarantees the following: Let L be a closed edge chain (Loop) such that the interior of the loop does not contain either pole. Now if P is any point such that L.ContainsPoint(P), then RectBound(L).ContainsPoint(LatLngFromPoint(P)).

func NewRectBounder 

func NewRectBounder() *RectBounder

NewRectBounder returns a new instance of a RectBounder.

func (*RectBounder) AddPoint 

func (r *RectBounder) AddPoint(b Point)

AddPoint adds the given point to the chain. The Point must be unit length.

func (*RectBounder) RectBound 

func (r *RectBounder) RectBound() Rect

RectBound returns the bounding rectangle of the edge chain that connects the vertices defined so far. This bound satisfies the guarantee made above, i.e. if the edge chain defines a Loop, then the bound contains the LatLng coordinates of all Points contained by the loop.

type ReferencePoint 

type ReferencePoint struct {
	Point     Point
	Contained bool
}

A ReferencePoint consists of a point and a boolean indicating whether the point is contained by a particular shape.

func OriginReferencePoint 

func OriginReferencePoint(contained bool) ReferencePoint

OriginReferencePoint returns a ReferencePoint with the given value for contained and the origin point. It should be used when all points or no points are contained.

type Region 

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

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

	// ContainsPoint reports whether the region contains the given point or not.
	// The point should be unit length, although some implementations may relax
	// this restriction.
	ContainsPoint(p Point) bool

	// CellUnionBound returns a small collection of CellIDs whose union covers
	// the region. The cells are not sorted, may have redundancies (such as cells
	// that contain other cells), and may cover much more area than necessary.
	//
	// This method is not intended for direct use by client code. Clients
	// should typically use Covering, which has options to control the size and
	// accuracy of the covering. Alternatively, if you want a fast covering and
	// don't care about accuracy, consider calling FastCovering (which returns a
	// cleaned-up version of the covering computed by this method).
	//
	// CellUnionBound implementations should attempt to return a small
	// covering (ideally 4 cells or fewer) that covers the region and can be
	// computed quickly. The result is used by RegionCoverer as a starting
	// point for further refinement.
	CellUnionBound() []CellID
}

A Region represents a 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 {
	MinLevel int // the minimum cell level to be used.
	MaxLevel int // the maximum cell level to be used.
	LevelMod int // the LevelMod to be used.
	MaxCells int // the maximum desired number of cells in the approximation.
}

func (*RegionCoverer) CellUnion 

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

CellUnion returns a normalized CellUnion that covers the given region and satisfies the restrictions except for minLevel and levelMod. These criteria cannot be satisfied using a cell union because cell unions are automatically normalized by replacing four child cells with their parent whenever possible. (Note that the list of cell ids passed to the CellUnion constructor does in fact satisfy all the given restrictions.)

func (*RegionCoverer) Covering 

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

Covering returns a CellUnion that covers the given region and satisfies the various restrictions.

func (*RegionCoverer) FastCovering 

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

这个函数作为递归细分 cell 的起点，非常管用。

func (*RegionCoverer) InteriorCellUnion 

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

InteriorCellUnion returns a normalized CellUnion that is contained within the given region and satisfies the restrictions except for minLevel and levelMod. These criteria cannot be satisfied using a cell union because cell unions are automatically normalized by replacing four child cells with their parent whenever possible. (Note that the list of cell ids passed to the CellUnion constructor does in fact satisfy all the given restrictions.)

func (*RegionCoverer) InteriorCovering 

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

InteriorCovering returns a CellUnion that is contained within the given region and satisfies the various restrictions.

type Shape 

type Shape interface {
	// NumEdges returns the number of edges in this shape.
	NumEdges() int

	// Edge returns the edge for the given edge index.
	Edge(i int) Edge

	// HasInterior reports whether this shape has an interior.
	HasInterior() bool

	// ReferencePoint returns an arbitrary reference point for the shape. (The
	// containment boolean value must be false for shapes that do not have an interior.)
	//
	// This reference point may then be used to compute the containment of other
	// points by counting edge crossings.
	ReferencePoint() ReferencePoint

	// NumChains reports the number of contiguous edge chains in the shape.
	// For example, a shape whose edges are [AB, BC, CD, AE, EF] would consist
	// of two chains (AB,BC,CD and AE,EF). Every chain is assigned a chain Id
	// numbered sequentially starting from zero.
	//
	// Note that it is always acceptable to implement this method by returning
	// NumEdges, i.e. every chain consists of a single edge, but this may
	// reduce the efficiency of some algorithms.
	NumChains() int

	// Chain returns the range of edge IDs corresponding to the given edge chain.
	// Edge chains must consist of contiguous, non-overlapping ranges that cover
	// the entire range of edge IDs. This is spelled out more formally below:
	//
	//  0 <= i < NumChains()
	//  Chain(i).length > 0, for all i
	//  Chain(0).start == 0
	//  Chain(i).start + Chain(i).length == Chain(i+1).start, for i < NumChains()-1
	//  Chain(i).start + Chain(i).length == NumEdges(), for i == NumChains()-1
	Chain(chainID int) Chain

	// ChainEdgeReturns the edge at offset "offset" within edge chain "chainID".
	// Equivalent to "shape.Edge(shape.Chain(chainID).start + offset)"
	// but more efficient.
	ChainEdge(chainID, offset int) Edge

	// ChainPosition finds the chain containing the given edge, and returns the
	// position of that edge as a ChainPosition(chainID, offset) pair.
	//
	//  shape.Chain(pos.chainID).start + pos.offset == edgeID
	//  shape.Chain(pos.chainID+1).start > edgeID
	//
	// where pos == shape.ChainPosition(edgeID).
	ChainPosition(edgeID int) ChainPosition
	// contains filtered or unexported methods
}

Shape defines an interface for any S2 type that needs to be indexable. A shape is a collection of edges that optionally defines an interior. It can be used to represent a set of points, a set of polylines, or a set of polygons.

The edges of a Shape are indexed by a contiguous range of edge IDs starting at 0. The edges are further subdivided into chains, where each chain consists of a sequence of edges connected end-to-end (a polyline). Shape has methods that allow edges to be accessed either using the global numbering (edge ID) or within a particular chain. The global numbering is sufficient for most purposes, but the chain representation is useful for certain algorithms such as intersection (see BoundaryOperation).

type ShapeIndex 

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

ShapeIndex indexes a set of Shapes, where a Shape is some collection of edges that optionally defines an interior. It can be used to represent a set of points, a set of polylines, or a set of polygons. For Shapes that have interiors, the index makes it very fast to determine which Shape(s) contain a given point or region.

The index can be updated incrementally by adding or removing shapes. It is designed to handle up to hundreds of millions of edges. All data structures are designed to be small, so the index is compact; generally it is smaller than the underlying data being indexed. The index is also fast to construct.

Polygon, Loop, and Polyline implement Shape which allows these objects to be indexed easily. You can find useful query methods in CrossingEdgeQuery and ClosestEdgeQuery (Not yet implemented in Go).

Example showing how to build an index of Polylines: 

index := NewShapeIndex()
for _, polyline := range polylines {
    index.Add(polyline);
}
// Now you can use a CrossingEdgeQuery or ClosestEdgeQuery here.

func NewShapeIndex 

func NewShapeIndex() *ShapeIndex

NewShapeIndex creates a new ShapeIndex.

func (*ShapeIndex) Add 

func (s *ShapeIndex) Add(shape Shape)

Add adds the given shape to the index.

func (*ShapeIndex) Begin 

func (s *ShapeIndex) Begin() *ShapeIndexIterator

Begin positions the iterator at the first cell in the index.

func (*ShapeIndex) End 

func (s *ShapeIndex) End() *ShapeIndexIterator

End positions the iterator at the last cell in the index.

func (*ShapeIndex) IsFresh 

func (s *ShapeIndex) IsFresh() bool

IsFresh reports if there are no pending updates that need to be applied. This can be useful to avoid building the index unnecessarily, or for choosing between two different algorithms depending on whether the index is available.

The returned index status may be slightly out of date if the index was built in a different thread. This is fine for the intended use (as an efficiency hint), but it should not be used by internal methods.

func (*ShapeIndex) Iterator 

func (s *ShapeIndex) Iterator() *ShapeIndexIterator

Iterator returns an iterator for this index.

func (*ShapeIndex) Len 

func (s *ShapeIndex) Len() int

Len reports the number of Shapes in this index.

func (*ShapeIndex) NumEdges 

func (s *ShapeIndex) NumEdges() int

NumEdges returns the number of edges in this index.

func (*ShapeIndex) Remove 

func (s *ShapeIndex) Remove(shape Shape)

Remove removes the given shape from the index.

func (*ShapeIndex) Reset 

func (s *ShapeIndex) Reset()

Reset resets the index to its original state.

func (*ShapeIndex) Shape 

func (s *ShapeIndex) Shape(id int32) Shape

Shape returns the shape with the given ID, or nil if the shape has been removed from the index.

type ShapeIndexCell 

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

ShapeIndexCell stores the index contents for a particular CellID.

func NewShapeIndexCell 

func NewShapeIndexCell(numShapes int) *ShapeIndexCell

NewShapeIndexCell creates a new cell that is sized to hold the given number of shapes.

type ShapeIndexIterator 

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

ShapeIndexIterator is an iterator that provides low-level access to the cells of the index. Cells are returned in increasing order of CellID. 

for it := index.Iterator(); !it.Done(); it.Next() {
  fmt.Print(it.CellID())
}

func (*ShapeIndexIterator) AtBegin 

func (s *ShapeIndexIterator) AtBegin() bool

AtBegin reports if the iterator is positioned at the first index cell.

func (*ShapeIndexIterator) CellID 

func (s *ShapeIndexIterator) CellID() CellID

CellID returns the CellID of the cell at the current position of the iterator.

func (*ShapeIndexIterator) Center 

func (s *ShapeIndexIterator) Center() Point

Center returns the Point at the center of the current position of the iterator.

func (*ShapeIndexIterator) Done 

func (s *ShapeIndexIterator) Done() bool

Done reports if the iterator is positioned at or after the last index cell.

func (*ShapeIndexIterator) IndexCell 

func (s *ShapeIndexIterator) IndexCell() *ShapeIndexCell

IndexCell returns the ShapeIndexCell at the current position of the iterator.

func (*ShapeIndexIterator) LocateCellID 

func (s *ShapeIndexIterator) LocateCellID(target CellID) CellRelation

LocateCellID attempts to position the iterator at the first matching indexCell in the index that has some relation to the given CellID. Let T be the target CellID. If T is contained by (or equal to) some index cell I, then the iterator is positioned at I and returns Indexed. Otherwise if T contains one or more (smaller) index cells, then position the iterator at the first such cell I and return Subdivided. Otherwise Disjoint is returned and the iterator position is undefined.

func (*ShapeIndexIterator) LocatePoint 

func (s *ShapeIndexIterator) LocatePoint(p Point) bool

LocatePoint positions the iterator at the cell that contains the given Point. If no such cell exists, the iterator position is unspecified, and false is returned. The cell at the matched position is guaranteed to contain all edges that might intersect the line segment between target and the cell's center.

func (*ShapeIndexIterator) Next 

func (s *ShapeIndexIterator) Next()

Next advances the iterator to the next cell in the index.

func (*ShapeIndexIterator) Prev 

func (s *ShapeIndexIterator) Prev()

Prev advances the iterator to the previous cell in the index. If the iterator is at the first cell the call does nothing.

func (*ShapeIndexIterator) Reset 

func (s *ShapeIndexIterator) Reset()

Reset the iterator to be positioned at the first cell in the index.

type WedgeRel 

type WedgeRel int

WedgeRel enumerates the possible relation between two wedges A and B. 

const (
	WedgeEquals              WedgeRel = iota // A and B are equal.
	WedgeProperlyContains                    // A is a strict superset of B.
	WedgeIsProperlyContained                 // A is a strict subset of B.
	WedgeProperlyOverlaps                    // A-B, B-A, and A intersect B are non-empty.
	WedgeIsDisjoint                          // A and B are disjoint.
)

Define the different possible relationships between two wedges.

Given an edge chain (x0, x1, x2), the wedge at x1 is the region to the left of the edges. More precisely, it is the set of all rays from x1x0 (inclusive) to x1x2 (exclusive) in the *clockwise* direction.

func WedgeRelation 

func WedgeRelation(a0, ab1, a2, b0, b2 Point) WedgeRel

WedgeRelation reports the relation between two non-empty wedges A=(a0, ab1, a2) and B=(b0, ab1, b2).

Notes

Bugs

  • The differences from the C++ version FloodFill, SimpleCovering

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.