Class S2Polyline
- All Implemented Interfaces:
S2Region
,S2Shape
,Serializable
Note: Polylines do not have a Contains(S2Point) method, because "containment" is not numerically well-defined except at the polyline vertices.
- See Also:
-
Nested Class Summary
Nested classes/interfaces inherited from interface com.google.common.geometry.S2Shape
S2Shape.MutableEdge, S2Shape.ReferencePoint
-
Field Summary
Fields -
Constructor Summary
ConstructorsModifierConstructorDescriptionprivate
S2Polyline
(S2Point[] vertices) S2Polyline
(List<S2Point> vertices) Create a polyline that connects the given vertices. -
Method Summary
Modifier and TypeMethodDescriptionboolean
If this method returns true, the region completely contains the given cell.boolean
Returns true if and only if the given point is contained by the region.boolean
Returns true if this shape containsS2.origin()
.(package private) static S2Polyline
decode
(LittleEndianInput decoder) static S2Polyline
decode
(InputStream is) private static S2Polyline
decodeCompressed
(LittleEndianInput decoder) private static S2Polyline
int
Returns the dimension of the geometry represented by this shape.void
encode
(OutputStream os) Encodes this polyline into the given output stream.void
encodeCompact
(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
Encodes this polyline into the given little endian output stream.boolean
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.Return the angle corresponding to the total arclength of the polyline on a unit sphere.(package private) int
Computes the level at which most of the vertices are snapped.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.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.Return a bounding latitude-longitude rectangle.int
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
Returns true if this shape has an interior, i.e.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
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
Returns the number of contiguous edge chains in the shape.int
numEdges()
Returns the number of edges in this shape.int
Returns the point on the polyline closest toqueryPoint
.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.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.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.vertex
(int k) 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 Details
-
log
-
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
-
-
Constructor Details
-
S2Polyline
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
-
-
Method Details
-
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
Return true if the given vertices form a valid polyline. -
numVertices
public int numVertices() -
vertex
-
getArclengthAngle
Return the angle corresponding to the total arclength of the polyline on a unit sphere. -
interpolate
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
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
Return a bounding spherical cap.- Specified by:
getCapBound
in interfaceS2Region
-
getRectBound
Return a bounding latitude-longitude rectangle.- Specified by:
getRectBound
in interfaceS2Region
-
contains
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
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
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
Returns a new polyline where the vertices of the given polyline have been snapped to the centers of cells at the specified level. -
snapPointToLevel
Returns a new point, snapped to the center of the cell containing the given point at the specified level. -
subsampleVertices
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
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
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
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
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
-
intersects
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() -
toString
-
numEdges
public int numEdges()Description copied from interface:S2Shape
Returns the number of edges in this shape. -
getEdge
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
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
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
Encodes this polyline into the given output stream.- Throws:
IOException
-
encodeCompact
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:
IOException
- if there was a problem writing into the output stream.
-
encodeUncompressed
Encodes this polyline into the given little endian output stream.- Throws:
IOException
-
encodeCompressed
Encodes a compressed polyline at requested snap level.- Throws:
IOException
-
decode
- Throws:
IOException
-
decode
- Throws:
IOException
-
decodeLossless
- Throws:
IOException
-
decodeCompressed
- 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 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.
-