Class S2Builder

S2Builder is a tool for assembling polygonal geometry from edges. Here are some of the things it is designed for:

class S2Builder ;

1. Building polygons, polylines, and polygon meshes from unsorted collections of edges.

2. Snapping geometry to discrete representations (such as S2CellId centers or E7 lat/lng coordinates) while preserving the input topology and with guaranteed error bounds.

3. Simplifying geometry (e.g. for indexing, display, or storage).

4. Importing geometry from other formats, including repairing geometry that has errors.

5. As a tool for implementing more complex operations such as polygon intersections and unions.

The implementation is based on the framework of "snap rounding". Unlike most snap rounding implementations, S2Builder defines edges as geodesics on the sphere (straight lines) and uses the topology of the sphere (i.e., there are no "seams" at the poles or 180th meridian). The algorithm is designed to be 100% robust for arbitrary input geometry. It offers the following properties:

- Guaranteed bounds on how far input vertices and edges can move during the snapping process (i.e., at most the given "snap_radius").

- Guaranteed minimum separation between edges and vertices other than their endpoints (similar to the goals of Iterated Snap Rounding). In other words, edges that do not intersect in the output are guaranteed to have a minimum separation between them.

- Idempotency (similar to the goals of Stable Snap Rounding), i.e. if the input already meets the output criteria then it will not be modified.

- Preservation of the input topology (up to the creation of degeneracies). This means that there exists a continuous deformation from the input to the output such that no vertex crosses an edge. In other words, self-intersections won't be created, loops won't change orientation, etc.

- The ability to snap to arbitrary discrete point sets (such as S2CellId centers, E7 lat/lng points on the sphere, or simply a subset of the input vertices), rather than being limited to an integer grid.

Here are some of its other features:

- It can handle both directed and undirected edges. Undirected edges can be useful for importing data from other formats, e.g. where loops have unspecified orientations.

- It can eliminate self-intersections by finding all edge pairs that cross and adding a new vertex at each intersection point.

- It can simplify polygons to within a specified tolerance. For example, if two vertices are close enough they will be merged, and if an edge passes nearby a vertex then it will be rerouted through that vertex. Optionally, it can also detect nearly straight chains of short edges and replace them with a single long edge, while maintaining the same accuracy, separation, and topology guarantees ("simplify_edge_chains").

- It supports many different output types through the concept of "layers" (polylines, polygons, polygon meshes, etc). You can build multiple layers at once in order to ensure that snapping does not create intersections between different objects (for example, you can simplify a set of contour lines without the risk of having them cross each other).

- It supports edge labels, which allow you to attach arbitrary information to edges and have it preserved during the snapping process. (This can also be achieved using layers, at a coarser level of granularity.)

Constructors

NameDescription
this () Default constructor; requires Init() to be called.
this (options) Convenience constructor that calls Init(). Note that to use the default options, C++ syntax requires an extra layer of parentheses:

Methods

NameDescription
addEdge (v0, v1) Adds the given edge to the current layer.
addIsFullPolygonPredicate (predicate) For layers that will be assembled into polygons, this method specifies a predicate that will be called to determine whether the polygon is empty or full except for the given degeneracies. (See IsFullPolygonPredicate above.)
addLoop (loop) Adds the edges in the given loop. If the sign() of the loop is negative (i.e. this loop represents a hole within a polygon), the edge directions are automatically reversed to ensure that the polygon interior is always to the left of every edge.
addPoint (v) Adds a degenerate edge (representing a point) to the current layer.
addPolygon (polygon) Adds the loops in the given polygon. Loops representing holes have their edge directions automatically reversed as described for AddLoop(). 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.
addPolyline (polyline) Adds the edges in the given polyline. (Note that if the polyline consists of 0 or 1 vertices, this method does nothing.)
addShape (shape) Adds the edges of the given shape to the current layer.
build (error) Performs the requested edge splitting, snapping, simplification, etc, and then assembles the resulting edges into the requested output layers.
clearLabels () Clear the stack of labels.
forceVertex (vertex) Forces a vertex to be located at the given position. This can be used to prevent certain input vertices from moving. However if you are trying to preserve part of the input boundary, be aware that this option does not prevent edges from being split by new vertices.
initialize (options) Initializes an S2Builder with the given options.
popLabel () Remove a label from the stack.
pushLabel (label) Add a label to the stack.
reset () Clears all input data and resets the builder state. Any options specified are preserved.
setLabel (label) Convenience function that clears the stack and adds a single label.
startLayer (layer) Starts a new output layer. This method must be called before adding any edges to the S2Builder. You may call this method multiple times to build multiple geometric objects that are snapped to the same set of sites.

Inner classes

NameDescription
SnapFunction A SnapFunction restricts the locations of the output vertices. For example, there are predefined snap functions that require vertices to be located at S2CellId centers or at E5/E6/E7 coordinates. The SnapFunction can also specify a minimum spacing between vertices (the "snap radius").

Enums

NameDescription
EdgeType Indicates whether the input edges are undirected. Typically this is specified for each output layer (e.g., s2builderutil::S2PolygonLayer).

Aliases

NameDescription
InputEdgeId Identifies an input edge.
InputEdgeIdSetId Identifies the set of input edge ids that were snapped to a given edge.
InputVertexId Identifies an input vertex.
IsFullPolygonPredicate For output layers that represent polygons, there is an ambiguity inherent in spherical geometry that does not exist in planar geometry. Namely, if a polygon has no edges, does it represent the empty polygon (containing no points) or the full polygon (containing all points)? This ambiguity also occurs for polygons that consist only of degeneracies, e.g. a degenerate loop with only two edges could be either a degenerate shell in the empty polygon or a degenerate hole in the full polygon.
Label Every edge can have a set of non-negative integer labels attached to it. When used with an appropriate layer type, you can then retrieve the labels associated with each output edge. This can be useful when merging or combining data from several sources. (Note that in many cases it is easier to use separate output layers rather than labels.)

Caveats

- Because S2Builder only works with edges, it cannot distinguish between the empty and full polygons. If your application can generate both the empty and full polygons, you must implement logic outside of this class.

Example showing how to snap a polygon to E7 coordinates: 

S2Builder builder(S2Builder.Options(new IntLatLngSnapFunction(7)));
auto output = new S2Polygon();
builder.startLayer(new S2PolygonLayer(output));
builder.addPolygon(input);
S2Error error;
if (!builder.build(&error)) {
  logger.logError(error);
  ...
}