S2Builder

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

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

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);
  ...
}

Constructors

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

Members

Aliases

InputEdgeId alias InputEdgeId = int: Identifies an input edge.
InputEdgeIdSetId alias InputEdgeIdSetId = int: Identifies the set of input edge ids that were snapped to a given edge.
InputVertexId alias InputVertexId = int: Identifies an input vertex.
IsFullPolygonPredicate alias IsFullPolygonPredicate = bool function(in Graph g, ref S2Error error): 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 alias Label = int: 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.)
LabelSetId alias LabelSetId = int: Undocumented in source.

Classes

Options class Options: Undocumented in source.
SnapFunction class 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

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

Functions

addEdge void addEdge(S2Point v0, S2Point v1): Adds the given edge to the current layer.
addIsFullPolygonPredicate void addIsFullPolygonPredicate(IsFullPolygonPredicate 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 void addLoop(S2Loop 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 void addPoint(S2Point v): Adds a degenerate edge (representing a point) to the current layer.
addPolygon void addPolygon(S2Polygon 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 void addPolyline(S2Polyline polyline): Adds the edges in the given polyline. (Note that if the polyline consists of 0 or 1 vertices, this method does nothing.)
addShape void addShape(S2Shape shape): Adds the edges of the given shape to the current layer.
build bool build(S2Error error): Performs the requested edge splitting, snapping, simplification, etc, and then assembles the resulting edges into the requested output layers.
clearLabels void clearLabels(): Clear the stack of labels.
forceVertex void forceVertex(S2Point 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 void initialize(Options options): Initializes an S2Builder with the given options.
options const(Options) options(): Undocumented in source. Be warned that the author may not have intended to support it.
popLabel void popLabel(): Remove a label from the stack.
pushLabel void pushLabel(Label label): Add a label to the stack. REQUIRES: label >= 0.
reset void reset(): Clears all input data and resets the builder state. Any options specified are preserved.
setLabel void setLabel(Label label): Convenience function that clears the stack and adds a single label. REQUIRES: label >= 0.
startLayer void startLayer(Layer 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.