Class S2Loop
An S2Loop represents a simple spherical polygon. It consists of a single chain of vertices where the first vertex is implicitly connected to the last. All loops are defined to have a CCW orientation, i.e. the interior of the 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). Non-adjacent edges are not allowed to intersect, and furthermore edges of length 180 degrees are not allowed (i.e., adjacent vertices cannot be antipodal). Loops must have at least 3 vertices (except for the "empty" and "full" loops discussed below). Although these restrictions are not enforced in optimized code, you may get unexpected results if they are violated.
There are two special loops: the "empty" loop contains no points, while 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 kEmpty and kFull).
Point containment of loops is defined such that if the sphere is subdivided into faces (loops), every point is contained by exactly one face. This implies that loops do not necessarily contain their vertices.
Constructors
| Name | Description |
|---|---|
this
()
|
Default constructor. The loop must be initialized by calling Init() or Decode() before it is used. |
this
(vertices, s2DebugOverride)
|
Convenience constructor that calls Init() with the given vertices. |
this
(cell)
|
Construct a loop corresponding to the given cell. |
Properties
| Name | Type | Description |
|---|---|---|
s2DebugOverride[set]
|
s2 | Allows overriding the automatic validity checks controlled by the --s2debug flag. If this flag is true, then loops are automatically checked for validity as they are initialized. The main reason to disable this flag is if you intend to call IsValid() explicitly, like this: |
Methods
| Name | Description |
|---|---|
boundaryApproxEquals
(b, max_error)
|
Returns true if two loops have the same boundary except for vertex perturbations. More precisely, the vertices in the two loops must be in the same cyclic order, and corresponding vertex pairs must be separated by no more than "max_error". |
boundaryEquals
(b)
|
Returns true if two loops have the same boundary. This is true if and only if the loops have the same vertices in the same cyclic order (i.e., the vertices may be cyclically rotated). The empty and full loops are considered to have different boundaries. |
boundaryNear
(b, max_error)
|
Returns true if the two loop boundaries are within "max_error" of each other along their entire lengths. The two loops may have different numbers of vertices. More precisely, this method returns true if the two loops have parameterizations a:[0,1] -> S^2, b:[0,1] -> S^2 such that distance(a(t), b(t)) <= max_error for all t. You can think of this as testing whether it is possible to drive two cars all the way around the two loops such that no car ever goes backward and the cars are always within "max_error" of each other. |
clone
()
|
|
compareBoundary
(b)
|
Return +1 if A contains the boundary of B, -1 if A excludes the boundary of B, and 0 if the boundaries of A and B cross. Shared edges are handled as follows: If XY is a shared edge, define Reversed(XY) to be true if XY appears in opposite directions in A and B. Then A contains XY if and only if Reversed(XY) == B->is_hole(). (Intuitively, this checks whether A contains a vanishingly small region extending from the boundary of B toward the interior of the polygon to which loop B belongs.) |
contains
(b)
|
Returns true if the region contained by this loop is a superset of the region contained by the given other loop. |
containsNested
(b)
|
Given two loops of a polygon, return true if A contains B. This version of Contains() is cheap because it does not test for edge intersections. The loops must meet all the S2Polygon requirements; for example this implies that their boundaries may not cross or have any shared edges (although they may have shared vertices). |
decode
(decoder)
|
Decodes a loop encoded with Encode() or the private method EncodeCompressed() (used by the S2Polygon encoder). Returns true on success. |
depth
()
|
The depth of a loop is defined as its nesting level within its containing polygon. "Outer shell" loops have depth 0, holes within those loops have depth 1, shells within those holes have depth 2, etc. This field is only used by the S2Polygon implementation. |
empty
()
|
A special vertex chain of length 1 that creates an empty loop (i.e., a loop with no edges that contains no points). Example usage: |
encode
(encoder)
|
Appends a serialized representation of the S2Loop to "encoder". |
equals
(b)
|
Returns true if two loops have the same vertices in the same linear order (i.e., cyclic rotations are not allowed). |
findValidationError
(error)
|
Returns true if this is *not* a valid loop and sets "error" appropriately. Otherwise returns false and leaves "error" unchanged. |
findValidationErrorNoIndex
(error)
|
Like FindValidationError(), but skips any checks that would require building the S2ShapeIndex (i.e., self-intersection tests). This is used by the S2Polygon implementation, which uses its own index to check for loop self-intersections. |
full
()
|
A special vertex chain of length 1 that creates a full loop (i.e., a loop with no edges that contains all points). See kEmpty() for details. |
getArea
()
|
Return the area of the loop interior, i.e. the region on the left side of the loop. The return value is between 0 and 4*Pi. (Note that the return value is not affected by whether this loop is a "hole" or a "shell".) |
getCapBound
()
|
GetRectBound() returns essentially tight results, while GetCapBound() might have a lot of extra padding. Both bounds are conservative in that if the loop contains a point P, then the bound contains P also. |
getCentroid
()
|
Returns the true centroid of the loop multiplied by the area of the loop (see s2centroids.h for details on centroids). 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. |
getDistance
(x)
|
Returns the distance from the given point to the loop interior. If the loop is empty, return S1Angle::Infinity(). "x" should be unit length. |
getDistanceToBoundary
(x)
|
Returns the distance from the given point to the loop boundary. If the loop is empty or full, return S1Angle::Infinity() (since the loop has no boundary). "x" should be unit length. |
getSurfaceIntegral
(fTri)
|
This method computes the oriented surface integral of some quantity f(x) over the loop interior, given a function f_tri(A,B,C) that returns the corresponding integral over the spherical triangle ABC. Here "oriented surface integral" means: |
getTurningAngle
()
|
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 s2pred::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. |
getTurningAngleMaxError
()
|
Return the maximum error in GetTurningAngle(). The return value is not constant; it depends on the loop. |
initialize
(vertexRange)
|
Initialize a loop with given vertices. The last vertex is implicitly connected to the first. All points should be unit length. Loops must have at least 3 vertices (except for the "empty" and "full" loops, see kEmpty and kFull). This method may be called multiple times. |
intersects
(b)
|
Returns true if the region contained by this loop intersects the region contained by the given other loop. |
invert
()
|
Reverse 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. |
isEmpty
()
|
Returns true if this is the special "empty" loop that contains no points. |
isEmptyOrFull
()
|
Returns true if this loop is either "empty" or "full". |
isFull
()
|
Returns true if this is the special "full" loop that contains all points. |
isHole
()
|
Returns true if this loop represents a hole in its containing polygon. |
isNormalized
()
|
Return true if the loop area is at most 2*Pi. Degenerate loops are handled consistently with s2pred::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. |
isValid
()
|
Returns true if this is a valid loop. Note that validity is checked automatically during initialization when --s2debug is enabled (true by default in debug binaries). |
makeRegularLoop
(center, radius, num_vertices)
|
Constructs a regular polygon with the given number of vertices, all located on a circle of the specified radius around "center". The radius is the actual distance from "center" to each vertex. |
makeRegularLoop
(frame, radius, num_vertices)
|
Like the function above, but this version constructs a loop centered around the z-axis of the given coordinate frame, with the first vertex in the direction of the positive x-axis. (This allows the loop to be rotated for testing purposes.) |
normalize
()
|
Invert the loop if necessary so that the area enclosed by the loop is at most 2*Pi. |
orientedVertex
(i)
|
Like vertex(), but this method returns vertices 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 == num_vertices(). This ensures that the interior of the polygon is always to the left of the vertex chain. |
project
(x)
|
If the given point is contained by the loop, return it. Otherwise return the closest point on the loop boundary. If the loop is empty, return the input argument. Note that the result may or may not be contained by the loop. "x" should be unit length. |
projectToBoundary
(x)
|
Return the closest point on the loop boundary to the given point. If the loop is empty or full, return the input argument (since the loop has no boundary). "x" should be unit length. |
sign
()
|
The sign of a loop is -1 if the loop represents a hole in its containing polygon, and +1 otherwise. |
spaceUsed
()
|
Returns the total number of bytes used by the loop. |
vertex
(i)
|
For convenience, we make two entire copies of the vertex list available: vertex(n..2*n-1) is mapped to vertex(0..n-1), where n == num_vertices(). |
clone
()
|
Returns a deep copy of the region. |
contains
(p)
|
Returns true if and only if the given point is contained by the region. The point 'p' is generally required to be unit length, although some subtypes may relax this restriction. |
contains
(cell)
|
Returns true if the region completely contains the given cell, otherwise returns false. |
getCapBound
()
|
Returns a bounding spherical cap that contains the region. The bound may not be tight. |
getCellUnionBound
(cellIds)
|
Returns a small collection of S2CellIds 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. |
getRectBound
()
|
Returns a bounding latitude-longitude rectangle that contains the region. The bound may not be tight. |
mayIntersect
(cell)
|
If this method returns false, the region does not intersect the given cell. Otherwise, either region intersects the cell, or the intersection relationship could not be determined. |
Inner classes
| Name | Description |
|---|---|
Shape
|
Wrapper class for indexing a loop (see S2ShapeIndex). Once this object is inserted into an S2ShapeIndex it is owned by that index, and will be automatically deleted when no longer needed by the index. Note that this class does not take ownership of the loop itself (see OwningShape below). You can also subtype this class to store additional data (see S2Shape for details). |
Note
The reason that duplicate vertices and intersecting edges are not allowed is that they make it harder to define and implement loop relationships, e.g. whether one loop contains another. If your data does not satisfy these restrictions, you can use S2Builder to normalize it.
TODO
Convert logic to use a ForwardRange rather than making a copy of its vertices.