Class S2Polyline
- java.lang.Object
-
- com.google.common.geometry.S2Polyline
-
@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
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface com.google.common.geometry.S2Shape
S2Shape.MutableEdge, S2Shape.ReferencePoint
-
-
Field Summary
Fields Modifier and Type Field Description private static S2Point[]
ARR_TEMPLATE
private static byte
COMPRESSED_ENCODING_VERSION
private static java.util.logging.Logger
log
private static byte
LOSSLESS_ENCODING_VERSION
private int
numVertices
private S2Point[]
vertices
-
Constructor Summary
Constructors Modifier Constructor Description private
S2Polyline(S2Point[] vertices)
S2Polyline(java.util.List<S2Point> vertices)
Create a polyline that connects the given vertices.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
contains(S2Cell cell)
If this method returns true, the region completely contains the given cell.boolean
contains(S2Point point)
Returns true if and only if the given point is contained by the region.boolean
containsOrigin()
Returns true if this shape containsS2.origin()
.(package private) static S2Polyline
decode(LittleEndianInput decoder)
static S2Polyline
decode(java.io.InputStream is)
private static S2Polyline
decodeCompressed(LittleEndianInput decoder)
private static S2Polyline
decodeLossless(LittleEndianInput is)
int
dimension()
Returns the dimension of the geometry represented by this shape.void
encode(java.io.OutputStream os)
Encodes this polyline into the given output stream.void
encodeCompact(java.io.OutputStream output)
Encodes the polyline into an efficient, lossless binary representation, which can be decoded by callingdecode(java.io.InputStream)
.(package private) void
encodeCompressed(int snapLevel, LittleEndianOutput encoder)
Encodes a compressed polyline at requested snap level.(package private) void
encodeUncompressed(LittleEndianOutput os)
Encodes this polyline into the given little endian output stream.boolean
equals(java.lang.Object that)
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.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.S1Angle
getArclengthAngle()
Return the angle corresponding to the total arclength of the polyline on a unit sphere.(package private) int
getBestSnapLevel()
Computes the level at which most of the vertices are snapped.S2Cap
getCapBound()
Return a bounding spherical cap.void
getChainEdge(int chainId, int offset, S2Shape.MutableEdge result)
Returns the edge for the given chain id and offset inresult
.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 byS2Shape.getChainEdge(int, int, com.google.common.geometry.S2Shape.MutableEdge)
, or the endpoint of the last edge ifedgeOffset==getChainLength(chainId)
.void
getEdge(int index, S2Shape.MutableEdge result)
Returns the edge for the given index inresult
.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.S2LatLngRect
getRectBound()
Return a bounding latitude-longitude rectangle.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.int
hashCode()
boolean
hasInterior()
Returns true if this shape has an interior, i.e.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.boolean
intersects(S2Polyline line)
Return true if this polyline intersects the given polyline.boolean
isValid()
Return true if the polyline is valid having all vertices be in unit length and having no identical or antipodal adjacent vertices.boolean
isValid(java.util.List<S2Point> vertices)
Return true if the given vertices form a valid polyline.boolean
mayIntersect(S2Cell cell)
If this method returns false, the region does not intersect the given cell.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
project(S2Point queryPoint)
Returns the point on the polyline closest toqueryPoint
.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.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.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.java.lang.String
toString()
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.S2Point
vertex(int k)
java.util.List<S2Point>
vertices()
Returns an unmodifiable view of the vertices of this polyline.-
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
-
Methods inherited from interface com.google.common.geometry.S2Shape
chain, chains, getReferencePoint
-
-
-
-
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 interfaceS2Region
-
getRectBound
public S2LatLngRect getRectBound()
Return a bounding latitude-longitude rectangle.- Specified by:
getRectBound
in interfaceS2Region
-
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.
-
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.
-
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 interfaceS2Region
-
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 toqueryPoint
.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 classjava.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 classjava.lang.Object
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
numEdges
public int numEdges()
Description copied from interface:S2Shape
Returns the number of edges in this shape.
-
getEdge
public void getEdge(int index, S2Shape.MutableEdge result)
Description copied from interface:S2Shape
Returns the edge for the given index inresult
. Must not return zero-length edges.- Specified by:
getEdge
in interfaceS2Shape
- Parameters:
index
- which edge to set intoresult
, from 0 toS2Shape.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 interfaceS2Shape
-
containsOrigin
public boolean containsOrigin()
Description copied from interface:S2Shape
Returns true if this shape containsS2.origin()
. Should return false for shapes that do not have an interior.- Specified by:
containsOrigin
in interfaceS2Shape
-
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 equalS2Shape.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.
-
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 interfaceS2Shape
- Parameters:
chainId
- which edge chain to return its start, from 0 toS2Shape.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 interfaceS2Shape
- Parameters:
chainId
- which edge chain to return its length, from 0 toS2Shape.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 inresult
. Must not return zero-length edges.- Specified by:
getChainEdge
in interfaceS2Shape
- Parameters:
chainId
- which chain contains the edge to return, from 0 toS2Shape.numChains()
- 1offset
- position from chain start for the edge to return, from 0 toS2Shape.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 byS2Shape.getChainEdge(int, int, com.google.common.geometry.S2Shape.MutableEdge)
, or the endpoint of the last edge ifedgeOffset==getChainLength(chainId)
.- Specified by:
getChainVertex
in interfaceS2Shape
-
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.
-
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 callingdecode(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
-
decode
static S2Polyline decode(LittleEndianInput decoder) 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 alsofromSnapped(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.
-
-