Class S2Polygon
- All Implemented Interfaces:
S2Region
,Serializable
,Comparable<S2Polygon>
S2Loop
.)
There are two different conventions for creating an S2Polygon:
First, initNested(List)
expects the input loops to be nested hierarchically. The
polygon interior then consists of the set of points contained by an odd number of loops. So for
example, a circular region with a hole in it would be defined as two CCW loops, with one loop
containing the other. The loops can be provided in any order.
When the orientation of the input loops is unknown, the nesting requirement is typically met
by calling S2Loop.normalize()
on each loop (which inverts the loop if necessary so that
it encloses at most half the sphere). But in fact any set of loops can be used as long as (1)
there is no pair of loops that cross, and (2) there is no pair of loops whose union is the entire
sphere.
Second, initOriented(List)
expects the input loops to be oriented such that the
polygon interior is on the left-hand side of every loop. So for example, a circular region with a
hole in it would be defined using a CCW outer loop and a CW inner loop. The loop orientations
must all be consistent; for example, it is not valid to have one CCW loop nested inside another
CCW loop, because the region between the two loops is on the left-hand side of one loop and the
right-hand side of the other.
Most clients will not call these methods directly; instead they should use S2PolygonBuilder
, which has better support for dealing with imperfect data.
When the polygon is initialized, the given loops are automatically converted into a canonical form consisting of "shells" and "holes". Shells and holes are both oriented CCW, and are nested hierarchically. The loops are reordered to correspond to a preorder traversal of the nesting hierarchy; initOriented may also invert some loops.
Polygons may represent any region of the sphere with a polygonal boundary, including the
entire sphere (known as the "full" polygon). The full polygon consists of a single full loop (see
S2Loop.full()
), whereas the empty polygon has no loops at all.
Polygons have the following restrictions:
- Loops may not cross, i.e. the boundary of a loop may not intersect both the interior and exterior of any other loop.
- Loops may not share edges, i.e. if a loop contains an edge AB, then no other loop may contain AB or BA.
- Loops may share vertices, however no vertex may appear twice in a single loop (see S2Loop).
- No loop may be empty. The full loop may appear only in the full polygon.
- See Also:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static class
EdgeClipper finds all the intersections of a given edge with the edges contained in an S2ShapeIndex.private static final class
private static class
Indexing structure to efficientlyS2EdgeIndex.clipEdge(com.google.common.geometry.S2Point, com.google.common.geometry.S2Point, boolean, java.util.Collection<com.google.common.geometry.ParametrizedS2Point>)
of a polygon.static final class
Indexing structure for anS2Polygon
.class
Wrapper class for indexing a polygon viaS2ShapeIndex
. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate S2LatLngRect
bound
is a conservative bound on all points contained by this polygon: If A.contains(P), then A.bound.contains(new S2LatLng(P)).private static final byte
Version number of the compressed encoding format for S2Polygon.private boolean
True if this polygon has at least one hole.(package private) S2ShapeIndex
The spatial index for this S2Polygon.private static final Logger
The loops of this polygon.private static final byte
Version number of the lossless encoding format for S2Polygon.private int
Total number of vertices in all loops.private static final com.google.common.base.Predicate
<S2Shape> Returns true for S2Loops for whichS2Loop.isHole()
is true.private static final com.google.common.base.Predicate
<S2Shape> Returns false for all shapes.private S2LatLngRect
Since "bound" is not exact, it is possible that a polygon A contains another polygon B whose bounds are slightly larger.private AtomicInteger
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. -
Constructor Summary
ConstructorsConstructorDescriptionCreates an empty polygon.Creates an S2Polygon for a given cell.Copy constructor.Copy constructor.Creates an empty polygon and then callsinitNested(List)
with the given loops. -
Method Summary
Modifier and TypeMethodDescriptionprivate boolean
Returns true if any loop contains the given loop.private boolean
Returns true if any loop intersects the given loop.boolean
approxContains
(S2Polygon b, S1Angle vertexMergeRadius) Returns true if this polygon (A) approximately contains the given other polygon (B).(package private) S2Polygon.Shape
Returns an implementation that does a binary search to map an edge to one of a large number of loops.(package private) boolean
boundaryApproxEquals
(S2Polygon b, double maxError) Returns true if two polygons have the same boundary, except for vertex perturbations.private boolean
boundaryApproxIntersects
(S2Iterator<S2ShapeIndex.Cell> it, S2Cell target) Returns true if the polygon boundary intersectstarget
.(package private) boolean
boundaryNear
(S2Polygon b, double maxError) Returns true if two polygons have boundaries that are withinmaxError
of each other along their entire lengths.static void
breakEdgesAndAddToBuilder
(S2ShapeIndex index, S2PolygonBuilder builder) Takes a set of possibly intersecting edges, stored in the S2ShapeIndex, and breaks the edges into small pieces so that there is no intersection anymore, and adds all these edges to the builder.private void
private static void
clipBoundary
(S2Polygon a, boolean reverseA, S2Polygon b, boolean invertB, boolean addSharedEdges, S2PolygonBuilder builder) Clips the boundary of A to the interior of B, and adds the resulting edges tobuilder
.(package private) int
Returns +1 if this polygon (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
Comparator (needed by Comparable interface).boolean
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 S2ShapeIndex.Cell containingp
, returncontains(p)
.boolean
The pointp
does not need to be normalized.boolean
Returns true if this polygon contains the given other polygon, i.e., if polygon A contains all points contained by polygon B.private boolean
Returns true if this polygon (A) contains the entire boundary of B.private boolean
containsNonCrossingBoundary
(S2Loop b, boolean bReverse) Given a polygon A and a loop B whose boundaries do not cross, returns true if A contains the boundary of B.private boolean
containsNonCrossingBoundary
(S2Loop a, S2Loop b, boolean bReverse) Given two loops whose boundaries do not cross (seecompareBoundary(S2Loop)
, returns true if A contains the boundary of B.(package private) void
Initializes this polygon to a copy of the given polygon.static S2Polygon
decode
(InputStream input) Decodes a polygon that was encoded usingencode(java.io.OutputStream)
.private static S2Polygon
decodeCompressed
(LittleEndianInput decoder) private static S2Polygon
decodeLossless
(LittleEndianInput decoder) void
encode
(OutputStream output) Encodes the polygon into an efficient, lossless binary representation, which can be decoded by callingdecode(java.io.InputStream)
.private void
encodeCompressed
(int level, LittleEndianOutput encoder) (package private) void
encodeUncompressed
(LittleEndianOutput encoder) Encodes the polygon into an uncompressed binary representation, which can be decoded by callingdecode(InputStream)
.boolean
private boolean
Returns true if this polygon (A) excludes the entire boundary of B.private boolean
Given two polygons A and B such that the boundary of A does not cross any loop of B, returns true if A excludes all shell boundaries of the complement of B.private boolean
Given two polygons A and B such that the boundary of A does not cross any loop of B, returns true if A excludes all shell boundaries of B.private boolean
findLoopNestingError
(S2Error error) Returns true if there is an error in the loop nesting hierarchy.boolean
findValidationError
(S2Error error) Returns true if this is *not* a valid polygon and setserror
appropriately.double
getArea()
Returns the area of the polygon interior, i.e.Returns the area of the polygon interior, i.e.private S2AreaCentroid
getAreaCentroid
(boolean doCentroid) (package private) int
Computes the level at which most of the vertices are snapped.Returns a spherical cap that bounds this loop.Returns the true centroid of the polygon, weighted by the area of the polygon (see s2.h for details on centroids).Returns the shortest distance from a point P to this polygon, given as the angle formed between P, the origin, and the nearest point on the polygon to P.int
getLastDescendant
(int k) Returns the index of the last loop that is contained within loopk
.getLoops()
Returns a view of the list ofS2Loop
s that make up this S2Polygon.int
Returns the total number of vertices in all loops.static double
Returns the overlap fraction of polygon b on polygon a, i.e.int
getParent
(int k) Returns the index of the parent of loopk
, or -1 if it has no parent.Returns a fairly tight bounding latitude-longitude rectangle.int
If all of the polygon's vertices happen to be the centers of S2Cells at some level, then returns that level, otherwise returns -1.int
hashCode()
index()
Returns the index of this polygon.void
Initializes a polygon by callinginitNested(List)
.private void
private void
private void
Computes hasHoles, numVertices, bound, subregionBound, and the index..void
initNested
(List<S2Loop> loops) Initializes this polygon from a set of hierarchically nested loops.private void
Given that loops contains a single loop, initializes all other fields.void
initOriented
(List<S2Loop> loops) LikeinitNested(List)
, but expects loops to be oriented such that the polygon interior is on the left-hand side of all loops.void
Initializes this polygon to the complement of the given polygon.void
void
initToDifferenceSloppy
(S2Polygon a, S2Polygon b, S1Angle vertexMergeRadius) void
Initializes this polygon to the intersection, union, or difference (A - B) of the given two polygons.void
initToIntersectionSloppy
(S2Polygon a, S2Polygon b, S1Angle vertexMergeRadius) void
initToSimplified
(S2Polygon a, S1Angle tolerance, boolean snapToCellCenters) Initializes this polygon to a polygon that contains fewer vertices and is within tolerance of the polygon a, with some caveats.void
initToSimplifiedInCell
(S2Polygon a, S2Cell cell, S1Angle tolerance) Initializes this polygon to a polygon that contains fewer vertices and is within tolerance of the polygon a, while ensuring that the vertices on the cell boundary are preserved.private void
initToSimplifiedInternal
(S2Polygon a, S1Angle tolerance, boolean snapToCellCenters, com.google.common.base.Predicate<S2Point> vertexFilter) Simplifies the polygon.void
initToSnapped
(S2Polygon a, int snapLevel) Use S2PolygonBuilder to build this polygon by assembling the edges of a given polygon after snapping its vertices to the center of leaf cells.void
initToUnion
(S2Polygon a, S2Polygon b) void
initToUnionSloppy
(S2Polygon a, S2Polygon b, S1Angle vertexMergeRadius) void
initWithNestedLoops
(Map<S2Loop, List<S2Loop>> nestedLoops) Initializes a polygon from a set ofS2Loop
s.private static void
private List
<S2Polyline> internalClipPolyline
(boolean invert, S2Polyline a, S1Angle mergeRadius) Clips theS2Polyline
a
to the interior of this polygon.boolean
Returns true if this polygon intersects the given other polygon, i.e., if there is a point that is contained by both polygons.Intersects this polygon with theS2Polyline
in
and returns the resulting zero or more polylines.intersectWithPolylineSloppy
(S2Polyline in, S1Angle vertexMergeRadius) Similar tointersectWithPolyline(com.google.common.geometry.S2Polyline)
, except that vertices will be dropped as necessary to ensure that all adjacent vertices in the sequence obtained by concatenating the output polylines will be farther thanvertexMergeRadius
apart.private void
invert()
Inverts this polygon (replacing it by its complement.)boolean
isEmpty()
boolean
isFull()
boolean
Return true if every loop of this polygon shares at most one vertex with its parent loop.boolean
isValid()
Returns true if each loop on this polygon is valid, and if the relationships between all loops are valid.static boolean
Returns true if the given loops form a valid polygon, including checking whether the loops themselves are valid.(package private) S2Polygon.Shape
Returns an implementation that does a linear search to map an edge to one of a number of loops.loop
(int k) Returns the loop at the given index.boolean
mayIntersect
(S2Cell target) If this method returns false, the region does not intersect the given cell.int
numLoops()
Returns a point on the polygon that is closest to point P.private Object
Returns the same instance after initializing transient fields.void
Appends the loops of this polygon to the given list and resets this polygon to be empty.shape()
Returns a shape wrapping this polygon.private static void
sortValueLoops
(Map<S2Loop, List<S2Loop>> loopMap) For each map entry, sorts the value list.Same asintersectWithPolyline(com.google.common.geometry.S2Polyline)
, but subtracts this polygon from the given polyline.subtractFromPolylineSloppy
(S2Polyline in, S1Angle vertexMergeRadius) Same asintersectWithPolylineSloppy(com.google.common.geometry.S2Polyline, com.google.common.geometry.S1Angle)
, but subtracts this polygon from the given polyline.toString()
Returns a human readable representation of the polygon.static S2Polygon
Returns a polygon that is the union of the given polygons.static S2Polygon
unionSloppy
(Iterable<S2Polygon> polygons, S1Angle vertexMergeRadius) Returns a polygon that is the union of the given polygons; combines vertices that form edges that are almost identical, as defined byvertexMergeRadius
.
-
Field Details
-
log
-
LOSSLESS_ENCODING_VERSION
private static final byte LOSSLESS_ENCODING_VERSIONVersion number of the lossless encoding format for S2Polygon.- See Also:
-
COMPRESSED_ENCODING_VERSION
private static final byte COMPRESSED_ENCODING_VERSIONVersion number of the compressed encoding format for S2Polygon.- See Also:
-
REVERSE_NONE
Returns false for all shapes. -
REVERSE_HOLES
Returns true for S2Loops for whichS2Loop.isHole()
is true. -
loops
The loops of this polygon. There is no total ordering of the loops, but a nested loop always follows its containing loop, and all loops between parent and child are nested somewhere under the parent. -
bound
bound
is a conservative bound on all points contained by this polygon: If A.contains(P), then A.bound.contains(new S2LatLng(P)). -
subregionBound
Since "bound" is not exact, it is possible that a polygon A contains another polygon 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). -
index
The spatial index for this S2Polygon. -
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. -
hasHoles
private boolean hasHolesTrue if this polygon has at least one hole. -
numVertices
private int numVerticesTotal number of vertices in all loops.
-
-
Constructor Details
-
S2Polygon
public S2Polygon()Creates an empty polygon. It can be made non-empty by callinginit(List)
. -
S2Polygon
Creates an S2Polygon for a given cell. -
S2Polygon
Creates an empty polygon and then callsinitNested(List)
with the given loops. Clears the given list. -
S2Polygon
Copy constructor. -
S2Polygon
Copy constructor.
-
-
Method Details
-
copy
Initializes this polygon to a copy of the given polygon. -
initIndex
private void initIndex() -
readResolve
Returns the same instance after initializing transient fields. -
equals
-
hashCode
public int hashCode() -
compareTo
Comparator (needed by Comparable interface). For two polygons to be compared as equal:- They must have the same number of loops
- The loops must be ordered in the same way (this is guaranteed by the total ordering
imposed by
sortValueLoops(java.util.Map<com.google.common.geometry.S2Loop, java.util.List<com.google.common.geometry.S2Loop>>)
) - Loops must be logically equivalent (even if ordered with a different starting point, e.g. ABCD and BCDA).
- Specified by:
compareTo
in interfaceComparable<S2Polygon>
-
init
Initializes a polygon by callinginitNested(List)
. -
initNested
Initializes this polygon from a set of hierarchically nested loops. The polygon interior consists of the points contained by an odd number of loops. (Recall that a loop contains the set of points on its left-hand side.)This method takes ownership of the given loops and clears the given list. It then figures out the loop nesting hierarchy and assigns every loop a depth. Shells have even depths, and holes have odd depths. Note that the loops are reordered so the hierarchy can be traversed more easily (see
getParent(int)
,getLastDescendant(int)
, andS2Loop.depth()
).This method may be called more than once, in which case any existing loops are deleted before being replaced by the input loops.
-
initOriented
LikeinitNested(List)
, but expects loops to be oriented such that the polygon interior is on the left-hand side of all loops. This implies that shells and holes should have opposite orientations in the input to this method. (During initialization, loops representing holes will automatically be inverted.) -
initLoopProperties
private void initLoopProperties()Computes hasHoles, numVertices, bound, subregionBound, and the index.. -
initOneLoop
private void initOneLoop()Given that loops contains a single loop, initializes all other fields. -
initWithNestedLoops
Initializes a polygon from a set ofS2Loop
s.Unlike
init(java.util.List<com.google.common.geometry.S2Loop>)
this method assumes the caller already knows the nesting of loops within other loops. The passed-in map maps from parents to their immediate child loops, withnull
mapping to the list of top-most shell loops. Immediate child loops must be completely spatially contained within their parent loop, but not contained in any other loop, except for ancestors of the parent. This method avoids the cost of determining nesting internally, but if the passed in nesting is wrong, future operations on the S2Polygon may be arbitrarily incorrect.Note that unlike
init(java.util.List<com.google.common.geometry.S2Loop>)
, the passed-in container of loops is not cleared; however, the passed-in loops become owned by the S2Polygon and should not be modified by the caller after calling this method.- Parameters:
nestedLoops
- loops with nesting.
-
release
Appends the loops of this polygon to the given list and resets this polygon to be empty. -
clearLoops
private void clearLoops() -
isValid
Returns true if the given loops form a valid polygon, including checking whether the loops themselves are valid. -
isValid
public boolean isValid()Returns true if each loop on this polygon is valid, and if the relationships between all loops are valid.Specifically, this verifies that
S2Loop.isValid()
is true for eachS2Loop
, and thatisValid(List)
is true for the whole list of loops. -
findValidationError
Returns true if this is *not* a valid polygon and setserror
appropriately. Otherwise, returns false and leaveserror
unchanged. -
findLoopNestingError
Returns true if there is an error in the loop nesting hierarchy. -
isEmpty
public boolean isEmpty() -
isFull
public boolean isFull() -
numLoops
public int numLoops() -
loop
Returns the loop at the given index. Note that during initialization, the given loops are reordered according to a preorder traversal of the loop nesting hierarchy. This implies that every loop is immediately followed by its descendants. This hierarchy can be traversed using the methodsgetParent(int)
,getLastDescendant(int)
, andS2Loop.depth()
. -
getLoops
Returns a view of the list ofS2Loop
s that make up this S2Polygon. -
index
Returns the index of this polygon. -
getParent
public int getParent(int k) Returns the index of the parent of loopk
, or -1 if it has no parent. -
getLastDescendant
public int getLastDescendant(int k) Returns the index of the last loop that is contained within loopk
. ReturnsnumLoops() - 1
ifk < 0
. Note that loops are indexed according to a preorder traversal of the nesting hierarchy, so the immediate children of loopk
can be found by iterating over loops(k+1)..getLastDescendant(k)
and selecting those whose depth is equal to(loop(k).depth() + 1)
. -
getAreaCentroid
-
getAreaAndCentroid
Returns the area of the polygon interior, i.e. the region on the left side of an odd number of loops (the area is between 0 and 4*Pi) and the true centroid of the polygon, weighted by the area of the polygon (see s2.h for details on centroids). Note that the centroid might not be contained by the polygon. -
getArea
public double getArea()Returns the area of the polygon interior, i.e. the region on the left side of an odd number of loops. The return value is between 0 and 4*Pi. -
getCentroid
Returns the true centroid of the polygon, weighted by the area of the polygon (see s2.h for details on centroids). Note that the centroid might not be contained by the polygon. -
getSnapLevel
public int getSnapLevel()If all of the polygon's vertices happen to be the centers of S2Cells at some level, then returns that level, otherwise returns -1. See alsoinitToSnapped(S2Polygon, int)
andS2PolygonBuilder.Options.Builder.setSnapToCellCenters(boolean)
. Returns -1 if the polygon 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 polygons.See also
initToSnapped(S2Polygon, int)
andS2PolygonBuilder.Options.Builder.setSnapToCellCenters(boolean)
. -
getDistance
Returns the shortest distance from a point P to this polygon, given as the angle formed between P, the origin, and the nearest point on the polygon to P. This angle in radians is equivalent to the arclength along the unit sphere.If the point is contained inside the polygon, the distance returned is 0.
-
getOverlapFraction
Returns the overlap fraction of polygon b on polygon a, i.e. the ratio of area of intersection to the area of polygon a. -
project
Returns a point on the polygon that is closest to point P. The distance between these two points should be the result ofgetDistance(S2Point)
.If point P is contained within the loop, it is returned.
The polygon must not be empty.
-
contains
Returns true if this polygon contains the given other polygon, i.e., if polygon A contains all points contained by polygon B. -
approxContains
Returns true if this polygon (A) approximately contains the given other polygon (B). This is true if it is possible to move the vertices of B no further than "vertexMergeRadius" such that A contains the modified B.For example, the empty polygon will contain any polygon whose maximum width is no more than vertexMergeRadius.
-
intersects
Returns true if this polygon intersects the given other polygon, i.e., if there is a point that is contained by both polygons. -
clipBoundary
private static void clipBoundary(S2Polygon a, boolean reverseA, S2Polygon b, boolean invertB, boolean addSharedEdges, S2PolygonBuilder builder) Clips the boundary of A to the interior of B, and adds the resulting edges tobuilder
. Shells are directed CCW and holes are directed clockwise. IfreverseA
is true, these directions are reversed in polygon A. IfinvertB
is true, the boundary of A is clipped to the exterior rather than the interior of B. IfaddSharedEdges
is true, then the output will include any edges that are shared between A and B (both edges must be in the same direction after any edge reversals are taken into account). -
getNumVertices
public int getNumVertices()Returns the total number of vertices in all loops. -
initToComplement
Initializes this polygon to the complement of the given polygon. -
initToSnapped
Use S2PolygonBuilder to build this polygon by assembling the edges of a given polygon after snapping its vertices to the center of leaf cells. This will simplify the polygon with a tolerance ofS2Projections.maxDiag.getValue(S2CellId.MAX_LEVEL)
, or approximately 0.13 microdegrees, or 1.5cm on the surface of the Earth. Such a polygon can be efficiently compressed when serialized. The snap level can be changed to a non-leaf level if needed. -
invert
private void invert()Inverts this polygon (replacing it by its complement.) -
initToIntersection
Initializes this polygon to the intersection, union, or difference (A - B) of the given two polygons. ThevertexMergeRadius
determines how close two vertices must be to be merged together and how close a vertex must be to an edge in order to be spliced into it (seeS2PolygonBuilder
for details). By default, the merge radius is just large enough to compensate for errors that occur when computing intersection points between edges (S2EdgeUtil.DEFAULT_INTERSECTION_TOLERANCE
).If you are going to convert the resulting polygon to a lower-precision format, it is necessary to increase the merge radius in order to get a valid result after rounding (i.e., no duplicate vertices, etc). For example, if you are going to convert them to
geostore.PolygonProto
format, thenS1Angle.e7(1)
is a good value forvertexMergeRadius
. -
initToIntersectionSloppy
-
initToUnion
-
initToUnionSloppy
-
initToDifference
-
initToDifferenceSloppy
-
initToSimplified
Initializes this polygon to a polygon that contains fewer vertices and is within tolerance of the polygon a, with some caveats.If
snapToCellCenters
is true, the vertices of this polygon will be snapped to the centers of cells at the smallest level that is guaranteed to result in a valid polygon given the specified tolerance.- If there is a very small island in the original polygon, it may disappear completely. Thus some parts of the original polygon may not be close to the simplified polygon. Those parts are small, though, and arguably don't need to be kept.
- However, if there are dense islands, they may all disappear, instead of replacing them by a big simplified island.
- For small tolerances (compared to the polygon size), it may happen that the simplified polygon has more vertices than the original, if the first step of the simplification creates too many self-intersections. One can construct unrealistic cases where that happens to an extreme degree.
-
initToSimplifiedInCell
Initializes this polygon to a polygon that contains fewer vertices and is within tolerance of the polygon a, while ensuring that the vertices on the cell boundary are preserved.Precondition: Polygon a is contained in the cell.
-
initToSimplifiedInternal
private void initToSimplifiedInternal(S2Polygon a, S1Angle tolerance, boolean snapToCellCenters, com.google.common.base.Predicate<S2Point> vertexFilter) Simplifies the polygon. The algorithm is straightforward and naive:- Simplify each loop by removing points while staying in the tolerance zone. This uses
S2Polyline.subsampleVertices(S1Angle)
, which is not guaranteed to be optimal in terms of number of points. - Break any edge in pieces such that no piece intersects any other.
- Use the polygon builder to regenerate the full polygon.
- If
vertexFilter
is not null, the vertices for which it returns true are kept in the simplified polygon.
- Simplify each loop by removing points while staying in the tolerance zone. This uses
-
breakEdgesAndAddToBuilder
Takes a set of possibly intersecting edges, stored in the S2ShapeIndex, and breaks the edges into small pieces so that there is no intersection anymore, and adds all these edges to the builder. -
union
Returns a polygon that is the union of the given polygons. -
unionSloppy
Returns a polygon that is the union of the given polygons; combines vertices that form edges that are almost identical, as defined byvertexMergeRadius
. -
intersectWithPolyline
Intersects this polygon with theS2Polyline
in
and returns the resulting zero or more polylines. The polylines are ordered in the order they would be encountered by traversingin
from beginning to end. Note that the output may include polylines with only one vertex, but there will not be any zero-vertex polylines.This is equivalent to calling
intersectWithPolylineSloppy(com.google.common.geometry.S2Polyline, com.google.common.geometry.S1Angle)
with thevertexMergeRadius
set toS2EdgeUtil.DEFAULT_INTERSECTION_TOLERANCE
. -
intersectWithPolylineSloppy
Similar tointersectWithPolyline(com.google.common.geometry.S2Polyline)
, except that vertices will be dropped as necessary to ensure that all adjacent vertices in the sequence obtained by concatenating the output polylines will be farther thanvertexMergeRadius
apart. Note that this can change the number of output polylines and/or yield single-vertex polylines. -
subtractFromPolyline
Same asintersectWithPolyline(com.google.common.geometry.S2Polyline)
, but subtracts this polygon from the given polyline. -
subtractFromPolylineSloppy
Same asintersectWithPolylineSloppy(com.google.common.geometry.S2Polyline, com.google.common.geometry.S1Angle)
, but subtracts this polygon from the given polyline. -
internalClipPolyline
Clips theS2Polyline
a
to the interior of this polygon. The resulting polyline(s) will be returned. Ifinvert
istrue
, we clipa
to the exterior of this polygon instead. Vertices will be dropped such that adjacent vertices will not be closer thanmergeRadius
.We do the intersection/subtraction by walking the polyline edges. For each edge, we compute all intersections with the polygon boundary and sort them in increasing order of distance along that edge. We then divide the intersection points into pairs, and output a clipped polyline segment for each one. We keep track of whether we're inside or outside of the polygon at all times to decide which segments to output.
-
isNormalized
public boolean isNormalized()Return true if every loop of this polygon shares at most one vertex with its parent loop. Every polygon has a unique normalized form. A polygon can be normalized by passing it through S2Builder (with no snapping) in order to reconstruct the polygon from its edges.Generally there is no reason to convert polygons to normalized form. It is mainly useful for testing in order to compare whether two polygons have exactly the same interior, even when they have a different loop structure. For example, a diamond nested within a square (touching at four points) could be represented as a square with a diamond-shaped hole, or as four triangles. Methods such as
boundaryApproxEquals(S2Polygon, double)
will report these polygons as being different (because they have different boundaries) even though they contain the same points. However if they are both converted to normalized form (the "four triangles" version) then they can be compared more easily. -
boundaryApproxEquals
Returns true if two polygons have the same boundary, except for vertex perturbations. Both polygons must have loops with the same cyclic vertex order and the same nesting hierarchy, but the vertex locations are allowed to differ by up tomaxError
. Note: This method mostly useful only for testing purposes. -
boundaryNear
Returns true if two polygons have boundaries that are withinmaxError
of each other along their entire lengths. More precisely, there must be a bijection between the two sets of loops such thataLoop.boundaryNear(bLoop)
is true for each aLoop inthis
and each bLoop inb
. -
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 interfaceS2Region
-
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 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. -
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
-
boundaryApproxIntersects
Returns true if the polygon boundary intersectstarget
. It may also return true when the polygon boundary does not intersecttarget
but some edge comes within the worst-case error tolerance.Requires:
it.id().contains(target.id())
(This condition is true wheneverit.locate(target)
returns INDEXED. -
contains
The pointp
does not need to be normalized. -
contains
Given an iterator that is already positioned at the S2ShapeIndex.Cell containingp
, returncontains(p)
. -
sortValueLoops
For each map entry, sorts the value list. -
insertLoop
-
initLoop
-
compareBoundary
Returns +1 if this polygon (A) contains the boundary of B, -1 if A excludes the boundary of B, and 0 if the boundaries of A and B cross. -
containsBoundary
Returns true if this polygon (A) contains the entire boundary of B. -
excludesBoundary
Returns true if this polygon (A) excludes the entire boundary of B. -
containsNonCrossingBoundary
Given a polygon A and a loop B whose boundaries do not cross, returns true if A contains the boundary of B. Shared edges are handled according to the rule described incontainsNonCrossingBoundary(S2Loop, S2Loop, boolean)
. -
containsNonCrossingBoundary
Given two loops whose boundaries do not cross (seecompareBoundary(S2Loop)
, returns true if A contains the boundary of B.This method is cheaper than compareBoundary() because it does not test for edge intersections, but it does trigger building the index if there are edges in both polygons.
- Parameters:
b
- the loop to test for containment by this loop; neither loop may be empty or have an edge crossing with the other, and if b is full then bReverse must be false.bReverse
- If true, the boundary of B is reversed first (which only affects the result when there are shared edges).
-
excludesNonCrossingShells
Given two polygons A and B such that the boundary of A does not cross any loop of B, returns true if A excludes all shell boundaries of B. -
excludesNonCrossingComplementShells
Given two polygons A and B such that the boundary of A does not cross any loop of B, returns true if A excludes all shell boundaries of the complement of B. -
anyLoopContains
Returns true if any loop contains the given loop. -
anyLoopIntersects
Returns true if any loop intersects the given loop. -
toString
Returns a human readable representation of the polygon. -
encode
Encodes the polygon 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 the polygon into an uncompressed binary representation, which can be decoded by callingdecode(InputStream)
. The encoding is byte-compatible with the C++ version of the S2 library.- Parameters:
encoder
- The output stream into which the encoding should be written.- Throws:
IOException
- if there was a problem writing into the output stream.
-
encodeCompressed
- Throws:
IOException
-
decode
Decodes a polygon that was encoded usingencode(java.io.OutputStream)
.This method will never return null. It will either throw an exception or return a valid
S2Polygon
.- Parameters:
input
- The input stream containing the encoded polygon data.- Returns:
- the decoded
S2Polygon
. - Throws:
IOException
- if there was a problem reading from the input stream.
-
decodeLossless
- Throws:
IOException
-
decodeCompressed
- Throws:
IOException
-
shape
Returns a shape wrapping this polygon. -
binarySearchShape
S2Polygon.Shape binarySearchShape()Returns an implementation that does a binary search to map an edge to one of a large number of loops. -
linearSearchShape
S2Polygon.Shape linearSearchShape()Returns an implementation that does a linear search to map an edge to one of a number of loops.When the number of loops is small, linear search is faster. Most often there is exactly one loop and the getEdge and getChainStart loops execute zero times.
-