Class S2PolygonBuilder

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

@GwtCompatible(serializable=false) public final class S2PolygonBuilder extends Object
This is a simple class for assembling polygons out of edges. It requires that no two edges cross. It can handle both directed and undirected edges, and, optionally, it can remove duplicate-edge pairs (consisting of two identical edges or an edge and its reverse edge). This is useful for computing seamless unions of polygons that have been cut into pieces.

Some of the situations this class was designed to handle:

  1. Computing the union of disjoint polygons that may share part of their boundaries. For example, reassembling a lake that has been split into two loops by a state boundary.
  2. Constructing polygons from input data that do not follow S2 conventions, i.e., where loops may have repeated vertices, or distinct loops may share edges, or shells and holes having opposite or unspecified orientations.
  3. Computing the symmetric difference of a set of polygons whose edges intersect only at vertices. This can be used to implement a limited form of polygon intersection or subtraction as well as unions.
  4. As a tool for implementing other polygon operations by generating a collection of directed edges and then assembling them into loops.
Caveat: Because S2PolygonBuilder only works with polygon boundaries, it cannot distinguish between the empty and full polygon. If your application can generate both the empty and full polygons, you must implement logic outside of this class (see assemblePolygon()).
  • Field Details

    • options

      private final S2PolygonBuilder.Options options
    • edges

      private final Map<S2Point,com.google.common.collect.Multiset<S2Point>> edges
      The current set of edges, grouped by origin. The set of destination vertices is a multiset so that the same edge can be present more than once.
    • startingVertices

      private final List<S2Point> startingVertices
      Unique collection of the starting (first) vertex of all edges, in the order they are added to edges.
  • Constructor Details

    • S2PolygonBuilder

      public S2PolygonBuilder()
      Default constructor for well-behaved polygons. Uses the DIRECTED_XOR options.
    • S2PolygonBuilder

      public S2PolygonBuilder(S2PolygonBuilder.Options options)
  • Method Details

    • options

      public S2PolygonBuilder.Options options()
    • addEdge

      public boolean addEdge(S2Point v0, S2Point v1)
      Adds the given edge to the polygon builder and returns true if the edge was actually added to the edge graph.

      This method should be used for input data that may not follow S2 polygon conventions. Note that edges are not allowed to cross each other. Also note that as a convenience, edges where v0 == v1 are ignored.

    • addLoop

      public void addLoop(S2Loop loop)
      Adds all edges in the given loop. If the sign() of the loop is negative (i.e., this loop represents a hole), the reverse edges are added instead. This implies that "shells" are CCW and "holes" are CW, as required for the directed edges convention described above.

      This method does not take ownership of the loop.

    • addPolygon

      public void addPolygon(S2Polygon polygon)
      Add all loops in the given polygon. Shells and holes are added with opposite orientations as described for addLoop(S2Loop). Note that this method does not distinguish between the empty and full polygons, i.e. adding a full polygon has the same effect as adding an empty one.
    • snapPointToLevel

      private S2Point snapPointToLevel(S2Point p, int level)
      Returns a new point, snapped to the center of the cell containing the given point at the specified level.
    • snapLoopToLevel

      private S2Loop snapLoopToLevel(S2Loop loop, int level)
      Returns a new loop where the vertices of the given loop have been snapped to the centers of cells at the specified level.
    • assembleLoops

      public boolean assembleLoops(List<S2Loop> loops, @Nullable List<S2Edge> unusedEdges)
      Assembles the given edges into as many non-crossing loops as possible. When there is a choice about how to assemble the loops, then CCW loops are preferred. Returns true if all edges were assembled. If unusedEdges is not null, it is initialized to the set of edges that could not be assembled into loops.

      Note that if S2PolygonBuilder.Options.getXorEdges() returns false and duplicate edge pairs may be present, then use S2PolygonBuilder.Options.Builder.setUndirectedEdges(boolean) to set it to true, unless all loops can be assembled in a counter-clockwise direction. Otherwise this method may not be able to assemble all loops due to its preference for CCW loops.

      This method resets the S2PolygonBuilder state so that it can be reused.

    • assemblePolygon

      public boolean assemblePolygon(S2Polygon polygon, @Nullable List<S2Edge> unusedEdges)
      Like AssembleLoops, but then assembles the loops into a polygon. If the edges were directed, then it is expected that holes and shells will have opposite orientations, and the polygon interior is to the left of all edges. If the edges were undirected, then all loops are first normalized so that they enclose at most half of the sphere, and the polygon interior consists of points enclosed by an odd number of loops.

      For this method to succeed, there should be no duplicate edges in the input. If this is not known to be true, then the "xor_edges" option should be set (which is true by default).

      Note that because the polygon is constructed from its boundary, this method cannot distinguish between the empty and full polygons. An empty boundary always yields an empty polygon. If the result should sometimes be the full polygon, such logic must be implemented outside of this class (and will need to consider factors other than the polygon's boundary). For example, it is often possible to estimate the polygon area.

    • assemblePolygon

      public S2Polygon assemblePolygon()
      Convenience method for when you don't care about unused edges.
    • eraseEdge

      private void eraseEdge(S2Point v0, S2Point v1)
    • eraseLoop

      private void eraseLoop(List<S2Point> v, int n)
    • eraseLoop

      private void eraseLoop(S2Loop v, int n)
    • assembleLoop

      private S2Loop assembleLoop(S2Point v0, S2Point v1, @Nullable List<S2Edge> unusedEdges)
      We start at the given edge and assemble a loop taking left turns whenever possible. We stop the loop as soon as we encounter any vertex that we have seen before *except* for the first vertex (v0). This ensures that only CCW loops are constructed when possible.
    • rejectLoop

      private void rejectLoop(S2Loop v, int n, List<S2Edge> unusedEdges)
      Erases all edges of the given loop and marks them as unused.
    • rejectLoop

      private void rejectLoop(List<S2Point> v, int n, List<S2Edge> unusedEdges)
      Marks all edges of the given loop as unused.
    • moveVertices

      private void moveVertices(Map<S2Point,S2Point> mergeMap)
      Moves a set of vertices from old to new positions.
    • index

      private S2PointIndex<Void> index()
      Returns an index of all the points.
    • buildMergeMap

      private Map<S2Point,S2Point> buildMergeMap(S1Angle snapDistance)
      Clusters vertices that are separated by at most S2PolygonBuilder.Options.getMergeDistance() and returns a map of each one to a single representative vertex for all the vertices in the cluster.
    • hasEdge

      public boolean hasEdge(S2Point v0, S2Point v1)
      Returns true if the given directed edge [v0 -> v1] is present in the directed edge graph.
    • spliceEdges

      private void spliceEdges(S1Angle spliceDistance)
      Splices vertices that are near an edge onto the edge.