Class 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.

    • 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
      • points

        private final java.util.List<S2Point> points
    • Constructor Detail

      • S2ConvexHullQuery

        public S2ConvexHullQuery()
    • 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).
      • getSingleEdgeLoop

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