Class S2Polyline

  • All Implemented Interfaces:
    S2Region, S2Shape, java.io.Serializable

    @GwtCompatible(serializable=true)
    public final class S2Polyline
    extends java.lang.Object
    implements S2Shape, S2Region, java.io.Serializable
    An S2Polyline represents a sequence of zero or more vertices connected by straight edges (geodesics). Edges of length 0 and 180 degrees are not allowed, i.e. adjacent vertices should not be identical or antipodal.

    Note: Polylines do not have a Contains(S2Point) method, because "containment" is not numerically well-defined except at the polyline vertices.

    See Also:
    Serialized Form
    • Field Detail

      • log

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

        private static final S2Point[] ARR_TEMPLATE
      • LOSSLESS_ENCODING_VERSION

        private static final byte LOSSLESS_ENCODING_VERSION
        See Also:
        Constant Field Values
      • COMPRESSED_ENCODING_VERSION

        private static final byte COMPRESSED_ENCODING_VERSION
        See Also:
        Constant Field Values
      • numVertices

        private final int numVertices
      • vertices

        private final S2Point[] vertices
    • Constructor Detail

      • S2Polyline

        public S2Polyline​(java.util.List<S2Point> vertices)
        Create a polyline that connects the given vertices. Empty polylines are allowed. Adjacent vertices should not be identical or antipodal. All vertices should be unit length.
      • S2Polyline

        private S2Polyline​(S2Point[] vertices)
    • Method Detail

      • vertices

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

        public boolean isValid()
        Return true if the polyline is valid having all vertices be in unit length and having no identical or antipodal adjacent vertices.
      • isValid

        public boolean isValid​(java.util.List<S2Point> vertices)
        Return true if the given vertices form a valid polyline.
      • numVertices

        public int numVertices()
      • vertex

        public S2Point vertex​(int k)
      • getArclengthAngle

        public S1Angle getArclengthAngle()
        Return the angle corresponding to the total arclength of the polyline on a unit sphere.
      • interpolate

        public S2Point interpolate​(double fraction)
        Return the point whose distance from vertex 0 along the polyline is the given fraction of the polyline's total length. Fractions less than zero or greater than one are clamped. The return value is unit length. This cost of this function is currently linear in the number of vertices.
      • uninterpolate

        public double uninterpolate​(S2Point queryPoint)
        Projects the query point to the nearest part of the polyline, and returns the fraction of the polyline's total length traveled along the polyline from vertex 0 to the projected point.

        For any query point, the returned fraction is at least 0 (when the query point projects to the first vertex of the line) and at most 1 (when the query point projects to the last vertex).

        This method is essentially the inverse of interpolate(double), except that this method accepts any normalized point, whereas interpolate() only produces points on the line.

        In the unusual case of multiple equidistant points on the polyline, one of the nearest points is selected in a deterministic but unpredictable manner, and the fraction is computed up to that position. For example, all points of the S2 edge from (1,0,0) to (0,1,0) are equidistant from (0,0,1), so any fraction from 0 to 1 is a correct answer!

      • getCapBound

        public S2Cap getCapBound()
        Return a bounding spherical cap.
        Specified by:
        getCapBound 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
      • contains

        public boolean contains​(S2Point point)
        Description copied from interface: S2Region
        Returns true if and only if the given point is contained by the region. p is generally required to be unit length, although some subtypes may relax this restriction.
        Specified by:
        contains in interface S2Region
      • mayIntersect

        public boolean mayIntersect​(S2Cell cell)
        If this method returns false, the region does not intersect the given cell. Otherwise, either region intersects the cell, or the intersection relationship could not be determined.
        Specified by:
        mayIntersect in interface S2Region
      • fromSnapped

        public static S2Polyline fromSnapped​(S2Polyline a,
                                             int snapLevel)
        Returns a new polyline where the vertices of the given polyline have been snapped to the centers of cells at the specified level.
      • snapPointToLevel

        private static S2Point snapPointToLevel​(S2Point p,
                                                int level)
        Returns a new point, snapped to the center of the cell containing the given point at the specified level.
      • subsampleVertices

        public S2Polyline subsampleVertices​(S1Angle tolerance)
        Return a subsequence of vertex indices such that the polyline connecting these vertices is never further than "tolerance" from the original polyline. Provided the first and last vertices are distinct, they are always preserved; if they are not, the subsequence may contain only a single index.

        Some useful properties of the algorithm:

        • It runs in linear time.
        • The output is always a valid polyline. In particular, adjacent output vertices are never identical or antipodal.
        • The method is not optimal, but it tends to produce 2-3% fewer vertices than the Douglas-Peucker algorithm with the same tolerance.
        • The output is *parametrically* equivalent to the original polyline to within the given tolerance. For example, if a polyline backtracks on itself and then proceeds onwards, the backtracking will be preserved (to within the given tolerance). This is different than the Douglas-Peucker algorithm, which only guarantees geometric equivalence.
      • findEndVertex

        private int findEndVertex​(S1Angle tolerance,
                                  int index)
        Given a polyline, a tolerance distance, and a start index, this function returns the maximal end index such that the line segment between these two vertices passes within "tolerance" of all interior vertices, in order.
      • getNearestEdgeIndex

        public int getNearestEdgeIndex​(S2Point point)
        Given a point, returns the index of the start point of the (first) edge on the polyline that is closest to the given point. The polyline must have at least one vertex. Throws IllegalStateException if this is not the case.
      • projectToEdge

        public S2Point projectToEdge​(S2Point point,
                                     int index)
        Given a point p and the index of the start point of an edge of this polyline, returns the point on that edge that is closest to p.
      • project

        public S2Point project​(S2Point queryPoint)
        Returns the point on the polyline closest to queryPoint.

        In the unusual case of a query point that is equidistant from multiple points on the line, one is returned in a deterministic but otherwise unpredictable way.

      • equals

        public boolean equals​(java.lang.Object that)
        Overrides:
        equals in class java.lang.Object
      • intersects

        public boolean intersects​(S2Polyline line)
        Return true if this polyline intersects the given polyline. If the polylines share a vertex they are considered to be intersecting. When a polyline endpoint is the only intersection with the other polyline, the function may return true or false arbitrarily.

        The running time is quadratic in the number of vertices.

      • hashCode

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

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • 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
      • encode

        public void encode​(java.io.OutputStream os)
                    throws java.io.IOException
        Encodes this polyline into the given output stream.
        Throws:
        java.io.IOException
      • encodeCompact

        public void encodeCompact​(java.io.OutputStream output)
                           throws java.io.IOException
        Encodes the polyline 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 os)
                         throws java.io.IOException
        Encodes this polyline into the given little endian output stream.
        Throws:
        java.io.IOException
      • encodeCompressed

        void encodeCompressed​(int snapLevel,
                              LittleEndianOutput encoder)
                       throws java.io.IOException
        Encodes a compressed polyline at requested snap level.
        Throws:
        java.io.IOException
      • decode

        public static S2Polyline decode​(java.io.InputStream is)
                                 throws java.io.IOException
        Throws:
        java.io.IOException
      • decodeLossless

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

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

        public int getSnapLevel()
        If all of the polyline's vertices happen to be the centers of S2Cells at some level, then returns that level, otherwise returns -1. See also fromSnapped(S2Polyline, int). Returns -1 if the polyline 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 polylines.