Module polygon_boolean 

Robust 2D boolean operations on simple polygons (union, intersection, difference).

Approach

Rather than weaving a doubly-linked list through coincident vertices (the classic Greiner–Hormann hazard), this implementation builds a planar arrangement and classifies directed sub-edges by their midpoints:

1. Every edge of A is split at all points where it meets B (proper crossings, vertex-on-edge T-junctions, and the endpoints of any collinear-overlap), and vice versa.
2. All split points are snapped to a tolerance grid so that points arising independently from A and B collapse to bit-identical coordinates. This is what eliminates sliver artifacts from near-coincident edges.
3. Each resulting sub-edge is classified by sampling its midpoint against the other polygon: Outside, Inside, or OnBoundary (with the relative direction of the shared boundary recorded).
4. Sub-edges are selected per the operation, then traced into closed loops by following snapped coordinates.
5. Loops are classified as outer (CCW) or hole (CW) by signed area and assembled into a PolygonBooleanResult.

Deciding inside/outside on a midpoint — a point in the relative interior of a sub-edge, away from the singular intersection vertices — is what makes the degenerate cases (collinear overlap, T-junctions, shared edges, corner touches) robust: the classification never has to disambiguate behaviour at a shared vertex.

Tolerance model

tol is an absolute linear tolerance in the polygons’ coordinate units. Two points within tol of each other are treated as identical (snapped to a shared grid cell of size tol); a point within tol of an edge is treated as lying on it; an edge pair whose overlap exceeds tol in length is treated as collinear-shared. Pass the same tol you use elsewhere for the geometry in question (e.g. Tolerance::default().linear, or a looser value for coarse data).

Structs

PolygonBooleanResult

The result of a polygon boolean operation.

Enums

BooleanOp

Which boolean operation to perform.

Functions

polygon_boolean

General boolean of two simple polygons.

polygon_union

Union of two simple polygons.

signed_area

Signed area via the shoelace formula. Positive for CCW, negative for CW.