Class S2Polygon

java.lang.Object
com.google.common.geometry.S2Polygon
All Implemented Interfaces:
S2Region, Serializable, Comparable<S2Polygon>

@GwtCompatible(serializable=true) public final class S2Polygon extends Object implements S2Region, Comparable<S2Polygon>, Serializable
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:

First, initNested(List) 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.

Second, initOriented(List) 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 S2PolygonBuilder, 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.

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.full()), 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.
See Also:
  • Field Details

    • log

      private static final Logger log
    • LOSSLESS_ENCODING_VERSION

      private static final byte LOSSLESS_ENCODING_VERSION
      Version number of the lossless encoding format for S2Polygon.
      See Also:
    • COMPRESSED_ENCODING_VERSION

      private static final byte COMPRESSED_ENCODING_VERSION
      Version number of the compressed encoding format for S2Polygon.
      See Also:
    • REVERSE_NONE

      private static final com.google.common.base.Predicate<S2Shape> REVERSE_NONE
      Returns false for all shapes.
    • REVERSE_HOLES

      private static final com.google.common.base.Predicate<S2Shape> REVERSE_HOLES
      Returns true for S2Loops for which S2Loop.isHole() is true.
    • loops

      private final List<S2Loop> loops
      The loops of this polygon. There is no total ordering of the loops, but a nested loop always follows its containing loop, and all loops between parent and child are nested somewhere under the parent.
    • bound

      private S2LatLngRect bound
      bound is a conservative bound on all points contained by this polygon: If A.contains(P), then A.bound.contains(new S2LatLng(P)).
    • subregionBound

      private S2LatLngRect subregionBound
      Since "bound" is not exact, it is possible that a polygon A contains another polygon B whose bounds are slightly larger. "subregionBound" has been expanded sufficiently to account for this error, i.e. if A.Contains(B), then A.subregionBound.contains(B.bound).
    • index

      transient S2ShapeIndex index
      The spatial index for this S2Polygon.
    • unindexedContainsCalls

      private AtomicInteger unindexedContainsCalls
      In general we build the index the first time it is needed, but we make an exception for contains(S2Point) because this method has a simple brute force implementation that is relatively cheap. For this one method we keep track of the number of calls made and only build the index once enough calls have been made that we think an index would be worthwhile.
    • hasHoles

      private boolean hasHoles
      True if this polygon has at least one hole.
    • numVertices

      private int numVertices
      Total number of vertices in all loops.
  • Constructor Details

    • S2Polygon

      public S2Polygon()
      Creates an empty polygon. It can be made non-empty by calling init(List).
    • S2Polygon

      public S2Polygon(S2Cell cell)
      Creates an S2Polygon for a given cell.
    • S2Polygon

      public S2Polygon(List<S2Loop> loops)
      Creates an empty polygon and then calls initNested(List) with the given loops. Clears the given list.
    • S2Polygon

      public S2Polygon(S2Loop loop)
      Copy constructor.
    • S2Polygon

      public S2Polygon(S2Polygon src)
      Copy constructor.
  • Method Details

    • copy

      void copy(S2Polygon src)
      Initializes this polygon to a copy of the given polygon.
    • initIndex

      private void initIndex()
    • readResolve

      private Object readResolve()
      Returns the same instance after initializing transient fields.
    • equals

      public boolean equals(Object o)
      Overrides:
      equals in class Object
    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object
    • compareTo

      public int compareTo(S2Polygon other)
      Comparator (needed by Comparable interface). For two polygons to be compared as equal:
      Specified by:
      compareTo in interface Comparable<S2Polygon>
    • init

      public void init(List<S2Loop> loops)
      Initializes a polygon by calling initNested(List).
    • initNested

      public void initNested(List<S2Loop> loops)
      Initializes this 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.)

      This method takes ownership of the given loops and clears the given list. It then figures out the loop nesting hierarchy and assigns every loop a depth. Shells have even depths, and holes have odd depths. Note that the loops are reordered so the hierarchy can be traversed more easily (see getParent(int), getLastDescendant(int), and S2Loop.depth()).

      This method may be called more than once, in which case any existing loops are deleted before being replaced by the input loops.

    • initOriented

      public void initOriented(List<S2Loop> loops)
      Like initNested(List), 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.)
    • initLoopProperties

      private void initLoopProperties()
      Computes hasHoles, numVertices, bound, subregionBound, and the index..
    • initOneLoop

      private void initOneLoop()
      Given that loops contains a single loop, initializes all other fields.
    • initWithNestedLoops

      public void initWithNestedLoops(Map<S2Loop,List<S2Loop>> nestedLoops)
      Initializes a polygon from a set of S2Loops.

      Unlike init(java.util.List<com.google.common.geometry.S2Loop>) this method assumes the caller already knows the nesting of loops within other loops. The passed-in map maps from parents to their immediate child loops, with null mapping to the list of top-most shell loops. Immediate child loops must be completely spatially contained within their parent loop, but not contained in any other loop, except for ancestors of the parent. This method avoids the cost of determining nesting internally, but if the passed in nesting is wrong, future operations on the S2Polygon may be arbitrarily incorrect.

      Note that unlike init(java.util.List<com.google.common.geometry.S2Loop>), the passed-in container of loops is not cleared; however, the passed-in loops become owned by the S2Polygon and should not be modified by the caller after calling this method.

      Parameters:
      nestedLoops - loops with nesting.
    • release

      public void release(List<S2Loop> loops)
      Appends the loops of this polygon to the given list and resets this polygon to be empty.
    • clearLoops

      private void clearLoops()
    • isValid

      public static boolean isValid(List<S2Loop> loops)
      Returns true if the given loops form a valid polygon, including checking whether the loops themselves are valid.
    • isValid

      public boolean isValid()
      Returns true if each loop on this polygon is valid, and if the relationships between all loops are valid.

      Specifically, this verifies that S2Loop.isValid() is true for each S2Loop, and that isValid(List) is true for the whole list of loops.

    • findValidationError

      public boolean findValidationError(S2Error error)
      Returns true if this is *not* a valid polygon and sets error appropriately. Otherwise, returns false and leaves error unchanged.
    • findLoopNestingError

      private boolean findLoopNestingError(S2Error error)
      Returns true if there is an error in the loop nesting hierarchy.
    • isEmpty

      public boolean isEmpty()
    • isFull

      public boolean isFull()
    • numLoops

      public int numLoops()
    • loop

      public S2Loop loop(int k)
      Returns the loop at the given index. Note that during initialization, the given loops are reordered according to a preorder 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 getParent(int), getLastDescendant(int), and S2Loop.depth().
    • getLoops

      public List<S2Loop> getLoops()
      Returns a view of the list of S2Loops that make up this S2Polygon.
    • index

      public S2ShapeIndex index()
      Returns the index of this polygon.
    • getParent

      public int getParent(int k)
      Returns the index of the parent of loop k, or -1 if it has no parent.
    • getLastDescendant

      public int getLastDescendant(int k)
      Returns the index of the last loop that is contained within loop k. Returns numLoops() - 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).
    • getAreaCentroid

      private S2AreaCentroid getAreaCentroid(boolean doCentroid)
    • getAreaAndCentroid

      public S2AreaCentroid getAreaAndCentroid()
      Returns the area of the polygon interior, i.e. the region on the left side of an odd number of loops (the area is between 0 and 4*Pi) and the true centroid of the polygon, weighted by the area of the polygon (see s2.h for details on centroids). Note that the centroid might not be contained by the polygon.
    • getArea

      public double getArea()
      Returns 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.
    • getCentroid

      public S2Point getCentroid()
      Returns the true centroid of the polygon, weighted by the area of the polygon (see s2.h for details on centroids). Note that the centroid might not be contained by the polygon.
    • getSnapLevel

      public int getSnapLevel()
      If all of the polygon's vertices happen to be the centers of S2Cells at some level, then returns that level, otherwise returns -1. See also initToSnapped(S2Polygon, int) and S2PolygonBuilder.Options.Builder.setSnapToCellCenters(boolean). Returns -1 if the polygon has no vertices.
    • getBestSnapLevel

      int getBestSnapLevel()
      Computes the level at which most of the vertices are snapped. If multiple levels have the same maximum number of vertices snapped to it, the first one (lowest level number / largest area / smallest encoding length) will be chosen, so this is desired. Returns -1 for unsnapped polygons.

      See also initToSnapped(S2Polygon, int) and S2PolygonBuilder.Options.Builder.setSnapToCellCenters(boolean).

    • getDistance

      public S1Angle getDistance(S2Point p)
      Returns the shortest distance from a point P to this polygon, given as the angle formed between P, the origin, and the nearest point on the polygon to P. This angle in radians is equivalent to the arclength along the unit sphere.

      If the point is contained inside the polygon, the distance returned is 0.

    • getOverlapFraction

      public static double getOverlapFraction(S2Polygon a, S2Polygon b)
      Returns the overlap fraction of polygon b on polygon a, i.e. the ratio of area of intersection to the area of polygon a.
    • project

      public S2Point project(S2Point p)
      Returns a point on the polygon that is closest to point P. The distance between these two points should be the result of getDistance(S2Point).

      If point P is contained within the loop, it is returned.

      The polygon must not be empty.

    • contains

      public boolean contains(S2Polygon b)
      Returns true if this polygon contains the given other polygon, i.e., if polygon A contains all points contained by polygon B.
    • approxContains

      public boolean approxContains(S2Polygon b, S1Angle vertexMergeRadius)
      Returns true if this polygon (A) approximately contains the given other polygon (B). This is true if it is possible to move the vertices of B no further than "vertexMergeRadius" such that A contains the modified B.

      For example, the empty polygon will contain any polygon whose maximum width is no more than vertexMergeRadius.

    • intersects

      public boolean intersects(S2Polygon b)
      Returns true if this polygon intersects the given other polygon, i.e., if there is a point that is contained by both polygons.
    • clipBoundary

      private static void clipBoundary(S2Polygon a, boolean reverseA, S2Polygon b, boolean invertB, boolean addSharedEdges, S2PolygonBuilder builder)
      Clips the boundary of A to the interior of B, and adds the resulting edges to builder. Shells are directed CCW and holes are directed clockwise. If reverseA is true, these directions are reversed in polygon A. If invertB is true, the boundary of A is clipped to the exterior rather than the interior of B. If addSharedEdges is true, then the output will include any edges that are shared between A and B (both edges must be in the same direction after any edge reversals are taken into account).
    • getNumVertices

      public int getNumVertices()
      Returns the total number of vertices in all loops.
    • initToComplement

      public void initToComplement(S2Polygon a)
      Initializes this polygon to the complement of the given polygon.
    • initToSnapped

      public void initToSnapped(S2Polygon a, int snapLevel)
      Use S2PolygonBuilder to build this polygon by assembling the edges of a given polygon after snapping its vertices to the center of leaf cells. This will simplify the polygon with a tolerance of S2Projections.maxDiag.getValue(S2CellId.MAX_LEVEL), or approximately 0.13 microdegrees, or 1.5cm on the surface of the Earth. Such a polygon can be efficiently compressed when serialized. The snap level can be changed to a non-leaf level if needed.
    • invert

      private void invert()
      Inverts this polygon (replacing it by its complement.)
    • initToIntersection

      public void initToIntersection(S2Polygon a, S2Polygon b)
      Initializes this polygon to the intersection, union, or difference (A - B) of the given two polygons. The vertexMergeRadius determines how close two vertices must be to be merged together and how close a vertex must be to an edge in order to be spliced into it (see S2PolygonBuilder for details). By default, the merge radius is just large enough to compensate for errors that occur when computing intersection points between edges (S2EdgeUtil.DEFAULT_INTERSECTION_TOLERANCE).

      If you are going to convert the resulting polygon to a lower-precision format, it is necessary to increase the merge radius in order to get a valid result after rounding (i.e., no duplicate vertices, etc). For example, if you are going to convert them to geostore.PolygonProto format, then S1Angle.e7(1) is a good value for vertexMergeRadius.

    • initToIntersectionSloppy

      public void initToIntersectionSloppy(S2Polygon a, S2Polygon b, S1Angle vertexMergeRadius)
    • initToUnion

      public void initToUnion(S2Polygon a, S2Polygon b)
    • initToUnionSloppy

      public void initToUnionSloppy(S2Polygon a, S2Polygon b, S1Angle vertexMergeRadius)
    • initToDifference

      public void initToDifference(S2Polygon a, S2Polygon b)
    • initToDifferenceSloppy

      public void initToDifferenceSloppy(S2Polygon a, S2Polygon b, S1Angle vertexMergeRadius)
    • initToSimplified

      public void initToSimplified(S2Polygon a, S1Angle tolerance, boolean snapToCellCenters)
      Initializes this polygon to a polygon that contains fewer vertices and is within tolerance of the polygon a, with some caveats.

      If snapToCellCenters is true, the vertices of this polygon will be snapped to the centers of cells at the smallest level that is guaranteed to result in a valid polygon given the specified tolerance.

      • If there is a very small island in the original polygon, it may disappear completely. Thus some parts of the original polygon may not be close to the simplified polygon. Those parts are small, though, and arguably don't need to be kept.
      • However, if there are dense islands, they may all disappear, instead of replacing them by a big simplified island.
      • For small tolerances (compared to the polygon size), it may happen that the simplified polygon has more vertices than the original, if the first step of the simplification creates too many self-intersections. One can construct unrealistic cases where that happens to an extreme degree.
    • initToSimplifiedInCell

      public void initToSimplifiedInCell(S2Polygon a, S2Cell cell, S1Angle tolerance)
      Initializes this polygon to a polygon that contains fewer vertices and is within tolerance of the polygon a, while ensuring that the vertices on the cell boundary are preserved.

      Precondition: Polygon a is contained in the cell.

    • initToSimplifiedInternal

      private void initToSimplifiedInternal(S2Polygon a, S1Angle tolerance, boolean snapToCellCenters, com.google.common.base.Predicate<S2Point> vertexFilter)
      Simplifies the polygon. The algorithm is straightforward and naive:
      1. Simplify each loop by removing points while staying in the tolerance zone. This uses S2Polyline.subsampleVertices(S1Angle), which is not guaranteed to be optimal in terms of number of points.
      2. Break any edge in pieces such that no piece intersects any other.
      3. Use the polygon builder to regenerate the full polygon.
      4. If vertexFilter is not null, the vertices for which it returns true are kept in the simplified polygon.
    • breakEdgesAndAddToBuilder

      public static void breakEdgesAndAddToBuilder(S2ShapeIndex index, S2PolygonBuilder builder)
      Takes a set of possibly intersecting edges, stored in the S2ShapeIndex, and breaks the edges into small pieces so that there is no intersection anymore, and adds all these edges to the builder.
    • union

      public static S2Polygon union(Iterable<S2Polygon> polygons)
      Returns a polygon that is the union of the given polygons.
    • unionSloppy

      public static S2Polygon unionSloppy(Iterable<S2Polygon> polygons, S1Angle vertexMergeRadius)
      Returns a polygon that is the union of the given polygons; combines vertices that form edges that are almost identical, as defined by vertexMergeRadius.
    • intersectWithPolyline

      public List<S2Polyline> intersectWithPolyline(S2Polyline in)
      Intersects this polygon with the S2Polyline in and returns the resulting zero or more polylines. The polylines are ordered 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.

      This is equivalent to calling intersectWithPolylineSloppy(com.google.common.geometry.S2Polyline, com.google.common.geometry.S1Angle) with the vertexMergeRadius set to S2EdgeUtil.DEFAULT_INTERSECTION_TOLERANCE.

    • intersectWithPolylineSloppy

      public List<S2Polyline> intersectWithPolylineSloppy(S2Polyline in, S1Angle vertexMergeRadius)
      Similar to intersectWithPolyline(com.google.common.geometry.S2Polyline), 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 vertexMergeRadius apart. Note that this can change the number of output polylines and/or yield single-vertex polylines.
    • subtractFromPolyline

      public List<S2Polyline> subtractFromPolyline(S2Polyline in)
      Same as intersectWithPolyline(com.google.common.geometry.S2Polyline), but subtracts this polygon from the given polyline.
    • subtractFromPolylineSloppy

      public List<S2Polyline> subtractFromPolylineSloppy(S2Polyline in, S1Angle vertexMergeRadius)
    • internalClipPolyline

      private List<S2Polyline> internalClipPolyline(boolean invert, S2Polyline a, S1Angle mergeRadius)
      Clips the S2Polyline a to the interior of this polygon. The resulting polyline(s) will be returned. If invert is true, we clip a to the exterior of this polygon instead. Vertices will be dropped such that adjacent vertices will not be closer than mergeRadius.

      We do the intersection/subtraction by walking the polyline edges. For each edge, we compute all intersections with the polygon boundary and sort them in increasing order of distance along that edge. We then divide the intersection points into pairs, and output a clipped polyline segment for each one. We keep track of whether we're inside or outside of the polygon at all times to decide which segments to output.

    • isNormalized

      public boolean 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.

      Generally there is no reason to convert polygons to normalized form. It is mainly useful for testing in order to compare whether two polygons have exactly the same interior, even when they have a different loop structure. For example, a diamond nested within a square (touching at four points) could be represented as a square with a diamond-shaped hole, or as four triangles. Methods such as boundaryApproxEquals(S2Polygon, double) will report these polygons as being different (because they have different boundaries) even though they contain the same points. However if they are both converted to normalized form (the "four triangles" version) then they can be compared more easily.

    • boundaryApproxEquals

      boolean boundaryApproxEquals(S2Polygon b, double maxError)
      Returns 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 maxError. Note: This method mostly useful only for testing purposes.
    • boundaryNear

      boolean boundaryNear(S2Polygon b, double maxError)
      Returns true if two polygons have boundaries that are within maxError of each other along their entire lengths. More precisely, there must be a bijection between the two sets of loops such that aLoop.boundaryNear(bLoop) is true for each aLoop in this and each bLoop in b.
    • getCapBound

      public S2Cap getCapBound()
      Returns a spherical cap that bounds this loop. It may be expanded slightly such that if the loop contains a point P, then the bound contains P also.
      Specified by:
      getCapBound in interface S2Region
    • getRectBound

      public S2LatLngRect getRectBound()
      Returns a fairly tight bounding latitude-longitude rectangle. It is not guaranteed to be as tight as possible, to ensure that if the loop contains a point P, then the bound contains P also.
      Specified by:
      getRectBound in interface S2Region
    • contains

      public boolean contains(S2Cell cell)
      If this method returns true, the region completely contains the given cell. Otherwise, either the region does not contain the cell or the containment relationship could not be determined.
      Specified by:
      contains in interface S2Region
    • mayIntersect

      public boolean mayIntersect(S2Cell target)
      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.
      Specified by:
      mayIntersect in interface S2Region
    • boundaryApproxIntersects

      private boolean boundaryApproxIntersects(S2Iterator<S2ShapeIndex.Cell> it, S2Cell target)
      Returns true if the polygon boundary intersects target. It may also return true when the polygon boundary does not intersect target but some edge comes within the worst-case error tolerance.

      Requires: it.id().contains(target.id()) (This condition is true whenever it.locate(target) returns INDEXED.

    • contains

      public boolean contains(S2Point p)
      The point p does not need to be normalized.
      Specified by:
      contains in interface S2Region
    • contains

      private boolean contains(S2Iterator<S2ShapeIndex.Cell> it, S2Point p)
      Given an iterator that is already positioned at the S2ShapeIndex.Cell containing p, return contains(p).
    • sortValueLoops

      private static void sortValueLoops(Map<S2Loop,List<S2Loop>> loopMap)
      For each map entry, sorts the value list.
    • insertLoop

      private static void insertLoop(S2Loop newLoop, S2Loop parent, Map<S2Loop,List<S2Loop>> loopMap)
    • initLoop

      private void initLoop(S2Loop loop, int depth, Map<S2Loop,List<S2Loop>> loopMap)
    • compareBoundary

      int compareBoundary(S2Loop b)
      Returns +1 if this polygon (A) contains the boundary of B, -1 if A excludes the boundary of B, and 0 if the boundaries of A and B cross.
    • containsBoundary

      private boolean containsBoundary(S2Polygon b)
      Returns true if this polygon (A) contains the entire boundary of B.
    • excludesBoundary

      private boolean excludesBoundary(S2Polygon b)
      Returns true if this polygon (A) excludes the entire boundary of B.
    • containsNonCrossingBoundary

      private boolean containsNonCrossingBoundary(S2Loop b, boolean bReverse)
      Given a polygon A and a loop B whose boundaries do not cross, returns true if A contains the boundary of B. Shared edges are handled according to the rule described in containsNonCrossingBoundary(S2Loop, S2Loop, boolean).
    • containsNonCrossingBoundary

      private boolean containsNonCrossingBoundary(S2Loop a, S2Loop b, boolean bReverse)
      Given two loops whose boundaries do not cross (see compareBoundary(S2Loop), returns true if A contains the boundary of B.

      This method is cheaper than compareBoundary() because it does not test for edge intersections, but it does trigger building the index if there are edges in both polygons.

      Parameters:
      b - the loop to test for containment by this loop; neither loop may be empty or have an edge crossing with the other, and if b is full then bReverse must be false.
      bReverse - If true, the boundary of B is reversed first (which only affects the result when there are shared edges).
    • excludesNonCrossingShells

      private boolean excludesNonCrossingShells(S2Polygon b)
      Given two polygons A and B such that the boundary of A does not cross any loop of B, returns true if A excludes all shell boundaries of B.
    • excludesNonCrossingComplementShells

      private boolean excludesNonCrossingComplementShells(S2Polygon b)
      Given two polygons A and B such that the boundary of A does not cross any loop of B, returns true if A excludes all shell boundaries of the complement of B.
    • anyLoopContains

      private boolean anyLoopContains(S2Loop b)
      Returns true if any loop contains the given loop.
    • anyLoopIntersects

      private boolean anyLoopIntersects(S2Loop b)
      Returns true if any loop intersects the given loop.
    • toString

      public String toString()
      Returns a human readable representation of the polygon.
      Overrides:
      toString in class Object
    • encode

      public void encode(OutputStream output) throws IOException
      Encodes the polygon into an efficient, lossless binary representation, which can be decoded by calling decode(java.io.InputStream). The encoding is byte-compatible with the C++ version of the S2 library.
      Parameters:
      output - The output stream into which the encoding should be written.
      Throws:
      IOException - if there was a problem writing into the output stream.
    • encodeUncompressed

      void encodeUncompressed(LittleEndianOutput encoder) throws IOException
      Encodes the polygon into an uncompressed binary representation, which can be decoded by calling decode(InputStream). The encoding is byte-compatible with the C++ version of the S2 library.
      Parameters:
      encoder - The output stream into which the encoding should be written.
      Throws:
      IOException - if there was a problem writing into the output stream.
    • encodeCompressed

      private void encodeCompressed(int level, LittleEndianOutput encoder) throws IOException
      Throws:
      IOException
    • decode

      public static S2Polygon decode(InputStream input) throws IOException
      Decodes a polygon that was encoded using encode(java.io.OutputStream).

      This method will never return null. It will either throw an exception or return a valid S2Polygon.

      Parameters:
      input - The input stream containing the encoded polygon data.
      Returns:
      the decoded S2Polygon.
      Throws:
      IOException - if there was a problem reading from the input stream.
    • decodeLossless

      private static S2Polygon decodeLossless(LittleEndianInput decoder) throws IOException
      Throws:
      IOException
    • decodeCompressed

      private static S2Polygon decodeCompressed(LittleEndianInput decoder) throws IOException
      Throws:
      IOException
    • shape

      public S2Polygon.Shape shape()
      Returns a shape wrapping this polygon.
    • binarySearchShape

      S2Polygon.Shape binarySearchShape()
      Returns an implementation that does a binary search to map an edge to one of a large number of loops.
    • linearSearchShape

      S2Polygon.Shape linearSearchShape()
      Returns an implementation that does a linear search to map an edge to one of a number of loops.

      When the number of loops is small, linear search is faster. Most often there is exactly one loop and the getEdge and getChainStart loops execute zero times.