S2BooleanOperation

This class implements boolean operations (intersection, union, difference, and symmetric difference) for regions whose boundaries are defined by geodesic edges.

S2BooleanOperation operates on exactly two input regions at a time. Each region is represented as an S2ShapeIndex and may contain any number of points, polylines, and polygons. The region is essentially the union of these objects, except that polygon interiors must be disjoint from all other geometry (including other polygon interiors). If the input geometry for a region does not meet this condition, it can be normalized by computing its union first. Note that points or polylines are allowed to coincide with the boundaries of polygons.

Degeneracies are supported. A polygon loop or polyline may consist of a single edge from a vertex to itself, and polygons may contain "sibling pairs" consisting of an edge and its corresponding reverse edge. Polygons must not have any duplicate edges (due to the requirement that polygon interiors are disjoint), but polylines may have duplicate edges or can even be self-intersecting.

Points and polyline edges are treated as multisets: if the same point or polyline edge appears multiple times in the input, it will appear multiple times in the output. For example, the union of a point with an identical point consists of two points. This feature is useful for modeling large sets of points or polylines as a single region while maintaining their distinct identities, even when the points or polylines intersect each other. It is also useful for reconstructing polylines that loop back on themselves. If duplicate geometry is not desired, it can be merged by GraphOptions::DuplicateEdges::MERGE in the S2Builder output layer.

Polylines are always considered to be directed. Polyline edges between the same pair of vertices are defined to intersect even if the two edges are in opposite directions. (Undirected polylines can be modeled by specifying GraphOptions::EdgeType::UNDIRECTED in the S2Builder output layer.)

The output of each operation is sent to an S2Builder::Layer provided by the client. This allows clients to build any representation of the geometry they choose. It also allows the client to do additional postprocessing of the output before building data structures; for example, the client can easily discard degeneracies or convert them to another data type.

The boundaries of polygons and polylines can be modeled as open, semi-open, or closed. Polyline boundaries are controlled by the PolylineModel class, whose options are as follows:

- In the OPEN model, polylines do not contain their first or last vertex.

- In the SEMI_OPEN model, polylines contain vertices except the last. Therefore if one polyline starts where another polyline stops, the two polylines do not intersect.

- In the CLOSED model, polylines contain all of their vertices.

When multiple polylines are present, they are processed independently and have no effect on each other. For example, in the OPEN boundary model the polyline ABC contains the vertex B, while set of polylines {AB, BC} does not. (If you want to treat the polylines as a union instead, with boundaries merged according to the "mod 2" rule, this can be achieved by reassembling the edges into maximal polylines using S2PolylineVectorLayer with EdgeType::UNDIRECTED, DuplicateEdges::MERGE, and PolylineType::WALK.)

Polygon boundaries are controlled by the PolygonModel class, which has the following options:

- In the OPEN model, polygons do not contain their vertices or edges. This implies that a polyline that follows the boundary of a polygon will not intersect it.

- In the SEMI_OPEN model, polygon point containment is defined such that if several polygons tile the region around a vertex, then exactly one of those polygons contains that vertex. Similarly polygons contain all of their edges, but none of their reversed edges. This implies that a polyline and polygon edge with the same endpoints intersect if and only if they are in the same direction. (This rule ensures that if a polyline is intersected with a polygon and its complement, the two resulting polylines do not have any edges in common.)

- In the CLOSED model, polygons contain all their vertices, edges, and reversed edges. This implies that a polyline that shares an edge (in either direction) with a polygon is defined to intersect it. Similarly, this is the only model where polygons that touch at a vertex or along an edge intersect.

Note that PolylineModel and PolygonModel are defined as separate classes in order to allow for possible future extensions.

Operations between geometry of different dimensions are defined as follows:

- For UNION, the higher-dimensional shape always wins. For example the union of a closed polygon A with a polyline B that coincides with the boundary of A consists only of the polygon A.

- For INTERSECTION, the lower-dimensional shape always wins. For example, the intersection of a closed polygon A with a point B that coincides with a vertex of A consists only of the point B.

- For DIFFERENCE, higher-dimensional shapes are not affected by subtracting lower-dimensional shapes. For example, subtracting a point or polyline from a polygon A yields the original polygon A. This rule exists because in general, it is impossible to represent the output using the specified boundary model(s). (Consider subtracting one vertex from a PolylineModel::CLOSED polyline, or subtracting one edge from a PolygonModel::CLOSED polygon.) If you want to perform operations like this, consider representing all boundaries explicitly (topological boundaries) using OPEN boundary models. Another option for polygons is to subtract a degenerate loop, which yields a polygon with a degenerate hole (see S2LaxPolygonShape).

Note that in the case of Precision::EXACT operations, the above remarks only apply to the output before snapping. Snapping may cause nearby distinct edges to become coincident, e.g. a polyline may become coincident with a polygon boundary. However also note that S2BooleanOperation is perfectly happy to accept such geometry as input.

Note the following differences between S2BooleanOperation and the similar S2MultiBooleanOperation class:

- S2BooleanOperation operates on exactly two regions at a time, whereas S2MultiBooleanOperation operates on any number of regions.

- S2BooleanOperation is potentially much faster when the input is already represented as S2ShapeIndexes. The algorithm is output sensitive and is often sublinear in the input size. This can be a big advantage if, say,

- S2BooleanOperation supports exact predicates and the corresponding exact operations (i.e., operations that are equivalent to computing the exact result and then snap rounding it).

- S2MultiBooleanOperation has better error guarantees when there are many regions, since it requires only one snapping operation for any number of input regions.

Example usage: S2ShapeIndex a, b; // Input geometry, e.g. containing polygons. S2Polygon polygon; // Output geometry. S2BooleanOperation::Options options; options.set_snap_function(snap_function); S2BooleanOperation op(S2BooleanOperation::OpType::INTERSECTION, absl::make_unique<S2PolygonLayer>(&polygon), options); S2Error error; if (!op.Build(a, b, &error)) { LOG(ERROR) << error; ... }

If the output includes objects of different dimensions, they can be assembled into different layers with code like this:

vector<S2Point> points; vector<unique_ptr<S2Polyline>> polylines; S2Polygon polygon; S2BooleanOperation op( S2BooleanOperation::OpType::UNION, absl::make_unique<s2builderutil::PointVectorLayer>(&points), absl::make_unique<s2builderutil::S2PolylineVectorLayer>(&polylines), absl::make_unique<S2PolygonLayer>(&polygon));