Class S2PolygonBuilder
Some of the situations this class was designed to handle:
- 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.
- 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.
- 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.
- As a tool for implementing other polygon operations by generating a collection of directed edges and then assembling them into loops.
assemblePolygon()
).-
Nested Class Summary
Nested Classes -
Field Summary
FieldsModifier and TypeFieldDescriptionThe current set of edges, grouped by origin.private final S2PolygonBuilder.Options
Unique collection of the starting (first) vertex of all edges, in the order they are added toedges
. -
Constructor Summary
ConstructorsConstructorDescriptionDefault constructor for well-behaved polygons.S2PolygonBuilder
(S2PolygonBuilder.Options options) -
Method Summary
Modifier and TypeMethodDescriptionboolean
Adds the given edge to the polygon builder and returns true if the edge was actually added to the edge graph.void
Adds all edges in the given loop.void
addPolygon
(S2Polygon polygon) Add all loops in the given polygon.private S2Loop
assembleLoop
(S2Point v0, S2Point v1, List<S2Edge> unusedEdges) We start at the given edge and assemble a loop taking left turns whenever possible.boolean
assembleLoops
(List<S2Loop> loops, List<S2Edge> unusedEdges) Assembles the given edges into as many non-crossing loops as possible.Convenience method for when you don't care about unused edges.boolean
assemblePolygon
(S2Polygon polygon, List<S2Edge> unusedEdges) Like AssembleLoops, but then assembles the loops into a polygon.buildMergeMap
(S1Angle snapDistance) Clusters vertices that are separated by at mostS2PolygonBuilder.Options.getMergeDistance()
and returns a map of each one to a single representative vertex for all the vertices in the cluster.private void
private void
private void
boolean
Returns true if the given directed edge [v0 -> v1] is present in the directed edge graph.private S2PointIndex
<Void> index()
Returns an index of all the points.private void
moveVertices
(Map<S2Point, S2Point> mergeMap) Moves a set of vertices from old to new positions.options()
private void
rejectLoop
(S2Loop v, int n, List<S2Edge> unusedEdges) Erases all edges of the given loop and marks them as unused.private void
rejectLoop
(List<S2Point> v, int n, List<S2Edge> unusedEdges) Marks all edges of the given loop as unused.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.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.private void
spliceEdges
(S1Angle spliceDistance) Splices vertices that are near an edge onto the edge.
-
Field Details
-
options
-
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
Unique collection of the starting (first) vertex of all edges, in the order they are added toedges
.
-
-
Constructor Details
-
S2PolygonBuilder
public S2PolygonBuilder()Default constructor for well-behaved polygons. Uses the DIRECTED_XOR options. -
S2PolygonBuilder
-
-
Method Details
-
options
-
addEdge
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
Adds all edges in the given loop. If thesign()
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
Add all loops in the given polygon. Shells and holes are added with opposite orientations as described foraddLoop(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
Returns a new point, snapped to the center of the cell containing the given point at the specified level. -
snapLoopToLevel
Returns a new loop where the vertices of the given loop have been snapped to the centers of cells at the specified level. -
assembleLoops
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. IfunusedEdges
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 useS2PolygonBuilder.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
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
Convenience method for when you don't care about unused edges. -
eraseEdge
-
eraseLoop
-
eraseLoop
-
assembleLoop
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
Erases all edges of the given loop and marks them as unused. -
rejectLoop
Marks all edges of the given loop as unused. -
moveVertices
Moves a set of vertices from old to new positions. -
index
Returns an index of all the points. -
buildMergeMap
Clusters vertices that are separated by at mostS2PolygonBuilder.Options.getMergeDistance()
and returns a map of each one to a single representative vertex for all the vertices in the cluster. -
hasEdge
Returns true if the given directed edge [v0 -> v1] is present in the directed edge graph. -
spliceEdges
Splices vertices that are near an edge onto the edge.
-