Class S2ConvexHullQuery
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 ClassesModifier and TypeClassDescriptionprivate static final class
A comparator for sorting points in CCW around a central point "center". -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final S2LatLngRect.Builder
private static final double
The length of edges to expand away from degenerate points to form a polygon. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
Adds a loop to the input geometry.void
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.Computes a bounding cap for the input geometry provided.Computes the convex hull of the input geometry provided.getMonotoneChain
(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
Constructs a 3-vertex polygon consisting of "p" and two nearby vertices.
-
Field Details
-
OFFSET_FOR_SINGLE_POINT_LOOP
private static final double OFFSET_FOR_SINGLE_POINT_LOOPThe length of edges to expand away from degenerate points to form a polygon.- See Also:
-
bound
-
points
-
-
Constructor Details
-
S2ConvexHullQuery
public S2ConvexHullQuery()
-
-
Method Details
-
addPoint
Adds a point to the input geometry. -
addPolyline
Adds a polyline to the input geometry. -
addLoop
Adds a loop to the input geometry. -
addPolygon
Adds a polygon to the input geometry. -
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
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
-
getSinglePointLoop
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). -
getSingleEdgeLoop
Construct a loop consisting of the two vertices and their midpoint.
-