Subdivision Overlay and Polygon Boolean Operations

Subdivision Overlay and Polygon Boolean Operations

Polygon Boolean operations look like set algebra—keep points in \(A\), in \(B\), in both, or in exactly one—but a robust implementation is mostly about topology. The hard part is not choosing union versus intersection. It is turning two possibly complicated boundaries into one consistent planar subdivision whose faces can be classified without ambiguity.

That viewpoint gives us a reusable plan:

1. find every place the boundaries meet;
2. split edges so no surviving edge crosses another in its interior;
3. merge the pieces into a directed planar graph;
4. label each face by whether it lies inside each input;
5. select faces using a Boolean truth table; and
6. trace the boundary between selected and unselected faces.

The same overlay supports union, intersection, difference, and exclusive-or. Only the face-selection predicate changes.

From two boundaries to one subdivision

Suppose \(A\) and \(B\) are polygonal regions. Each may have several components and holes. Their input rings are oriented consistently—for example, outer boundaries counterclockwise and hole boundaries clockwise—but orientation alone does not resolve intersections.

The overlay refines both boundaries at every crossing, touch, shared endpoint, and overlap endpoint. After refinement, each atomic segment has a well-defined relationship to the surrounding faces. It either separates two different membership states or is redundant because both sides have the same state.

The marked vertices are more than drawing details. They are where cyclic edge order changes, so they determine the topology of the arrangement. Missing even one split can create an edge that passes through a vertex, corrupt face walks, and produce a plausible-looking but wrong polygon.

The overlay pipeline

1. Discover intersections

A quadratic all-pairs test is conceptually simple, but a sweep line reports \(k\) intersections among \(n\) input edges in \(O((n+k)\log n)\) time under standard assumptions. The event queue contains endpoints and discovered crossings; the sweep status orders edges near the current \(x\)-coordinate. Part 7’s sweep-line spotlight explains why only neighboring status edges can create the next event.

Do not report only proper crossings. The event model must distinguish:

• a transverse crossing;
• an endpoint touching another edge’s interior;
• coincident endpoints;
• collinear overlap, represented by the overlap’s endpoints; and
• a zero-length input edge, which should normally be removed during normalization.

For every original edge, collect its intersection parameters \(t\in[0,1]\), sort them, deduplicate them, and emit consecutive subsegments. Exact or consistently rounded parameters matter: two computations that refer to the same geometric point must produce the same vertex identity.

2. Split and merge edges

Once split, atomic edges intersect only at endpoints. Canonicalize vertices, then combine geometrically identical segments. A shared segment needs provenance from both inputs and direction information; simply retaining two coincident copies creates zero-width faces and ambiguous rotations.

Each undirected atomic segment becomes two half-edges. A half-edge stores at least:

• origin, twin, next, and prev;
• the face on its left;
• source and winding contributions from \(A\) and \(B\); and
• flags for coincident or input-boundary status.

At each vertex, sort outgoing half-edges by polar angle. The rotation order determines next: when walking a face with its interior on the left, continue along the appropriate edge adjacent to the incoming twin. This is the core of a doubly connected edge list, or DCEL.

3. Extract and label faces

Following next pointers partitions the half-edges into boundary cycles. Cycles alone are not yet faces: one face can have an outer component and several inner components, while the unbounded face can have multiple boundary components. Containment relationships among cycles assemble the actual face records.

Start with the unbounded face, whose state is outside both inputs. Then propagate labels across edges. Crossing a directed boundary changes a winding count according to that edge’s contribution. For the even–odd rule, only parity matters; for the nonzero rule, retain the signed count.

label(unbounded) = (wA = 0, wB = 0)
queue = [unbounded]

while queue not empty:
    face = queue.pop()
    for half_edge on boundary(face):
        other = face across half_edge
        candidate.wA = face.wA + crossing_delta_A(half_edge)
        candidate.wB = face.wB + crossing_delta_B(half_edge)
        assign or consistency-check candidate
        if newly assigned: queue.push(other)

Propagation avoids choosing a sample point for every face. Point-in-polygon sampling can still serve as a verification step, but it is awkward for very thin faces and points close to boundaries.

Boolean operations are face predicates

Convert each winding value to an inside bit using the chosen fill rule, then apply ordinary Boolean logic.

The output boundary consists precisely of half-edges with a selected face on one side and an unselected face on the other. Orient the retained edge so the result interior lies on its left, link compatible edges at vertices, and trace closed rings. This rule automatically removes internal seams from a union and keeps the appropriate reversed boundary of \(B\) in \(A\setminus B\).

def select(op, in_a, in_b):
    if op == "union":        return in_a or in_b
    if op == "intersection": return in_a and in_b
    if op == "difference":   return in_a and not in_b
    if op == "xor":          return in_a != in_b
    raise ValueError(op)

def result_half_edges(dcel, op):
    kept = []
    for e in dcel.half_edges:
        left = select(op, e.left_face.in_a, e.left_face.in_b)
        right = select(op, e.twin.left_face.in_a,
                           e.twin.left_face.in_b)
        if left and not right:       # result interior stays on the left
            kept.append(e)
    return trace_cycles(kept)

Holes, boundaries, and fill rules

A hole is not a special kind of edge. It is an unselected face enclosed by selected faces. Once face labels are correct, boundary extraction naturally yields an outer ring and inner rings. Ring orientation is then normalized for the output convention.

Boundary semantics still require an explicit policy. Closed-set polygon operations normally include boundary points, but a lower-dimensional contact—two polygons meeting only at a point or segment—may not appear in an area-polygon result. A geometry library might return mixed-dimensional objects instead. Document whether your API preserves such line and point remnants.

Fill rules answer a different question: what does a self-overlapping input mean?

• Even–odd: inside when the crossing count is odd.
• Nonzero winding: inside when the signed winding count is nonzero.

For simple rings they agree. For nested rings with the same orientation or self-overlapping paths they may disagree. Carry winding deltas through the overlay instead of prematurely reducing everything to a single inside bit; then the same arrangement can support either interpretation.

Coincident edges are a first-class case

Overlapping collinear boundaries are where many otherwise convincing implementations fail. Imagine two rectangles sharing a side. For union, the shared side is internal and disappears. For intersection, it contributes no area if the interiors lie on opposite sides, though it may be a valid line-valued intersection. For difference, whether it survives depends on which region lies on each side.

Resolve this from adjacent face states, not from an ad hoc rule such as “drop duplicate edges.” First split the full overlap into identical atomic segments, combine provenance and winding contributions, and let face labeling determine the states on both sides. The selected/unselected boundary test then makes the correct operation-specific choice.

Complexity and output sensitivity

Let \(n\) be the total number of input edges and \(k\) the number of reported intersection events. Sweep-line discovery and splitting take \(O((n+k)\log n)\) time in a typical output-sensitive implementation. The refined DCEL has \(O(n+k)\) size; sorting incident edges, constructing faces, propagating labels, and tracing the output add linear or local sorting costs. Finally, writing \(m\) result edges necessarily costs \(O(m)\).

Thus a useful high-level bound is \(O((n+k)\log n + m)\), with linear space in the arrangement size. Degenerate overlaps can complicate the precise definition of \(k\), so state whether it counts overlap intervals, their endpoints, or all emitted atomic pieces.

Robustness is part of the data structure

The DCEL demands combinatorial consistency: twins agree, next cycles close, every half-edge belongs to exactly one left face, and labels propagated around any cycle agree. Floating-point coordinates can violate those invariants even when the picture looks harmless.

Use robust orientation and segment-intersection predicates; construct intersection coordinates with exact arithmetic or a controlled precision model when possible. Never use a global epsilon as equality for arbitrary coordinates: it is not transitive, so it cannot safely define vertex identity. If snapping is required, make it an explicit preprocessing model with a known grid and validate the result afterward.

Useful postconditions include:

• no atomic edge contains another vertex in its open interior;
• outgoing edges have a strict, deterministic rotation order;
• every half-edge has exactly one twin;
• face walks close without repeating a half-edge early;
• neighboring face labels differ by the stored crossing delta; and
• extracted rings contain no unintended spikes or zero-length edges.

Property tests are especially effective: \(A\cup B=B\cup A\), \(A\cap A=A\), \(A\setminus A=\varnothing\), and \((A\triangle B)\triangle B=A\), modulo the library’s normalization and lower-dimensional policy.

Where Sutherland–Hodgman fits

The Sutherland–Hodgman spotlight is an elegant special-purpose alternative when clipping a polygon against a convex clip window. It processes one clip half-plane at a time and needs no full arrangement. That makes it compact and practical for graphics pipelines.

Its limitation is structural: a single evolving vertex list does not naturally represent arbitrary disconnected components, general nonconvex clip regions, coincident-boundary topology, or the complete family of symmetric Boolean operations. Use it when its convex-clip assumptions match the problem; use overlay when the topology itself is part of the answer.

From overlay to triangulation

Overlay leaves us with a validated planar subdivision: vertices, noncrossing edges, faces, holes, and cyclic boundary order. That is almost exactly the input Part 9 needs. Triangulation will refine selected faces into simple cells while preserving their boundaries. The emphasis shifts from which faces belong to the result? to how can each chosen face be decomposed efficiently? Robust predicates and consistent topology remain the foundation.