Class S2ShapeUtil
- java.lang.Object
-
- com.google.common.geometry.S2ShapeUtil
-
@GwtCompatible public class S2ShapeUtil extends java.lang.Object
Utilities for working with S2Shape.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
S2ShapeUtil.AreaCentroidMeasure
A collector of both combined area and centroid values.static class
S2ShapeUtil.AreaMeasure
A collector of the steradian area.static class
S2ShapeUtil.CentroidMeasure
A collector of the center of mass.static interface
S2ShapeUtil.IntPredicate
A filter of indexes.(package private) static class
S2ShapeUtil.S2EdgeVectorShape
S2EdgeVectorShape is an S2Shape representing a set of unrelated edges.static interface
S2ShapeUtil.TriangleConsumer
A consumer of triangles.
-
Field Summary
Fields Modifier and Type Field Description private static java.util.Comparator<S2Edge>
EDGE_ORDER
Compares edges by start point, and then by end point.
-
Constructor Summary
Constructors Modifier Constructor Description private
S2ShapeUtil()
Utility methods only.
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static boolean
containsBruteForce(S2Shape shape, S2Point point)
Returns true if the given shape contains the given point.static boolean
equals(S2ShapeIndex.Cell a, S2ShapeIndex.Cell b)
Returns true if the index cells 'a' and 'b' contain identical contents.static boolean
equals(S2ShapeIndex.S2ClippedShape a, S2ShapeIndex.S2ClippedShape b)
Returns true if the clipped shapes 'a' and 'b' have identical edge offsets.static boolean
equals(S2ShapeIndex a, S2ShapeIndex b)
Returns true if all methods of the two S2ShapeIndex values return identical results, including all the S2Shapes in both indexes.static boolean
equals(S2Shape a, S2Shape b)
Returns true if all methods of the two S2Shapes return identical results, except for id() and typeTag().static boolean
equals(java.util.List<S2Shape> a, java.util.List<S2Shape> b)
Returns true if the lists 'a' and 'b' have identical shapes according toequals(S2Shape, S2Shape)
.(package private) static boolean
findAnyCrossing(S2ShapeIndex index, java.util.List<S2Loop> loops, S2Error error)
Given an S2ShapeIndex containing a set of loops, return true if any loop has a self-intersection (including duplicate vertices) or crosses any other loop (including vertex crossings and duplicate edges) and set "error" to a human-readable error message.(package private) static boolean
findLoopCrossing(java.util.List<S2Loop> loops, S2ShapeIndex.Cell cell, S2Error error)
Returns true if any of the given loops crosses a different loop (including vertex crossings) or two loops share a common edge, and sets "error" to a human-readable error message.(package private) static boolean
findSelfIntersection(S2ShapeIndex.S2ClippedShape aClipped, S2Loop aLoop, S2Error error)
Test for crossings between all edge pairs that do not share a vertex.(package private) static boolean
findSelfIntersection(S2ShapeIndex index, S2Loop loop, S2Error error)
Given an S2ShapeIndex containing a single loop, return true if the loop has a self-intersection (including duplicate vertices) and set "error" to a human-readable error message.(package private) static boolean
findSelfIntersection(java.util.List<S2Loop> loops, S2ShapeIndex.Cell cell, S2Error error)
Returns true if any of the given loops has a self-intersection (including a duplicate vertex), and set "error" to a human-readable error message.(package private) static boolean
getCrossingError(java.util.List<S2Loop> loops, S2Loop aLoop, int ai, S2Loop bLoop, int bj, int crossing, S2Error error)
Given two loop edges for which RobustCrossing returned a non-negative result "crossing", returns true if there is a crossing and sets "error" to a human-readable error message, otherwise returns false.static S2Shape.ReferencePoint
getReferencePoint(S2Shape shape)
This is a helper function for implementing S2Shape.getReferencePoint().private static java.lang.Boolean
getReferencePointAtVertex(S2Shape shape, S2Point vtest)
Returns null if 'vtest' is balanced (see definition above), otherwise 'vtest' is unbalanced and the return value indicates whether it is contained by 'shape'.(package private) static int
indexOf(java.util.List<? extends S2Shape> shapes, S2Shape shape)
Returns the index ofshape
inshapes
asList.indexOf(Object)
, but using identity instead of equality to honor the semantics of S2ShapeIndex (where adding two S2Loops that are equal but not the same instance is treated as adding two separate shapes, with distinct shape IDs.)static int
lowerBound(int low, int high, S2ShapeUtil.IntPredicate targetIsGreater)
Returns the lowest index in the range[low, high)
not smaller than a target.(package private) static com.google.common.collect.Multimap<S2Shape,java.lang.Integer>
shapeToShapeId(S2ShapeIndex index)
Returns a multimap ofS2Shape
fromindex
to the shape's ID (i.e., its position withinindex.shapes
).static int
upperBound(int low, int high, S2ShapeUtil.IntPredicate targetIsSmaller)
Returns the lowest index in the range[low, high)
greater than a target.static void
visitSurfaceIntegral(java.util.List<S2Point> vertices, S2ShapeUtil.TriangleConsumer consumer)
Visits the surface integral of the vertices, that is, a collection of oriented triangles, possibly overlapping.
-
-
-
Field Detail
-
EDGE_ORDER
private static final java.util.Comparator<S2Edge> EDGE_ORDER
Compares edges by start point, and then by end point.
-
-
Method Detail
-
findSelfIntersection
static boolean findSelfIntersection(S2ShapeIndex index, S2Loop loop, S2Error error)
Given an S2ShapeIndex containing a single loop, return true if the loop has a self-intersection (including duplicate vertices) and set "error" to a human-readable error message. Otherwise return false and leave "error" unchanged.
-
findAnyCrossing
static boolean findAnyCrossing(S2ShapeIndex index, java.util.List<S2Loop> loops, S2Error error)
Given an S2ShapeIndex containing a set of loops, return true if any loop has a self-intersection (including duplicate vertices) or crosses any other loop (including vertex crossings and duplicate edges) and set "error" to a human-readable error message. Otherwise return false and leave "error" unchanged.
-
findSelfIntersection
static boolean findSelfIntersection(S2ShapeIndex.S2ClippedShape aClipped, S2Loop aLoop, S2Error error)
Test for crossings between all edge pairs that do not share a vertex. This means that (a) the loop edge indices must differ by 2 or more, and (b) the pair cannot consist of the first and last loop edges. Part (b) is worthwhile in the case of very small loops; e.g. it reduces the number of crossing tests in a loop with four edges from two to one.
-
indexOf
static int indexOf(java.util.List<? extends S2Shape> shapes, S2Shape shape)
Returns the index ofshape
inshapes
asList.indexOf(Object)
, but using identity instead of equality to honor the semantics of S2ShapeIndex (where adding two S2Loops that are equal but not the same instance is treated as adding two separate shapes, with distinct shape IDs.)
-
lowerBound
public static int lowerBound(int low, int high, S2ShapeUtil.IntPredicate targetIsGreater)
Returns the lowest index in the range[low, high)
not smaller than a target.
-
upperBound
public static int upperBound(int low, int high, S2ShapeUtil.IntPredicate targetIsSmaller)
Returns the lowest index in the range[low, high)
greater than a target.
-
findSelfIntersection
static boolean findSelfIntersection(java.util.List<S2Loop> loops, S2ShapeIndex.Cell cell, S2Error error)
Returns true if any of the given loops has a self-intersection (including a duplicate vertex), and set "error" to a human-readable error message. Otherwise return false and leave "error" unchanged. All tests are limited to edges that intersect the given cell.
-
getCrossingError
static boolean getCrossingError(java.util.List<S2Loop> loops, S2Loop aLoop, int ai, S2Loop bLoop, int bj, int crossing, S2Error error)
Given two loop edges for which RobustCrossing returned a non-negative result "crossing", returns true if there is a crossing and sets "error" to a human-readable error message, otherwise returns false.
-
findLoopCrossing
static boolean findLoopCrossing(java.util.List<S2Loop> loops, S2ShapeIndex.Cell cell, S2Error error)
Returns true if any of the given loops crosses a different loop (including vertex crossings) or two loops share a common edge, and sets "error" to a human-readable error message. Otherwise return false and leaves "error" unchanged. All tests are limited to edges that intersect the given cell.
-
equals
public static boolean equals(S2Shape a, S2Shape b)
Returns true if all methods of the two S2Shapes return identical results, except for id() and typeTag(). Also returns true if both instances are null.
-
equals
public static boolean equals(java.util.List<S2Shape> a, java.util.List<S2Shape> b)
Returns true if the lists 'a' and 'b' have identical shapes according toequals(S2Shape, S2Shape)
.
-
equals
public static boolean equals(S2ShapeIndex.S2ClippedShape a, S2ShapeIndex.S2ClippedShape b)
Returns true if the clipped shapes 'a' and 'b' have identical edge offsets.This method does not check that
a.shape()
andb.shape()
are equal.
-
equals
public static boolean equals(S2ShapeIndex.Cell a, S2ShapeIndex.Cell b)
Returns true if the index cells 'a' and 'b' contain identical contents.
-
equals
public static boolean equals(S2ShapeIndex a, S2ShapeIndex b)
Returns true if all methods of the two S2ShapeIndex values return identical results, including all the S2Shapes in both indexes.
-
containsBruteForce
public static boolean containsBruteForce(S2Shape shape, S2Point point)
Returns true if the given shape contains the given point. Most clients should not use this method, since its running time is linear in the number of shape edges. Instead clients should create an S2ShapeIndex and useS2ContainsPointQuery
, since that strategy is much more efficient when many points need to be tested.Polygon boundaries are treated as being semi-open. See
S2ContainsPointQuery.S2VertexModel
for other options.
-
getReferencePoint
public static S2Shape.ReferencePoint getReferencePoint(S2Shape shape)
This is a helper function for implementing S2Shape.getReferencePoint().Given a shape consisting of closed polygonal loops, the interior of the shape is defined as the region to the left of all edges (which must be oriented consistently). This function then chooses an arbitrary point and returns true if that point is contained by the shape.
Unlike S2Loop and S2Polygon, this method allows duplicate vertices and edges, which requires some extra care with definitions. The rule that we apply is that an edge and its reverse edge "cancel" each other: the result is the same as if that edge pair were not present. Therefore shapes that consist only of degenerate loop(s) are either empty or full; by convention, the shape is considered full if and only if it contains an empty loop (see S2LaxPolygonShape for details).
Determining whether a loop on the sphere contains a point is harder than the corresponding problem in 2D plane geometry. It cannot be implemented just by counting edge crossings because there is no such thing as a "point at infinity" that is guaranteed to be outside the loop.
-
getReferencePointAtVertex
private static java.lang.Boolean getReferencePointAtVertex(S2Shape shape, S2Point vtest)
Returns null if 'vtest' is balanced (see definition above), otherwise 'vtest' is unbalanced and the return value indicates whether it is contained by 'shape'.
-
shapeToShapeId
static com.google.common.collect.Multimap<S2Shape,java.lang.Integer> shapeToShapeId(S2ShapeIndex index)
Returns a multimap ofS2Shape
fromindex
to the shape's ID (i.e., its position withinindex.shapes
).
-
visitSurfaceIntegral
public static void visitSurfaceIntegral(java.util.List<S2Point> vertices, S2ShapeUtil.TriangleConsumer consumer)
Visits the surface integral of the vertices, that is, a collection of oriented triangles, possibly overlapping.Let the sign of a triangle be +1 if it is CCW and -1 otherwise, and let the sign of a point "x" be the sum of the signs of the triangles containing "x". Then the collection of triangles T is chosen such that either:
- Each point in the loop interior has sign +1, and sign 0 otherwise; or
- Each point in the loop exterior has sign -1, and sign 0 otherwise.
The triangles basically consist of a "fan" from vertex 0 to every loop edge that does not include vertex 0. These triangles will always satisfy either (1) or (2).
However, what makes this a bit tricky is that spherical edges become numerically unstable as their length approaches 180 degrees. Of course there is not much we can do if the loop itself contains such edges, but we would like to make sure that all the triangle edges under our control (i.e., the non-loop edges) are stable. For example, consider a loop around the equator consisting of four equally spaced points. This is a well-defined loop, but we cannot just split it into two triangles by connecting vertex 0 to vertex 2.
We handle this type of situation by moving the origin of the triangle fan whenever we are about to create an unstable edge. We choose a new location for the origin such that all relevant edges are stable. We also create extra triangles with the appropriate orientation so that the sum of the triangle signs is still correct at every point.
-
-