Class S2Polygon

An S2Polygon is an S2Region object that represents a polygon. A polygon is defined by zero or more loops; recall that the interior of a loop is defined to be its left-hand side (see S2Loop). There are two different conventions for creating an S2Polygon:

class S2Polygon
  : S2Region ;

- InitNested() expects the input loops to be nested hierarchically. The polygon interior then consists of the set of points contained by an odd number of loops. So for example, a circular region with a hole in it would be defined as two CCW loops, with one loop containing the other. The loops can be provided in any order.

When the orientation of the input loops is unknown, the nesting requirement is typically met by calling S2Loop::Normalize() on each loop (which inverts the loop if necessary so that it encloses at most half the sphere). But in fact any set of loops can be used as long as (1) there is no pair of loops that cross, and (2) there is no pair of loops whose union is the entire sphere.

- InitOriented() expects the input loops to be oriented such that the polygon interior is on the left-hand side of every loop. So for example, a circular region with a hole in it would be defined using a CCW outer loop and a CW inner loop. The loop orientations must all be consistent; for example, it is not valid to have one CCW loop nested inside another CCW loop, because the region between the two loops is on the left-hand side of one loop and the right-hand side of the other.

Most clients will not call these methods directly; instead they should use S2Builder, which has better support for dealing with imperfect data.

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 preorder traversal of the nesting hierarchy; InitOriented may also invert some loops. The set of input S2Loop pointers is always preserved; the caller can use this to determine how the loops were reordered if desired.

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 S2Loop), whereas the empty polygon has no loops at all.

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

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

Constructors

NameDescription
this () The default constructor creates an empty polygon. It can be made non-empty by calling Init(), Decode(), etc.
this (loops, s2debugOverride) Convenience constructor that calls InitNested() with the given loops.
this (cell) Convenience constructor that creates a polygon with a single loop corresponding to the given cell.
this (loop, s2debugOverride) Convenience constructor that calls Init(S2Loop*). Note that this method automatically converts the special empty loop (see S2Loop) into an empty polygon, unlike the vector-of-loops constructor which does not allow empty loops at all.

Methods

NameDescription
approxContains (b, tolerance) Returns true if this polgyon (A) approximately contains the given other polygon (B). This is true if it is possible to move the vertices of B no further than "tolerance" such that A contains the modified B.
approxContains (b, tolerance) Returns true if this polgyon approximately contains the given polyline This is true if it is possible to move the polyline vertices no further than "tolerance" such that the polyline is now contained.
approxDisjoint (b, tolerance) Returns true if this polgyon (A) and the given polygon (B) are approximately disjoint. This is true if it is possible to ensure that A and B do not intersect by moving their vertices no further than "tolerance". This implies that in borderline cases where A and B overlap slightly, this method returns true (A and B are approximately disjoint).
approxDisjoint (b, tolerance) Returns true if this polgyon is approximately disjoint from the given polyline. This is true if it is possible to avoid intersection by moving their vertices no further than "tolerance".
approxEquals (b, tolerance) Return true if two polygons are approximately equal to within the given tolerance. This is true if it is possible to move the vertices of the two polygons so that they contain the same set of points.
approxIntersectWithPolyline (a, snap_radius) Similar to IntersectWithPolyline(), except that vertices will be dropped as necessary to ensure that all adjacent vertices in the sequence obtained by concatenating the output polylines will be farther than "snap_radius" apart. Note that this can change the number of output polylines and/or yield single-vertex polylines.
approxSubtractFromPolyline (a, snap_radius) Same as ApproxIntersectWithPolyline, but subtracts this polygon from the given polyline.
boundaryApproxEquals (b, max_error) Return true if two polygons have the same boundary except for vertex perturbations. Both polygons must have loops with the same cyclic vertex order and the same nesting hierarchy, but the vertex locations are allowed to differ by up to "max_error".
boundaryEquals (b) Returns true if two polygons have the same boundary. More precisely, this method requires that both polygons have loops with the same cyclic vertex order and the same nesting hierarchy. (This implies that vertices may be cyclically rotated between corresponding loops, and the loop ordering may be different between the two polygons as long as the nesting hierarchy is the same.)
boundaryNear (b, max_error) Return true if two polygons have boundaries that are within "max_error" of each other along their entire lengths. More precisely, there must be a bijection between the two sets of loops such that for each pair of loops, "a_loop->BoundaryNear(b_loop)" is true.
clone () 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.
contains (b) Return true if this polygon contains the given other polygon, i.e. if polygon A contains all points contained by polygon B.
contains (b) Return true if this polygon contains the given polyline. This method returns an exact result, according to the following model:
contains (p) The point 'p' does not need to be normalized.
decode (decoder) Decodes a polygon encoded with Encode(). Returns true on success.
destructiveUnion (polygons) Return a polygon which is the union of the given polygons.
encode (encoder) Appends a serialized representation of the S2Polygon to "encoder".
findValidationError (error) Returns true if this is *not* a valid polygon and sets "error" appropriately. Otherwise returns false and leaves "error" unchanged.
getArea () Return the area of the polygon interior, i.e. the region on the left side of an odd number of loops. The return value is between 0 and 4*Pi.
getCapBound () Cap surrounding rect bound.
getCentroid () Return the true centroid of the polygon multiplied by the area of the polygon (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 polygon.
getDistance (x) Return the distance from the given point to the polygon interior. If the polygon is empty, return S1Angle::Infinity(). "x" should be unit length.
getDistanceToBoundary (x) Return the distance from the given point to the polygon boundary. If the polygon is empty or full, return S1Angle::Infinity() (since the polygon has no boundary). "x" should be unit length.
getLastDescendant (k) Return the index of the last loop that is contained within loop k. Returns num_loops() - 1 if k < 0. Note that loops are indexed according to a preorder traversal of the nesting hierarchy, so the immediate children of loop k can be found by iterating over loops (k+1)..GetLastDescendant(k) and selecting those whose depth is equal to (loop(k)->depth() + 1).
getOverlapFractions (a, b) Return the overlap fractions between two polygons, i.e. the ratios of the area of intersection to the area of each polygon.
getParent (k) Return the index of the parent of loop k, or -1 if it has no parent.
getSnapLevel () If all of the polygon's vertices happen to be the centers of S2Cells at some level, then return that level, otherwise return -1. See also InitToSnapped() and s2builderutil::S2CellIdSnapFunction. Returns -1 if the polygon has no vertices.
index () Returns the built-in S2ShapeIndex associated with every S2Polygon. This can be used in conjunction with the various S2ShapeIndex query classes (S2ClosestEdgeQuery, S2BooleanOperation, etc) to do things beyond what is possible with S2Polygon built-in convenience methods.
initialize (loop) Initialize a polygon from a single loop. Note that this method automatically converts the special empty loop (see S2Loop) into an empty polygon, unlike the vector-of-loops InitNested() method which does not allow empty loops at all.
initializeNested (loops) Create a polygon from a set of hierarchically nested 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.)
initializeOriented (loops) Like InitNested(), but expects loops to be oriented such that the polygon interior is on the left-hand side of all loops. This implies that shells and holes should have opposite orientations in the input to this method. (During initialization, loops representing holes will automatically be inverted.)
initializeToCellUnionBorder (cells) Initialize this polygon to the outline of the given cell union. In principle this polygon should exactly contain the cell union and this polygon's inverse should not intersect the cell union, but rounding issues may cause this not to be the case.
initializeToComplement (a) Initialize this polygon to the complement of the given polygon.
initializeToIntersection (a, b) Initialize this polygon to the intersection, union, difference (A - B), or symmetric difference (XOR) of the given two polygons.
initializeToSimplified (a, snap_function) Snaps the input polygon according to the given "snap_function" and reduces the number of vertices if possible, while ensuring that no vertex moves further than snap_function.snap_radius().
initializeToSimplifiedInCell (a, cell, snap_radius, boundary_tolerance) Like InitToSimplified, except that any vertices or edges on the boundary of the given S2Cell are preserved if possible. This method requires that the polygon has already been clipped so that it does not extend outside the cell by more than "boundary_tolerance". In other words, it operates on polygons that have already been intersected with a cell.
initializeToSnapped (a, snap_function) Snaps the vertices of the given polygon using the given SnapFunction (e.g., s2builderutil::IntLatLngSnapFunction(6) snaps to E6 coordinates). This can change the polygon topology (merging loops, for example), but the resulting polygon is guaranteed to be valid, and no vertex will move by more than snap_function.snap_radius(). See S2Builder for other guarantees (e.g., minimum edge-vertex separation).
initializeToSnapped (a, snap_level) Convenience function that snaps the vertices to S2CellId centers at the given level (default level 30, which has S2CellId centers spaced about 1 centimeter apart). Polygons can be efficiently encoded by Encode() after they have been snapped.
intersects (b) Return true if this polygon intersects the given other polygon, i.e. if there is a point that is contained by both polygons.
intersects (b) Return true if this polygon intersects the given polyline. This method returns an exact result; see Contains(S2Polyline) for details.
intersectWithPolyline (a) Intersect this polygon with the polyline "in" and return the resulting zero or more polylines. The polylines are returned in the order they would be encountered by traversing "in" from beginning to end. Note that the output may include polylines with only one vertex, but there will not be any zero-vertex polylines.
invert () Invert the polygon (replace it by its complement).
isEmpty () Return true if this is the empty polygon (consisting of no loops).
isFull () Return true if this is the full polygon (consisting of a single loop that encompasses the entire sphere).
isNormalized () Return true if every loop of this polygon shares at most one vertex with its parent loop. Every polygon has a unique normalized form. A polygon can be normalized by passing it through S2Builder (with no snapping) in order to reconstruct the polygon from its edges.
isValid () Returns true if this is a valid polygon (including checking whether all the loops are themselves valid). Note that validity is checked automatically during initialization when --s2debug is enabled (true by default in debug binaries).
numLoops () Return the number of loops in this polygon.
numVertices () Total number of vertices in all loops.
opEquals (o) Return true if two polygons have exactly the same loops. The loops must appear in the same order, and corresponding loops must have the same linear vertex ordering (i.e., cyclic rotations are not allowed).
project (x) If the given point is contained by the polygon, return it. Otherwise return the closest point on the polygon boundary. If the polygon is empty, return the input argument. Note that the result may or may not be contained by the polygon. "x" should be unit length.
projectToBoundary (x) Return the closest point on the polygon boundary to the given point. If the polygon is empty or full, return the input argument (since the polygon has no boundary). "x" should be unit length.
release () Releases ownership of and returns the loops of this polygon, and resets the polygon to be empty.
setS2debugOverride (s2debugOverride) Destroys the polygon and frees its loops.
spaceUsed () Returns the total number of bytes used by the polygon.
subtractFromPolyline (a) Same as IntersectWithPolyline, but subtracts this polygon from the given polyline.
clone () Returns a deep copy of the region.
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

NameDescription
Shape Wrapper class for indexing a polygon (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 polygon itself (see OwningShape below). You can also subtype this class to store additional data (see S2Shape for details).