Class S2Loop

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

    @GwtCompatible(serializable=true)
    public final class S2Loop
    extends java.lang.Object
    implements S2Region, java.lang.Comparable<S2Loop>, java.io.Serializable, S2Shape
    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), and non- adjacent edges are not allowed to intersect. Loops must have at least 3 vertices (except for the "empty" and "full" loops discussed below). 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 ( empty() and full().)

    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.

    See Also:
    Serialized Form
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private S2LatLngRect bound
      A conservative bound on all points contained by this loop: if A.contains(P), then A.bound.contains(new S2LatLng(P)).
      private int depth  
      (package private) static S2Point EMPTY_VERTEX
      The single vertex that defines a loop that contains no area.
      (package private) static S2Point FULL_VERTEX
      The single vertex that defines a loop that contains the whole sphere.
      (package private) S2ShapeIndex index
      Spatial index for this loop.
      (package private) static byte LOSSLESS_ENCODING_VERSION  
      static double MAX_INTERSECTION_ERROR
      Max angle that intersections can be off by and yet still be considered collinear.
      private int numVertices  
      private boolean originInside  
      private S2LatLngRect subregionBound
      Since "bound" is not exact, it is possible that a loop A contains another loop B whose bounds are slightly larger.
      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.
      private S2Point[] vertices  
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
        S2Loop​(S2Cell cell)
      Initialize a loop corresponding to the given cell.
        S2Loop​(S2Loop src)
      Copy constructor.
        S2Loop​(java.util.List<S2Point> vertices)
      Initializes a loop with the given vertices.
      private S2Loop​(java.util.List<S2Point> vertices, boolean originInside, S2LatLngRect bound)  
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) boolean boundaryApproxEquals​(S2Loop loop)  
      (package private) boolean boundaryApproxEquals​(S2Loop b, double maxError)
      Returns true if two loops have the same boundary except for vertex perturbations.
      private boolean boundaryApproxIntersects​(S2Iterator<S2ShapeIndex.Cell> it, S2Cell target)
      Returns true if the loop boundary intersects 'target'.
      (package private) boolean boundaryEquals​(S2Loop b)
      Returns true if two loops have the same boundary.
      (package private) boolean boundaryNear​(S2Loop loop)  
      (package private) boolean boundaryNear​(S2Loop b, double maxError)
      Returns true if the two loop boundaries are within maxError of each other along their entire lengths.
      (package private) boolean bruteForceContains​(S2Point p)  
      int compareBoundary​(S2Loop b)
      Returns +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.
      int compareTo​(S2Loop other)
      Comparator (needed by Comparable interface)
      boolean contains​(S2Cell target)
      If this method returns true, the region completely contains the given cell.
      private boolean contains​(S2Iterator<S2ShapeIndex.Cell> it, S2Point p)
      Given an iterator that is already positioned at the S2ShapeIndexCell containing p, returns contains(p).
      boolean contains​(S2Loop b)
      Return true if the region contained by this loop is a superset of the region contained by the given other loop.
      boolean contains​(S2Point p)
      Returns true if the point is contained by the loop.
      boolean containsNested​(S2Loop b)
      Given two loops of a polygon, return true if A contains B.
      boolean containsOrigin()
      Returns true if this shape contains S2.origin().
      (package private) static S2Loop decode​(LittleEndianInput decoder)
      Returns a loop decoded from the given stream.
      (package private) static S2Loop decodeCompressed​(int level, LittleEndianInput decoder)  
      private static S2Loop decodeInternal​(LittleEndianInput decoder)  
      int depth()  
      int dimension()
      Returns the dimension of the geometry represented by this shape.
      static S2Loop empty()
      Returns a new loop with one vertex that defines an empty loop (i.e., a loop with no edges that contains no points.)
      (package private) void encode​(LittleEndianOutput encoder)
      Encodes this S2Loop using the lossless encoding.
      (package private) void encodeCompressed​(int level, LittleEndianOutput encoder)  
      private void encodeInternal​(LittleEndianOutput encoder)  
      boolean equals​(java.lang.Object obj)  
      boolean findValidationError​(S2Error error)
      Returns true if this is *not* a valid loop and sets error appropriately.
      boolean findValidationErrorNoIndex​(S2Error error)
      Like findValidationError(), but skips any checks that would require building the S2ShapeIndex (i.e., self-intersection tests).
      (package private) int findVertex​(S2Point p)
      Return the index of a vertex at point "p", or -1 if not found.
      static S2Loop full()
      Returns a new loop with one vertex that creates a full loop (i.e., a loop with no edges that contains all points).
      double getArea()
      Returns the area of the loop interior, i.e.
      S2AreaCentroid getAreaAndCentroid()
      Returns a pair of getArea() and getCentroid(), computed more efficiently than computing them separately.
      private int getCanonicalFirstVertex()
      Returns a canonical minimum vertex such that the vertex sequence starting at this vertex does not change when the loop vertex order is rotated or inverted.
      S2Cap getCapBound()
      Returns a spherical cap that bounds this loop.
      S2Point getCentroid()
      Returns the true centroid of the loop multiplied by the area of the loop, or null if this loop is empty, full, or invalid.
      void getChainEdge​(int chainId, int offset, S2Shape.MutableEdge result)
      Returns the edge for the given chain id and offset in result.
      int getChainLength​(int chainId)
      Returns the number of edge ids corresponding to the edge chain for the given chain id.
      int getChainStart​(int chainId)
      Returns the first edge id corresponding to the edge chain for the given chain id.
      S2Point getChainVertex​(int chainId, int edgeOffset)
      Returns the start point of the edge that would be returned by S2Shape.getChainEdge(int, int, com.google.common.geometry.S2Shape.MutableEdge), or the endpoint of the last edge if edgeOffset==getChainLength(chainId).
      S1Angle getDistance​(S2Point p)
      Returns the shortest distance from a point P to this loop, given as the angle formed between P, the origin and the nearest point on the loop to P.
      void getEdge​(int index, S2Shape.MutableEdge result)
      Returns the edge for the given index in result.
      S2LatLngRect getRectBound()
      Returns a fairly tight bounding latitude-longitude rectangle.
      S2LatLngRect getSubregionBound()
      Returns a slightly looser bounding latitude-longitude rectangle than that returned by getRectBound().
      double getTurningAngle()
      Returns the sum of the turning angles at each vertex.
      private static boolean hasCrossingRelation​(S2Loop a, S2Loop b, S2Loop.LoopRelation relation)
      This method checks all edges of loop A for intersection against all edges of loop B.
      int hashCode()  
      boolean hasInterior()
      Returns true if this shape has an interior, i.e.
      private void initBound()
      Initializes the bound.
      private void initIndex()  
      private void initOriginAndBound()  
      boolean intersects​(S2Loop b)
      Return true if the region contained by this loop intersects the region contained by the given other loop.
      void invert()
      Reverse the order of the loop vertices, effectively complementing the region represented by the loop.
      boolean isEmpty()
      Returns true if this is the special "empty" loop that contains no points.
      boolean isEmptyOrFull()
      Returns true if this loop is either "empty" or "full".
      boolean isFull()
      Returns true if this is the special "full" loop that contains all points.
      boolean isHole()
      Return true if this loop represents a hole in its containing polygon.
      boolean isNormalized()
      Return true if the loop is generally a left-turning, aka counter-clockwise loop.
      boolean isOriginInside()
      Return true if the S2:origin() is inside this loop.
      boolean isValid()
      Returns true if this loop is valid.
      static boolean isValid​(java.util.List<S2Point> vertices)
      Static version of isValid(), to be used only when an S2Loop instance is not available, but validity of the points must be checked.
      static S2Loop makeRegularLoop​(S2Point center, S1Angle radius, int numVertices)
      Create a circle of points with a given center, radius, and number of vertices.
      static java.util.List<S2Point> makeRegularVertices​(S2Point center, S1Angle radius, int numVertices)
      As makeRegularLoop(S2Point, S1Angle, int), but returns vertices as a list.
      (package private) boolean matchBoundaries​(S2Loop b, int aOffset, double maxError)
      Helper method called by boundaryNear() to determine if this loop and loop b remain within maxError of each other, starting the comparison with this loop at vertex a_offset and loop b at vertex 0.
      boolean mayIntersect​(S2Cell target)
      If this method returns false, the region does not intersect the given cell.
      static S2Loop newLoopWithTrustedDetails​(java.util.List<S2Point> vertices, boolean originInside, S2LatLngRect bound)
      Fast/unsafe loop initialization.
      void normalize()
      Invert the loop if necessary so that the area enclosed by the loop is at most 2*Pi.
      int numChains()
      Returns the number of contiguous edge chains in the shape.
      int numEdges()
      Returns the number of edges in this shape.
      int numVertices()  
      S2Point orientedVertex​(int i)
      Like vertex(), but this method returns vertices in reverse order if the loop represents a polygon hole.
      java.util.List<S2Point> orientedVertices()
      Returns the vertices oriented such that left is on the inside.
      private java.lang.Object readResolve()
      Returns the same instance after initializing transient fields.
      void setDepth​(int depth)
      The depth of a loop is defined as its nesting level within its containing polygon.
      int sign()
      The sign of a loop is -1 if the loop represents a hole in its containing polygon, and +1 otherwise.
      S2Loop simplify​(S1Angle tolerance, com.google.common.base.Predicate<S2Point> vertexFilter)
      Returns a simplified loop, which may be self-intersecting, or null if the entire loop was within the tolerance.
      java.lang.String toString()  
      S2Point vertex​(int 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 == numVertices().
      java.util.List<S2Point> vertices()
      Returns an unmodifiable view of the vertices of this polyline.
      (package private) static boolean wedgeContainsSemiwedge​(S2Point a0, S2Point ab1, S2Point a2, S2Point b2, boolean bReversed)
      Returns true if the wedge (a0, ab1, a2) contains the edge (ab1, b2), where [a0, ab1, a2] are a subset of the vertices of loop A, and [ab1, ab2, b2] are a subset of the vertices of loop B.
      • Methods inherited from class java.lang.Object

        clone, finalize, getClass, notify, notifyAll, wait, wait, wait
    • Field Detail

      • MAX_INTERSECTION_ERROR

        public static final double MAX_INTERSECTION_ERROR
        Max angle that intersections can be off by and yet still be considered collinear.
        See Also:
        Constant Field Values
      • EMPTY_VERTEX

        static final S2Point EMPTY_VERTEX
        The single vertex that defines a loop that contains no area.
      • FULL_VERTEX

        static final S2Point FULL_VERTEX
        The single vertex that defines a loop that contains the whole sphere.
      • index

        transient S2ShapeIndex index
        Spatial index for this loop.
      • unindexedContainsCalls

        private final 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.
      • vertices

        private final S2Point[] vertices
      • numVertices

        private final int numVertices
      • bound

        private S2LatLngRect bound
        A conservative bound on all points contained by this loop: 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 loop A contains another loop 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).
      • originInside

        private boolean originInside
      • depth

        private int depth
    • Constructor Detail

      • S2Loop

        public S2Loop​(java.util.List<S2Point> vertices)
        Initializes a loop with the 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 empty() and full().
        Parameters:
        vertices - the vertices for this new loop
      • S2Loop

        private S2Loop​(java.util.List<S2Point> vertices,
                       boolean originInside,
                       S2LatLngRect bound)
      • S2Loop

        public S2Loop​(S2Cell cell)
        Initialize a loop corresponding to the given cell.
      • S2Loop

        public S2Loop​(S2Loop src)
        Copy constructor.
    • Method Detail

      • newLoopWithTrustedDetails

        public static S2Loop newLoopWithTrustedDetails​(java.util.List<S2Point> vertices,
                                                       boolean originInside,
                                                       S2LatLngRect bound)
        Fast/unsafe loop initialization.

        This constructor provides known good values for bounds and the originInside value. This is intended to be a "fast loop creation" when we already know a lot about the loop. It is primarily used in combination with the fast S2Polygon initializer ( S2Polygon.initWithNestedLoops(java.util.Map)). 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 empty() and full().)

        Parameters:
        vertices - loop vertices
        originInside - true if the S2::origin() is inside the loop
        bound - the lat/long bounds of the loop
        Returns:
        new loop.
      • makeRegularLoop

        public static S2Loop makeRegularLoop​(S2Point center,
                                             S1Angle radius,
                                             int numVertices)
        Create a circle of points with a given center, radius, and number of vertices.
      • initIndex

        private void initIndex()
      • readResolve

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

        public static final S2Loop empty()
        Returns a new loop with one vertex that defines an empty loop (i.e., a loop with no edges that contains no points.)
      • full

        public static final S2Loop full()
        Returns a new loop with one vertex that creates a full loop (i.e., a loop with no edges that contains all points). See empty() for further details.
      • equals

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

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

        public int depth()
      • setDepth

        public void setDepth​(int 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.
        Parameters:
        depth -
      • isHole

        public boolean isHole()
        Return true if this loop represents a hole in its containing polygon.
      • sign

        public int sign()
        The sign of a loop is -1 if the loop represents a hole in its containing polygon, and +1 otherwise.
      • numVertices

        public int numVertices()
      • vertex

        public S2Point vertex​(int 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 == numVertices().
      • orientedVertex

        public S2Point orientedVertex​(int 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 == numVertices(). This ensures that the interior of the polygon is always to the left of the vertex chain.
      • vertices

        public java.util.List<S2Point> vertices()
        Returns an unmodifiable view of the vertices of this polyline.
      • orientedVertices

        public java.util.List<S2Point> orientedVertices()
        Returns the vertices oriented such that left is on the inside.
      • isEmpty

        public boolean isEmpty()
        Returns true if this is the special "empty" loop that contains no points.
      • isFull

        public boolean isFull()
        Returns true if this is the special "full" loop that contains all points.
      • isEmptyOrFull

        public boolean isEmptyOrFull()
        Returns true if this loop is either "empty" or "full".
      • numEdges

        public int numEdges()
        Description copied from interface: S2Shape
        Returns the number of edges in this shape.
        Specified by:
        numEdges in interface S2Shape
      • getEdge

        public void getEdge​(int index,
                            S2Shape.MutableEdge result)
        Description copied from interface: S2Shape
        Returns the edge for the given index in result. Must not return zero-length edges.
        Specified by:
        getEdge in interface S2Shape
        Parameters:
        index - which edge to set into result, from 0 to S2Shape.numEdges() - 1
      • hasInterior

        public boolean hasInterior()
        Description copied from interface: S2Shape
        Returns true if this shape has an interior, i.e. the shape consists of one or more closed non-intersecting loops.
        Specified by:
        hasInterior in interface S2Shape
      • containsOrigin

        public boolean containsOrigin()
        Description copied from interface: S2Shape
        Returns true if this shape contains S2.origin(). Should return false for shapes that do not have an interior.
        Specified by:
        containsOrigin in interface S2Shape
      • numChains

        public int numChains()
        Description copied from interface: S2Shape
        Returns the number of contiguous edge chains in the shape. For example, a shape whose edges are [AB, BC, CD, AE, EF] may consist of two chains [A, B, C, D] and [A, E, F]. Every chain is assigned a chain id numbered sequentially starting from zero.

        An empty shape has no chains. A full shape (which contains the entire globe) has one chain with no edges. Other shapes should have at least one chain, and the sum of all valid chain lengths should equal S2Shape.numEdges() (that is, edges may only be used by a single chain).

        Note that it is always acceptable to implement this method by returning S2Shape.numEdges() (i.e. every chain consists of a single edge), but this may reduce the efficiency of some algorithms.

        Specified by:
        numChains in interface S2Shape
      • getChainStart

        public int getChainStart​(int chainId)
        Description copied from interface: S2Shape
        Returns the first edge id corresponding to the edge chain for the given chain id. The edge chains must form contiguous, non-overlapping ranges that cover the entire range of edge ids.
        Specified by:
        getChainStart in interface S2Shape
        Parameters:
        chainId - which edge chain to return its start, from 0 to S2Shape.numChains() - 1
      • getChainLength

        public int getChainLength​(int chainId)
        Description copied from interface: S2Shape
        Returns the number of edge ids corresponding to the edge chain for the given chain id. The edge chains must form contiguous, non-overlapping ranges that cover the entire range of edge ids.
        Specified by:
        getChainLength in interface S2Shape
        Parameters:
        chainId - which edge chain to return its length, from 0 to S2Shape.numChains() - 1
      • getChainEdge

        public void getChainEdge​(int chainId,
                                 int offset,
                                 S2Shape.MutableEdge result)
        Description copied from interface: S2Shape
        Returns the edge for the given chain id and offset in result. Must not return zero-length edges.
        Specified by:
        getChainEdge in interface S2Shape
        Parameters:
        chainId - which chain contains the edge to return, from 0 to S2Shape.numChains() - 1
        offset - position from chain start for the edge to return, from 0 to S2Shape.getChainLength(int) - 1
      • dimension

        public int dimension()
        Description copied from interface: S2Shape
        Returns the dimension of the geometry represented by this shape.
        • 0 - Point geometry. Each point is represented as a degenerate edge.
        • 1 - Polyline geometry. Polyline edges may be degenerate. A shape may represent any number of polylines. Polylines edges may intersect.
        • 2 - Polygon geometry. Edges should be oriented such that the polygon interior is always on the left. In theory the edges may be returned in any order, but typically the edges are organized as a collection of edge chains where each chain represents one polygon loop. Polygons may have degeneracies, e.g., degenerate edges or sibling pairs consisting of an edge and its corresponding reversed edge. A polygon loop may also be full (containing all points on the sphere); by convention this is represented as a chain with no edges.

        Note that this method allows degenerate geometry of different dimensions to be distinguished, e.g., it allows a point to be distinguished from a polyline or polygon that has been simplified to a single point.

        Specified by:
        dimension in interface S2Shape
      • compareTo

        public int compareTo​(S2Loop other)
        Comparator (needed by Comparable interface)
        Specified by:
        compareTo in interface java.lang.Comparable<S2Loop>
      • getCanonicalFirstVertex

        private int getCanonicalFirstVertex()
        Returns a canonical minimum vertex such that the vertex sequence starting at this vertex does not change when the loop vertex order is rotated or inverted. This allows the loop vertices to be traversed in a canonical order. If the initial value is less than numVertices(), then stable iteration should be toward larger indices, otherwise smaller indices.
      • isNormalized

        public boolean isNormalized()
        Return true if the loop is generally a left-turning, aka counter-clockwise loop.
      • normalize

        public void normalize()
        Invert the loop if necessary so that the area enclosed by the loop is at most 2*Pi.
      • invert

        public void invert()
        Reverse the order of the loop vertices, effectively complementing the region represented by the loop.
      • getArea

        public double getArea()
        Returns the area of the loop interior, i.e. the region on the left side of the loop regardless of whether it is a shell or a hole. This value is between 0 and 4*Pi, or explicitly 0 if the loop is invalid.
      • getCentroid

        public S2Point getCentroid()
        Returns the true centroid of the loop multiplied by the area of the loop, or null if this loop is empty, full, or invalid.

        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. See S2 for additional centroid details.

        We prescale by the loop area for two reasons:

        1. It is cheaper to compute this way, and
        2. It makes it easier to compute the centroid of more complicated shapes (by splitting them into disjoint regions and summing their centroids).

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

      • getTurningAngle

        public double 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 S2Predicates.sign(S2Point, S2Point, S2Point).

        For example, if a loop has zero area (i.e., it is a very small CCW loop) then the turning angle will always be negative.

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

      • contains

        public boolean contains​(S2Loop b)
        Return true if the region contained by this loop is a superset of the region contained by the given other loop.
      • intersects

        public boolean intersects​(S2Loop b)
        Return true if the region contained by this loop intersects the region contained by the given other loop.
      • wedgeContainsSemiwedge

        static boolean wedgeContainsSemiwedge​(S2Point a0,
                                              S2Point ab1,
                                              S2Point a2,
                                              S2Point b2,
                                              boolean bReversed)
        Returns true if the wedge (a0, ab1, a2) contains the edge (ab1, b2), where [a0, ab1, a2] are a subset of the vertices of loop A, and [ab1, ab2, b2] are a subset of the vertices of loop B.

        Shared edges are handled as follows: If XY is a shared edge, define reversed(XY) to be true if this edge appears in opposite directions in A and B. Then A contains XY if and only if reversed(XY) == bReversed.

      • containsNested

        public boolean containsNested​(S2Loop 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).
      • compareBoundary

        public int compareBoundary​(S2Loop b)
        Returns +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->isHole(). 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.

        This method is used for testing containment and intersection of multi-loop polygons. Note that this method is not symmetric, since the result depends on the direction of loop A but not on the direction of loop B (in the absence of shared edges).

        Parameters:
        b - the loop to compare against this loop; neither loop may be empty, and if b is full, then it must not be a hole.
      • boundaryEquals

        boolean boundaryEquals​(S2Loop 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. The empty and full loops are considered to have different boundaries. (For testing purposes.)
      • boundaryApproxEquals

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

        boolean boundaryApproxEquals​(S2Loop loop)
      • matchBoundaries

        boolean matchBoundaries​(S2Loop b,
                                int aOffset,
                                double maxError)
        Helper method called by boundaryNear() to determine if this loop and loop b remain within maxError of each other, starting the comparison with this loop at vertex a_offset and loop b at vertex 0.
      • boundaryNear

        boolean boundaryNear​(S2Loop b,
                             double maxError)
        Returns true if the two loop boundaries are within maxError 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)) <= maxError 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 maxError of each other.

        (Package private, only used for testing purposes.)

      • boundaryNear

        boolean boundaryNear​(S2Loop loop)
      • 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
      • getSubregionBound

        public S2LatLngRect getSubregionBound()
        Returns a slightly looser bounding latitude-longitude rectangle than that returned by getRectBound(). It is not guaranteed that if this loop contains a loop X, then the subregion bound will contain X.getRectBound().
      • contains

        public boolean contains​(S2Cell target)
        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 loop boundary intersects 'target'. It may also return true when the loop 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.)

      • simplify

        public S2Loop simplify​(S1Angle tolerance,
                               com.google.common.base.Predicate<S2Point> vertexFilter)
        Returns a simplified loop, which may be self-intersecting, or null if the entire loop was within the tolerance.

        If self-intersections could occur and a valid result is needed, instead use S2Polygon.initToSimplified(S2Polygon, S1Angle, boolean).

        Always keeps the first vertex from the loop, and if vertexFilter is not null, also keeps vertices for which vertexFilter.shouldKeepVertex() is true.

      • contains

        public boolean contains​(S2Point p)
        Returns true if the point is contained by the loop. The containment test is exact, placing p arbitrarily within or without the loop depending on orientation of the edges, such that given two loops sharing an edge, and a point on that edge, only one of the loops will contain it. The point does not need to be normalized.
        Specified by:
        contains in interface S2Region
      • bruteForceContains

        boolean bruteForceContains​(S2Point p)
      • contains

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

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

        public boolean isOriginInside()
        Return true if the S2:origin() is inside this loop.

        Primarily used to serialize internal details about a loop for later fast initialization.

      • isValid

        public boolean isValid()
        Returns true if this loop is valid.
      • isValid

        public static boolean isValid​(java.util.List<S2Point> vertices)
        Static version of isValid(), to be used only when an S2Loop instance is not available, but validity of the points must be checked.
        Returns:
        true if the given loop is valid. Creates an instance of S2Loop and defers this call to isValid().
      • findValidationError

        public boolean findValidationError​(S2Error error)
        Returns true if this is *not* a valid loop and sets error appropriately. Otherwise returns false and leaves error unchanged. Requires that error != null.
      • findValidationErrorNoIndex

        public boolean findValidationErrorNoIndex​(S2Error error)
        Like findValidationError(), but skips any checks that would require building the S2ShapeIndex (i.e., self-intersection tests). This will be used by the S2Polygon implementation, which uses its own index to check for loop self-intersection.
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • initOriginAndBound

        private void initOriginAndBound()
      • initBound

        private void initBound()
        Initializes the bound. Requires bound == null.
      • findVertex

        int findVertex​(S2Point p)
        Return the index of a vertex at point "p", or -1 if not found. The return value is in the range 1..num_vertices_ if found.
      • encodeCompressed

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

        static S2Loop decodeCompressed​(int level,
                                       LittleEndianInput decoder)
                                throws java.io.IOException
        Throws:
        java.io.IOException
      • decodeInternal

        private static S2Loop decodeInternal​(LittleEndianInput decoder)
                                      throws java.io.IOException
        Throws:
        java.io.IOException
      • encodeInternal

        private void encodeInternal​(LittleEndianOutput encoder)
                             throws java.io.IOException
        Throws:
        java.io.IOException
      • encode

        void encode​(LittleEndianOutput encoder)
             throws java.io.IOException
        Encodes this S2Loop using the lossless encoding.
        Throws:
        java.io.IOException
      • hasCrossingRelation

        private static boolean hasCrossingRelation​(S2Loop a,
                                                   S2Loop b,
                                                   S2Loop.LoopRelation relation)
        This method checks all edges of loop A for intersection against all edges of loop B. If there is any shared vertex, the wedges centered at this vertex are set to relation.