Class S2ConvexHullQuery
- java.lang.Object
-
- com.google.common.geometry.S2ConvexHullQuery
-
@GwtCompatible(serializable=true) public final class S2ConvexHullQuery extends java.lang.Object
S2ConvexHullQuery builds the convex hull of any collection of points, polylines, loops, and polygons. It returns a single convex loop.The convex hull is defined as the smallest convex region on the sphere that contains all of the input geometry. Recall that a region is "convex" if for every pair of points inside the region, the straight edge between them is also inside the region. In our case, a "straight" edge is a geodesic, i.e. the shortest path on the sphere between two points.
Containment of input geometry is defined as follows:
- Each input loop and polygon is contained by the convex hull exactly (i.e., according to S2Polygon.contains(S2Polygon)).
- Each input point is either contained by the convex hull or is a vertex of the convex hull. (Recall that S2Loops do not necessarily contain their vertices.)
- For each input polyline, the convex hull contains all of its vertices according to the rule for points above. (The definition of convexity then ensures that the convex hull also contains the polyline edges.)
To use this class, call the add*() methods to add your input geometry, and then call getConvexHull(). Note that getConvexHull() does *not* reset the state; you can continue adding geometry if desired and compute the convex hull again. If you want to start from scratch, simply declare a new S2ConvexHullQuery object (they are cheap to create).
This class is not thread-safe.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
S2ConvexHullQuery.OrderedCcwAround
A comparator for sorting points in CCW around a central point "center".
-
Field Summary
Fields Modifier and Type Field Description private S2LatLngRect.Builder
bound
private static double
OFFSET_FOR_SINGLE_POINT_LOOP
The length of edges to expand away from degenerate points to form a polygon.private java.util.List<S2Point>
points
-
Constructor Summary
Constructors Constructor Description S2ConvexHullQuery()
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
addLoop(S2Loop loop)
Adds a loop to the input geometry.void
addPoint(S2Point point)
Adds a point to the input geometry.void
addPolygon(S2Polygon polygon)
Adds a polygon to the input geometry.void
addPolyline(S2Polyline polyline)
Adds a polyline to the input geometry.S2Cap
getCapBound()
Computes a bounding cap for the input geometry provided.S2Loop
getConvexHull()
Computes the convex hull of the input geometry provided.private static java.util.List<S2Point>
getMonotoneChain(java.util.List<S2Point> points)
private static S2Loop
getSingleEdgeLoop(S2Point a, S2Point b)
Construct a loop consisting of the two vertices and their midpoint.private static S2Loop
getSinglePointLoop(S2Point p)
Constructs a 3-vertex polygon consisting of "p" and two nearby vertices.
-
-
-
Field Detail
-
OFFSET_FOR_SINGLE_POINT_LOOP
private static final double OFFSET_FOR_SINGLE_POINT_LOOP
The length of edges to expand away from degenerate points to form a polygon.- See Also:
- Constant Field Values
-
bound
private final S2LatLngRect.Builder bound
-
points
private final java.util.List<S2Point> points
-
-
Method Detail
-
addPoint
public void addPoint(S2Point point)
Adds a point to the input geometry.
-
addPolyline
public void addPolyline(S2Polyline polyline)
Adds a polyline to the input geometry.
-
addLoop
public void addLoop(S2Loop loop)
Adds a loop to the input geometry.
-
addPolygon
public void addPolygon(S2Polygon polygon)
Adds a polygon to the input geometry.
-
getCapBound
public S2Cap getCapBound()
Computes a bounding cap for the input geometry provided.Note that this method does not clear the geometry; you can continue adding to it and call this method again if desired.
-
getConvexHull
public S2Loop getConvexHull()
Computes the convex hull of the input geometry provided.If there is no geometry, this method returns an empty loop containing no points (see S2Loop.isEmpty()).
If the geometry spans more than half of the sphere, this method returns a full loop containing the entire sphere (see S2Loop.isFull()).
If the geometry contains 1 or 2 points, or a single edge, this method returns a very small loop consisting of three vertices (which are a superset of the input vertices).
Note that this method does not clear the geometry; you can continue adding to it and call this method again if desired.
-
getMonotoneChain
private static java.util.List<S2Point> getMonotoneChain(java.util.List<S2Point> points)
-
getSinglePointLoop
private static S2Loop getSinglePointLoop(S2Point p)
Constructs a 3-vertex polygon consisting of "p" and two nearby vertices. Note that contains(p) may be false for the resulting loop (see comments at top of file).
-
-