Class S2ConvexHullQuery

java.lang.Object
com.google.common.geometry.S2ConvexHullQuery

@GwtCompatible(serializable=true) public final class S2ConvexHullQuery extends 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.

  • Field Details

    • 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:
    • bound

      private final S2LatLngRect.Builder bound
    • points

      private final List<S2Point> points
  • Constructor Details

    • S2ConvexHullQuery

      public S2ConvexHullQuery()
  • Method Details

    • 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 List<S2Point> getMonotoneChain(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).
    • getSingleEdgeLoop

      private static S2Loop getSingleEdgeLoop(S2Point a, S2Point b)
      Construct a loop consisting of the two vertices and their midpoint.