Class S2Polygon

  • All Implemented Interfaces:
    S2Region, java.io.Serializable, java.lang.Comparable<S2Polygon>

    @GwtCompatible(serializable=true)
    public final class S2Polygon
    extends java.lang.Object
    implements S2Region, java.lang.Comparable<S2Polygon>, java.io.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:
    Serialized Form
    • Field Detail

      • log

        private static final java.util.logging.Logger log
      • LOSSLESS_ENCODING_VERSION

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

        private static final byte COMPRESSED_ENCODING_VERSION
        Version number of the compressed encoding format for S2Polygon.
        See Also:
        Constant Field Values
      • 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 java.util.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 java.util.concurrent.atomic.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 Detail

      • 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​(java.util.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 Detail

      • copy

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

        private void initIndex()
      • readResolve

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

        public boolean equals​(java.lang.Object o)
        Overrides:
        equals in class java.lang.Object
      • hashCode

        public int hashCode()
        Overrides:
        hashCode in class java.lang.Object
      • init

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

        public void initNested​(java.util.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​(java.util.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​(java.util.Map<S2Loop,​java.util.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​(java.util.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​(java.util.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 java.util.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.
      • 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.

      • 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​(java.lang.Iterable<S2Polygon> polygons)
        Returns a polygon that is the union of the given polygons.
      • unionSloppy

        public static S2Polygon unionSloppy​(java.lang.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.
      • intersectWithPolylineSloppy

        public java.util.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.
      • internalClipPolyline

        private java.util.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​(java.util.Map<S2Loop,​java.util.List<S2Loop>> loopMap)
        For each map entry, sorts the value list.
      • insertLoop

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

        private void initLoop​(S2Loop loop,
                              int depth,
                              java.util.Map<S2Loop,​java.util.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 java.lang.String toString()
        Returns a human readable representation of the polygon.
        Overrides:
        toString in class java.lang.Object
      • encode

        public void encode​(java.io.OutputStream output)
                    throws java.io.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:
        java.io.IOException - if there was a problem writing into the output stream.
      • encodeUncompressed

        void encodeUncompressed​(LittleEndianOutput encoder)
                         throws java.io.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:
        java.io.IOException - if there was a problem writing into the output stream.
      • encodeCompressed

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

        public static S2Polygon decode​(java.io.InputStream input)
                                throws java.io.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:
        java.io.IOException - if there was a problem reading from the input stream.
      • decodeLossless

        private static S2Polygon decodeLossless​(LittleEndianInput decoder)
                                         throws java.io.IOException
        Throws:
        java.io.IOException
      • decodeCompressed

        private static S2Polygon decodeCompressed​(LittleEndianInput decoder)
                                           throws java.io.IOException
        Throws:
        java.io.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.