Class S2Polyline

java.lang.Object
com.google.common.geometry.S2Polyline
All Implemented Interfaces:
S2Region, S2Shape, Serializable

@GwtCompatible(serializable=true) public final class S2Polyline extends Object implements S2Shape, S2Region, 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:
  • Field Details

    • log

      private static final Logger log
    • ARR_TEMPLATE

      private static final S2Point[] ARR_TEMPLATE
    • LOSSLESS_ENCODING_VERSION

      private static final byte LOSSLESS_ENCODING_VERSION
      See Also:
    • COMPRESSED_ENCODING_VERSION

      private static final byte COMPRESSED_ENCODING_VERSION
      See Also:
    • numVertices

      private final int numVertices
    • vertices

      private final S2Point[] vertices
  • Constructor Details

    • S2Polyline

      public S2Polyline(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 Details

    • vertices

      public 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(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
    • getRectBound

      public S2LatLngRect getRectBound()
      Return a bounding latitude-longitude rectangle.
      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
    • 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(Object that)
      Overrides:
      equals in class 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 Object
    • toString

      public String toString()
      Overrides:
      toString in class 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
    • getChainVertex

      public S2Point getChainVertex(int chainId, int edgeOffset)
      Description copied from interface: S2Shape
      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).
      Specified by:
      getChainVertex in interface S2Shape
    • 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(OutputStream os) throws IOException
      Encodes this polyline into the given output stream.
      Throws:
      IOException
    • encodeCompact

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

      void encodeUncompressed(LittleEndianOutput os) throws IOException
      Encodes this polyline into the given little endian output stream.
      Throws:
      IOException
    • encodeCompressed

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

      public static S2Polyline decode(InputStream is) throws IOException
      Throws:
      IOException
    • decode

      static S2Polyline decode(LittleEndianInput decoder) throws IOException
      Throws:
      IOException
    • decodeLossless

      private static S2Polyline decodeLossless(LittleEndianInput is) throws IOException
      Throws:
      IOException
    • decodeCompressed

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