Skip to content

DESIGN.md

Latest commit

 

History

History
807 lines (617 loc) · 66 KB

DESIGN.md

File metadata and controls

807 lines (617 loc) · 66 KB

polyclip — Polygon Boolean and Offset Library for Go

Module path: github.com/lestrrat-go/polyclip

A pure-Go library for 2D polygon boolean operations and offsetting. This document records the design decisions behind the library: the public surface and why it is shaped this way, the algorithm chosen and the alternatives rejected, and the design of the scanline engine internals (§11–§12) — chiefly the degenerate-case handling that is the bulk of the engine's complexity (§12.11). It is not a changelog or a status report; for current state, test it.

Section numbers in §4–§12 are stable: source comments reference them (e.g. DESIGN.md §12.11). Subsection anchors must not be renumbered.

1. Overview

A pure-Go library for 2D polygon operations:

  • Boolean ops on filled polygonal regions: union, intersection, difference, symmetric difference (XOR).
  • Polygon offset ("inflate" / "shrink"): inward and outward, with miter / round / square joins.
  • Robust handling of polygons with holes, self-intersections, coincident edges, and overlapping boundaries.

The shape primitive is a simple-polygon-with-holes (ExPolygon) and collections of them (MultiPolygon); every operation is closed over MultiPolygon.

The target workload is 3D-printer slicing, where nearly every quality feature needs reliable polygon arithmetic, and the Go ecosystem lacks a robust pure-Go library for it. The established C++ reference for this problem is Clipper2 (Angus Johnson), whose algorithm polyclip's engine is built on (§4.1).

Goals: correctness on adversarial input (concentric circles, self-touching polygons, collinear/coincident edges, near-degenerate slivers); pure Go (no cgo); closed (MultiPolygon in, MultiPolygon out); idiomatic small API; acceptable performance on slicer workloads.

Non-goals: 3D, curved geometry (NURBS / true arcs — arcs are polyline-approximated), cgo bindings to a native clipping library. The planar-polygon feature surface and the design choice behind each feature are in §7.8.

2. Module layout

github.com/lestrrat-go/polyclip
├── polyclip.go            package doc, top-level conveniences
├── boolean.go             Union, Intersect, Difference, Xor, UnionAll (public API)
├── offset.go              Offset, JoinType, EndType, OffsetOptions (public API)
├── offsetpaths.go         OffsetPaths — open-polyline ribbon offset with end caps
├── builder.go             Builder, Result, PolyTree, ZAssigner (advanced public API)
├── geom/                  geometry value types (subpackage, no engine dependency)
│   ├── point.go           Point, BBox
│   ├── polygon.go         Polygon, ExPolygon, MultiPolygon, Polyline; winding, area, contains, Clean
│   └── validate.go        Validate, IssueKind, ValidationIssue; structural diagnostics
├── internal/clip/         scanline boolean engine
│   ├── segment.go         fixed-point directed-edge type, source tag
│   ├── preprocess.go      snap, dedup, overlap/T-junction splitting
│   ├── bounds.go          local-minima / bound construction, ring tracing
│   ├── event.go           event queue
│   ├── ael.go             active edge list
│   ├── sweep.go           scanline loop, DoIntersections, closeBound, lifecycle
│   ├── classify.go        winding-count classification
│   ├── poly_ops.go        IntersectEdges dispatch
│   ├── output.go          OutPt / OutRec ring construction
│   ├── horizontal.go      horizontal classification
│   ├── horzjoin.go        deferred horizontal joins
│   └── invariants.go      post-condition checks
├── internal/fixed/        fixed-point arithmetic (coord.go, mul.go)
├── tools/differential/    Monte-Carlo differential harness (correctness oracle)
└── examples/               runnable, output-verified testable examples (package examples_test)

The internal/clip and internal/fixed packages hold the engine and are not importable outside the module. The geom subpackage holds the public geometry value types and carries no dependency on the engine; together with the top-level polyclip package (which holds the operations) it forms the stable public API.

3. Public API

The public surface is small; see the Go doc comments for full signatures.

  • Core types (package geom): geom.Point{X,Y float64}, geom.BBox, geom.Polygon []geom.Point (implicit closing edge; outer rings CCW, holes CW by convention but either is accepted and normalized), geom.ExPolygon{Outer, Holes}, geom.MultiPolygon []geom.ExPolygon, and geom.Polyline for open paths. These value types live in package geom; the operations below live in the top-level polyclip package and consume them.
  • Boolean ops (boolean.go): Union, Intersect, Difference, Xor — each (a, b geom.MultiPolygon) (geom.MultiPolygon, error); UnionAll(...geom.MultiPolygon) for tournament-reduced multi-union.
  • Offset (offset.go): Offset(m, d, opts) with OffsetOptions{Join, MiterLimit, ArcTol} and JoinType ∈ {miter, round, square}.
  • Geometry utilities (package geom): SignedArea, Area, IsCCW, Reverse, BoundingBox, Contains (even-odd, boundary inside); MultiPolygon.Clean(vertexTol, minArea); MultiPolygon.Validate() []ValidationIssue.
  • Shape builder (package geom): geom.New() returns a fluent *geom.Builder — Point/Point3 extend the current piece's outer ring, Hole(...Polygon) attaches holes (pre-built, literal, or a spread []Polygon), NextPiece starts a disjoint piece, and Build/MustBuild normalize winding and emit a MultiPolygon. Polygon/MustPolygon extract a fluently-built single ring (e.g. to pass to Hole).

error is returned only for caller-fixable problems (e.g. a bounding box too large for the fixed-point grid, §5.1, or an offset that collapses to empty). Validate() issues are diagnostics, not errors.

Open-polyline clipping is available via Builder.AddOpenSubject + Result.Open; open-polyline offset (ribbons with end caps) via OffsetPaths; caller-selectable fill rules (incl. even-odd) via Builder.Fill; nested-hierarchy output via Builder.ExecuteTree (PolyTree); Douglas–Peucker path reduction via SimplifyPaths; bevel joins via JoinBevel; Minkowski sum/difference via MinkowskiSum/MinkowskiDiff; fast axis-aligned rectangle clip via RectClip/RectClipLines.

4. Algorithm

4.1 Boolean engine: Vatti / Clipper2 model

The engine is a Vatti scanline modeled on Clipper2 (Angus Johnson, CPP/Clipper2Lib/src/clipper.engine.cpp); polyclip's sweep follows its algorithm and data model, and engine.cpp:line references throughout this document point into that source. See NOTICE for attribution.

Plain-English sketch:

  1. Input prep (§11.2): scale float64 input to a fixed-point integer grid (§5), split each polygon into directed edges tagged subject/clip, split overlaps and T-junctions.
  2. Local minima / bounds (§12.1): reframe each ring as alternating ascending/descending bounds meeting at local minima/maxima.
  3. Scanline sweep (§11.5, §12.10): maintain an active edge list (AEL) of edges crossing the current scanline; spawn bounds at local minima, advance cursors, close at maxima.
  4. Crossings (§12.11): per scanbeam, recompute all edge crossings from the settled AEL (DoIntersections) and dispatch each through IntersectEdges (§12.5).
  5. Classification (§11.4): each edge carries winding counts; the op + winding decides whether it bounds the result.
  6. Output (§11.6, §11.9): contributing edges build doubly-linked rings; postprocess assigns holes and normalizes winding.

4.2 Boolean engine: file map

  • clip/preprocess.go — scale/snap, dedup, overlap and T-junction splitting.
  • clip/bounds.go — BuildLocalMinima, bound construction, ring tracing.
  • clip/sweep.go — the scanline loop, DoIntersections, lifecycle (closeBound, cursor advance), degenerate-confluence handling.
  • clip/poly_ops.go — IntersectEdges dispatch table.
  • clip/classify.go — winding-count classification per op.
  • clip/output.go — OutPt/OutRec, AddLocalMinPoly/AddLocalMaxPoly/JoinOutrecPaths/SwapOutrecs.

4.3 Offset engine

Offset walks each input ring once and emits an offset ring directly, vertex by vertex. With n_i the right-hand unit normal of edge ring[i]→ring[i+1] and d the signed distance, each vertex v expands based on its local turn:

  1. a = v + d·prevN, c = v + d·nextN — offset endpoints of the prev/next edges at v.
  2. cross = prevN × nextN; the sign of cross·d classifies the corner:
    • Wedge (cross·d > 0): convex offset corner; emit a join (miter apex, square chamfer, or tessellated arc) per OffsetOptions.Join.
    • Overlap (cross·d ≤ 0): the offset edges cross; emit the miter apex (for antiparallel normals, fall back to emitting a and c).

Holes are offset by -d. The raw ring is emitted unconditionally — when an inward offset overshoots the inradius it self-intersects (a pinched neck, a closing notch, an inside-out collapse) rather than being rejected.

Topology resolution (§7.1). Per input ExPolygon, the raw offset rings (outer by d, holes by -d) are checked for self/mutual intersection (ringsIntersect). If none, topology is unchanged and the rings are returned directly (exact, no engine pass). If they intersect, the piece is re-resolved by a positive-fill self-union: feed the rings to the scanline engine (clip.SweepFill with clip.FillPositive), which keeps exactly the strictly-positively-wound region — the outer winds +1 inside, CW holes −1 — so a pinched ring splits into islands and the negatively-wound overshoot folds drop. An inward result piece is additionally validated against the erosion definition (insetDeepEnough: an interior point must be ≥ |d| from the input boundary), which rejects the convex "inside-out" collapse whose ring is simple and positively oriented yet sits where the offset is empty. If everything collapses, Offset returns an empty MultiPolygon with a nil error.

Degeneracy robustness. The sweep is exact on transversal self-intersections but resolves a snapped degenerate configuration (same-source collinear coincident edges from parallel walls a multiple of 2|d| apart, or a near-pinch crossing) differently — sometimes wrongly — per coordinate frame. Axis-aligned and thin-neck inward offsets hit this. So the self-union is run in several rotated frames (selfUnionResolveAngles) and the most-agreed-upon result (same piece count and area, within 2%) is kept; the correct resolution recurs across frames while each degenerate misresolution is scattered. Angle 0 (no rotation, exact coordinates) is preferred within the agreeing majority, so non-degenerate offsets keep exact output. (The boolean engine's own same-source coincident-edge gap is the deeper root cause; see §7.2.)

Direct ring construction (rather than Clipper2's "fat-edge polygons → union") avoids dense diff-source coincident-edge pile-ups and is O(n) for the common no-topology-change case; only intersecting pieces pay for the multi-frame self-union.

Implementation in offset.go: Offset (orchestration, hole sign, inset validation), offsetRing (per-ring walk), emitVertex (wedge/overlap dispatch), appendMiter/appendMiterApex/appendSquareJoin/appendRoundJoin, resolveOffsetPiece (fast path vs self-union), selfUnionPositive/selfUnionAt (multi-frame positive-fill resolution), ringsIntersect, insetDeepEnough.

4.4 Complexity

  • Boolean: O((n + k) log n), n = edges, k = intersections; the per-scanbeam DoIntersections is O(m²) per beam of m active edges (correctness-first; a merge-sort inversion counter is the later optimisation).
  • Offset: O(n) per ring plus O(n·m) for the inward-overshoot check (early-exits on the first failing vertex).

5. Numeric robustness

This separates a working library from a fragile one; treat it as load-bearing.

5.1 Fixed-point internal representation

User input is float64; the engine scales to int64 on a uniform grid: internalCoord = int64(round(userCoord * Scale)). Scale is chosen per-operation from the input bounding box so all intermediate products (intersection determinants are degree-2 in coordinates) stay in range (int128 synthesized from two int64s for the high-precision determinant). Output is descaled to float64.

Integer coordinates eliminate the most common Vatti failure: "the same point computed two ways gives slightly different float64s and breaks topology."

5.2 Robust segment intersection

Two segments cross per the signs of orientation determinants:

det(P, Q, R) = (Q.X - P.X)*(R.Y - P.Y) - (Q.Y - P.Y)*(R.X - P.X)

Computed exactly via the int128 helper in fixed/mul.go; never in float64. The intersection point needs division and may be computed in float64 / rounded to the grid — only the orientation predicates need full precision. (Reference: Shewchuk 1997; integer coordinates give exact orientation, so the simpler "exact integer predicates" approach suffices.)

5.3 Coincident edges

Collinear overlapping edges are split in preprocess so the sweep only ever sees fully coincident pairs (§11.7), then resolved by the winding rule and the coincident-horizontal handling in §12.11.

5.4 Vertices on edges (T-junctions)

A vertex of one polygon lying on an edge of another is exactly representable on the integer grid. SplitTJunctions (preprocess) splits the edge at that vertex up front, so the sweep never faces an ambiguous mid-edge vertex. This is the single most common Vatti bug source in implementations that skimp on §5.1.

5.5 Self-intersecting input

Self-intersecting input rings are accepted; Vatti's intersection step processes every crossing, including self-crossings. Output is always simple.

6. Testing strategy

The testing approach is itself a design decision, because the obvious oracle (Clipper2) is unusable on the degenerate small-integer inputs that matter most (§12.11). The strategy has four layers, each chosen for what the layer above cannot catch.

6.1 Unit and property layer

  • Unit tests alongside each source file cover the pieces in isolation: predicates, segment intersection, AEL/event-queue operations, ring assembly, per-join offset geometry.
  • Fuzzing (testing.F) checks random polygons against algebraic invariants that hold regardless of the concrete geometry — Union(A,A)=A, Difference(A,A)=∅, Xor(A,B)=Union(Diff(A,B),Diff(B,A)), and Area(A∪B)=Area(A)+Area(B)−Area(A∩B). (The fuzz corpus is gitignored, so it is a discovery tool, not a fixed gate.)

6.2 Adversarial cases and the differential oracle

  • Hand-built adversarial cases pin the configurations known to break Vatti implementations: overlapping squares, square-minus-square annulus, edge- and vertex-touching unions, the self-touching "8", concentric rings, T-junctions, and hole–clip confluences. Each asserts the relevant set identity within tolerance.
  • The differential harness (tools/differential) is the standing correctness oracle. It generates random and forced-degenerate input pairs and checks the noise-free set identities idU = U−(A+B−I), idD = D−(A−I), idX = X−(U−I) — which must be exactly zero — plus absolute areas against a Monte-Carlo area oracle. The MC oracle, not Clipper2, is the reference by deliberate choice: on degenerate small-integer inputs Clipper2 rounds fractional crossings to its native integer grid and is itself wrong on all four ops, whereas polyclip's finer fixed-point grid is more accurate (§12.11). Any engine change is gated on this harness staying at zero identity violation.

7. Feature-area design decisions

Beyond the core sweep (§11–§12), each feature area below records the design decision taken and why — including the limitations deliberately accepted and the alternatives rejected. The boolean engine targets the noise-free set identities (§6.2) across random, large, degenerate, and holed inputs at slicer-grade correctness; the choices here extend that surface toward a drop-in slicer geometry layer.

7.1 Offset: inward-offset topology changes

Offset re-resolves inward topology changes — a neck pinched into two islands, a notch that closes, an over-shrunk ring that collapses to empty — via the per-piece positive-fill self-union of §4.3, made robust by a rotated majority vote. The vote is needed because the sweep mis-resolves snapped same-source coincident edges (§7.2); the design accepts its cost (≈8 sweeps per topology-changing piece) because non-topology-change offsets keep the exact O(n) fast path and pay nothing.

7.2 Public Simplify and the in-sweep coincident-edge limit

Simplify(m) runs the engine over m as a single source (NonZero) to make rings simple: a figure-eight splits into its two oppositely-wound loops, a doubly-traced ring collapses to one, a doubled-back spur cancels. General-position self-intersections resolve exactly.

Known limit — exactly coincident same-source walls. A single ring with same-source collinear coincident walls (axis-aligned and thin-neck inward offsets produce them — the dumbbell offset by -2 traces one wall twice) is ambiguous to a single sweep: two parallel coincident walls never cross, so no event orders them and the winding prefix cannot tell the zero-width sliver from the boundary. The robust resolution for such exact degeneracies is perturbation, and the offset self-union's rotated majority vote (§7.1) is exactly that — so the vote is the intended design here, not a stopgap, barring a future symbolic- perturbation (Simulation-of-Simplicity) scheme that breaks ties in one sweep. The offset path runs its self-union on the ordered-minima engine (clip/sweep_ordered.go SweepRingsFill, which builds minima in traversal order so the two wall passes occupy distinct positions); under AEL.Ordered the dispatch keys on the Contributing boundary flag so a positive-fill WindSelf==0 sliver is not dropped. All gated on fill rule / AEL.Ordered, so the boolean NonZero path is untouched. See docs/offset-coincidence-perturbation.md.

7.3 Performance

Performance is correctness-first but two algorithmic choices keep the slicer workload (disjoint contours, big circles, brick walls, meshing gears) off the naive quadratic path:

  • Preprocessing (SplitOverlaps/SplitTJunctions) is a single batch pass each — bucket by exact supporting line, then cut each segment at interior vertices via an X-sorted vertex index — rather than O(n²) pair scans. This is what makes sparse/disjoint/axis-aligned inputs (the common slicer-layer case) cheap.
  • Per-scanbeam crossing enumeration (buildIntersectList) is a merge-sort inversion counter (O(n log n + k)): a beam crossing inverts the pair's X-order between beam bottom and top, so crossings are the inversions between the two orderings. Edge ordering uses exact 128-bit rational X-intercept comparison (fixed.CmpRationals), not float XAtY — at the grid extremes a float intercept carries enough rounding error to mis-order and drop a crossing. This is what keeps dense mutually-intersecting inputs (meshing gears) tractable.

Acknowledged gap: there is no standing benchmark suite, so absolute throughput is uncharacterized.

7.4 Open-path offset (EndType)

Open polylines are offset into ribbons via OffsetPaths (§7.8c). EndType selects the cap: EndButt/EndSquare/EndRound open-path caps, EndJoined (closed-loop band), or EndPolygon (the closed Offset behaviour). This serves the slicer's thin-wall / gap-fill / single-extrusion features.

7.5 Reachable ErrHorizontalNotSupported

The legacy per-edge fallback returns ErrHorizontalNotSupported only when BuildLocalMinima fails AND the fallback's ClassifyHorizontals then meets a staircase (mid-bound) horizontal. Historically this was readily hit on non-simple axis-aligned input — a polygon and its hole (or two offset/slicer loops) snapping onto one grid point makes a degree-4 self-touching vertex that the old traceRing could not reconstruct, dropping the engine onto the staircase-rejecting fallback (~32 % of ops on some real slicer layers).

BuildLocalMinima now decomposes self-touching rings (§12.10.7): such a vertex pinch reconstructs into its simple loops, which the bound model handles natively (including their mid-bound horizontals), so this case no longer errors. The error remains reachable only for genuinely open / broken input chains (reconstruction cannot close a ring) that also carry a mid-bound horizontal, so it stays part of the contract and callers should handle it — but well-formed closed input, even self-touching or self-intersecting, no longer hits it.

7.6 Axis-aligned identity violations (collinear shared edge)

Distinct from §7.5 (this surfaces after the fallback succeeds, on inputs the bound model handles). Axis-aligned pairs sharing a collinear boundary — dominated by a coincident cross-source vertical wall (one polygon's wall lies exactly on the other's, overlapping in Y) — produce algebraic-identity violations (a spurious half-area lobe, or a whole-region miscount) unless the engine resolves them specially. The design resolves them in two layers:

  • Sweep level. Two exactly-coincident AEL edges tie on CurrX and slope, so they are ordered by where their bounds first diverge just above the scanline (coincidentDivergeLess, 128-bit cross product), not an arbitrary slope tie — this fixes which wall carries WindOther and hence contributes. At a coincident apex, closeBound decides whether a ring continues above from the winding strictly above the scanline (opMember / otherSourceWindingAbove), closing at the seam via AddLocalMaxPoly when nothing resumes; a hot maxima edge with a cold same-source partner emits its apex so the vertex is kept.
  • Result level. A runBooleanOp subset-invariant filter drops a hole-free piece whose interior point violates Difference ⊆ A / Intersect ⊆ A∩B (point-in-polygon) — catching any residual over-trace where a maxing bound fails to update an exiting neighbour's winding. Never drops a valid piece.

Xor is computed by composition Difference(Union(a,b), Intersect(a,b)) rather than a direct OpXor sweep: the direct sweep mis-resolves a residual confluence class that U/I/D handle correctly, so the public API routes around it. Retiring both masks — letting OpXor and the result-level filter resolve in-sweep via a per-segment winding model at confluences — is the eventual goal but not the current design.

7.7 Multipiece-subject Difference

A multipiece subject (one source contributing several disjoint rings) hits the same coincident cross-source over-trace as §7.6, but with a second piece present the spurious trace merges with a valid ring, so the §7.6 subset filter cannot drop it. The design therefore differences a multipiece subject per piece — (∪ᵢ Pᵢ) ∖ B = ∪ᵢ (Pᵢ ∖ B), exact because a valid MultiPolygon's pieces are disjoint (results disjoint, union is plain concatenation). Each Pᵢ ∖ B runs the clean single-subject path, where the over-trace becomes a stray hole-free lobe the subset filter drops; pieces clear of B short-circuit on bbox. Intersect, Union, and Xor need no such decomposition — only Difference is asymmetric in its subject. The single-pass in-sweep resolution that would remove the need is the same deferred rework as §7.6.

7.8 Planar feature surface

The guiding design principle: each feature beyond the core boolean ops should be additive — layered over the existing sweep, the containment forest (§11.9), or Union — so the core engine stays untouched. The map of features to where each one's design is recorded:

Feature Where / how
Builder accumulator API (0)
Boolean ops (∪ ∩ − ⊕) §4, §11–§12
Polygon offset, closed §4.3
Join Miter / Round / Square §4.3
Join Bevel (a)
Fill rules incl. EvenOdd (b)
Open-path clipping (c)
Open-path offset (end caps) (c) / §7.4
Nested PolyTree output (d)
Minkowski sum / difference (e)
RectClip / RectClipLines (f)
Path reduction (Douglas–Peucker) (g)
Z-coords / vertex callback (h)
Triangulation (i)

The additive principle holds across the board with one deliberate exception: Z-coords (h) touches the engine, and only minimally — a recording hook in the AEL behind an off-by-default flag. Open-path clipping (c) was expected to need engine changes too but is designed as a standalone post-sweep pass instead.

(0) Builder accumulator API. The entry point the other features build on: New().AddSubject(…).AddClip(…).Execute(op) returning Result{Closed, Open}, with a root-package Operation (OpUnion/OpIntersect/OpDifference/OpXor). The accumulator is the general path; the named free functions (Union/Intersect/Difference/Xor) are thin wrappers over the unexported execOp — the single home for the per-op short-circuits, Xor-by-composition (§7.6), and per-piece Difference (§7.7), so those decisions live in exactly one place. Execute is non-destructive; Reset clears the inputs for reuse.

(a) Bevel join. JoinBevel joins by emitting the straight chord between the two offset-edge endpoints a, c at a convex corner (no apex, no miter-limit fallback) — a flat chamfer that cuts the corner. It is distinct from JoinSquare, which extends each endpoint outward by |d|; keeping both matches Clipper2's distinction.

(b) Caller-selectable fill rules. Exposed at the root as FillRule (NonZero default, plus EvenOdd / Positive / Negative) selected via Builder.Fill(r); the named free functions stay NonZero. Under EvenOdd, Classify/isContributing skip the source-boundary winding-magnitude test (every edge is a boundary) and count the other source's membership by crossing parity (WindOther toggles 0↔1) rather than a signed sum; IntersectEdges swaps WindSelf and toggles WindOther on a crossing — a direct transcription of Clipper2's EvenOdd branches. The key design choice is that a non-NonZero fill routes through execOpFilled, which drops the identity/disjoint/per-piece short-circuits: those assume well-formed, simply-wound inputs, but a non-NonZero fill is chosen precisely to re-resolve self-overlapping input (e.g. Union(s,∅) must re-fill s, not return it verbatim). Only fill-independent empty results short-circuit, and Xor stays a composition. Accepted limitation: a non-NonZero Difference over a multipiece subject runs one sweep (no per-piece decomposition, §7.7), so it can hit the coincident-confluence over-trace.

(c) Open paths — clipping and offset. Reverses the former §1/§3/§7.4 non-goal. Open paths are subjects only — a clip region must be closed, matching Clipper2.

  • Type: Polyline []Point alongside Polygon; a result carries both a closed MultiPolygon and []Polyline.
  • Clipping: designed as a standalone post-sweep pass, not the in-sweep tagged-edge approach Clipper2 uses, so the engine stays untouched. Builder.AddOpenSubject accumulates open subjects; Execute clips them into Result.Open. Each open segment is split at every crossing of a relevant closed boundary ring (by segment/edge intersection), and each sub-segment is kept iff its midpoint satisfies the op's keep predicate — a direct port of Clipper2's IsContributingOpen: Intersect keeps points inside the clip region; Difference and Xor keep points outside it (an open path has no area, so ⊕ reduces to −); Union keeps points outside both the subject and clip regions. Membership is the filled-region test (MultiPolygon.Contains). Survivors are stitched into chains, breaking at each dropped sub-segment. Open paths never clip one another.
  • Offset (§7.4): OffsetPaths(lines, d, opts) offsets a polyline into a closed ribbon, |d| to each side, capped per opts.End (EndButt flush / EndSquare extended |d| / EndRound semicircle). The ribbon is built as one closed ring — start cap, forward-side interior joins, end cap, reverse-side joins — traced CCW so the existing positive-fill self-union (§4.3) resolves the self-overlap of sharp interior turns and overlapping ribbons. This reuses the Offset join emitters and resolveOffsetPiece unchanged; the only new geometry is emitEndCap (a transcription of Clipper2's DoBevel/DoSquare/DoRound endpoint case). EndPolygon is rejected (ErrOffsetEndType). EndJoined closes each path into a loop (implicit last→first edge) and bands it ±|d| via offsetJoinedBand: the loop offset outward by |d| is the outer ring, offset inward by |d| and reversed is the hole; resolveOffsetPiece yields an annulus when the loop encloses more than 2|d|, a solid ribbon otherwise. A sub-3-vertex loop falls back to the capped ribbon. Mirrors Clipper2's EndType::Joined.

(d) Nested PolyTree output. Root PolyTree{Children} / PolyTreeNode{Polygon; IsHole; Children} plus Builder.ExecuteTree(op). The design choice is to not thread tree assembly through the sweep: ExecuteTree runs the same execOp as Execute (reusing every path — short-circuits, Xor composition, per-piece Difference, alternate fills) and rebuilds the containment forest (§11.9) over the finished MultiPolygon's rings to recover the depth-≥2 nesting a flat MultiPolygon discards (an island inside a hole is a top-level piece in the flat form, a depth-2 child in the tree). The forest logic is shared with assembleResult (classifiedRing/buildContainmentForest/ringDepth). IsHole = odd depth; winding normalized as elsewhere (filled CCW, hole CW). The correctness contract: the tree flattened (filled nodes → ExPolygon with their hole-children, islands promoted) equals the flat Result.Closed.

(e) Minkowski sum / difference. MinkowskiSum(pattern, path, closed) emits, for each consecutive pair of path vertices, the quadrilateral strip between the two pattern placements (normalized to positive winding) and unions all the strips with UnionAll under the non-zero rule; MinkowskiDiff reflects the pattern through the origin (path[i] - pattern[k]). closed strips between the last and first vertices as well. A faithful port of Clipper2's Minkowski/MinkowskiSum/MinkowskiDiff, built entirely on the existing Union so it needs no engine change.

(f) RectClip / RectClipLines. RectClip(m, rect) clips closed rings against an axis-aligned BBox by Sutherland–Hodgman (four half-plane passes), O(n) per ring and independent of the sweep — a deliberate fast path for the common "clip a layer to the build plate" case rather than routing through Intersect. Each ExPolygon is clipped independently (outer and every hole), so the hole structure is preserved without rebuilding the containment forest: a hole stays nested because both rings are clipped by the same rectangle. The enclosed region equals Intersect(m, rectAsPolygon). One accepted representational difference: where the rectangle splits a concave ring into disjoint pieces, Sutherland–Hodgman returns one ring joined by a zero-width seam along the rectangle edge rather than separate ExPolygon values (same area; run Simplify for clean separation). RectClipLines(lines, rect) clips open polylines by Liang–Barsky per segment, stitching contiguous inside runs back into one polyline and splitting at each re-entry; no seam is introduced since open paths carry no interior. Both are errorless (the clip cannot fail) and treat an empty rect as producing no output.

(g) Path reduction. SimplifyPaths(m, epsilon) reduces each ring's vertex count via a faithful port of Clipper2's SimplifyPath (a Douglas–Peucker-family algorithm): every vertex's perpendicular distance to the line through its retained neighbours is tracked, and vertices within epsilon are removed smaller-deviation-first so collinear/near-collinear runs collapse cleanly; each ring is treated as closed. Matching Clipper2's iterative remove-by-perpendicular-distance (rather than classic recursive RDP) is a deliberate choice to keep a caller porting from Clipper2 byte-for-byte compatible. Distinct from Simplify (self-intersection resolution) and Clean (collinear/tiny removal); named to avoid the clash. A negative epsilon is treated as zero; rings with <4 vertices pass through; a ring reduced below 3 vertices is dropped (and an ExPolygon whose outer ring is dropped is omitted). Standalone, no engine.

(h) Z-coordinates / vertex callback. Clipper2's compile-time USINGZ, re-cast as a runtime opt-in so the standard path pays nothing. Point gains a third field Z float64; the engine ignores it (every comparison and the fixed-point snap are X/Y-only), so it is pure auxiliary data carried input→output. A ZAssigner interface (AssignZ(e1bot, e1top, e2bot, e2top, crossing Point) float64, the analog of Clipper2's ZCallback) is installed via Builder.SetZAssigner; nil disables tracking (the default), leaving the standard path bit-for-bit identical and allocation-free.

Wiring: a zTracker (assigner + a map[fixed.Point]float64 keyed by snapped grid point) is threaded through execOp/runBooleanOp — nil on the Z-free path. appendRing records each input vertex's Z under its grid point; the sweep, run via clip.SweepFillZ, records every crossing IntersectEdges dispatches as a clip.ZCrossing (four endpoints + crossing point) behind the AEL's off-by-default RecordCrossings flag. runBooleanOp maps each crossing through the assigner — input vertices take precedence, so a meeting at an existing vertex keeps that vertex's Z — and assembleResult reads the table when unsnapping each output vertex. Composition propagates naturally: Xor and per-piece Difference recurse with the same assigner, and intermediate results already carry Z, so the next sub-op sees it as input Z. Z applies to Result.Closed only; open-path output is rebuilt by interpolation and carries no Z. Consequence to note: adding the field is a (pre-1.0) breaking change to positional Point{x, y} / Polygon{{x,y},…} literals — use keyed fields.

(i) Triangulation. Triangulate(MultiPolygon) []Triangle is a standalone implementation of the ear-clipping algorithm with hole elimination popularized by mapbox/earcut (ISC-licensed): a doubly-linked-list ear clip, hole bridging via findHoleBridge/splitPolygon, and the full robustness ladder (filterPoints → cureLocalIntersections → splitEarcut) so weakly-simple bridged polygons triangulate correctly. The z-order hashing (a pure performance optimization) is omitted, leaving an O(n²) ear test — an accepted cost under the correctness-first priority. Output is CCW, uses only the input's own vertices (no Steiner points), and drops zero-area triangles. Correctness is checked by an area-conservation oracle (summed triangle area == region area catches both overlap and gaps). Input must be well-formed (the form Simplify produces); degenerate or self-touching geometry should be passed through Simplify first.

7.9 Open items to revisit

The planar feature surface is complete (§7.8) and the differential oracle holds at zero identity violation (§6.2). What remains is quality, not coverage — each item below is correct as shipped but is a deliberate shortcut over the ideal single-pass engine, or an unverified goal. Recorded here as one list so the remaining work is findable; the rationale lives in the cross-referenced section.

  1. Native single-pass Xor (§7.6). Xor is computed by composition Difference(Union(a,b), Intersect(a,b)) — three sweeps, not one — because the direct OpXor sweep mis-resolves a residual confluence class. Resolving Xor in-sweep (per-segment winding at confluences, retiring both the composition and the result-level subset filter) is the eventual design.
  2. Single-pass multipiece Difference (§7.7). A multipiece subject is differenced per piece ((∪ᵢ Pᵢ)∖B = ∪ᵢ(Pᵢ∖B)) to dodge the same coincident over-trace — exact, but N sweeps. Removing the decomposition is the same rework as item 1.
  3. Non-NonZero-fill Difference over a multipiece subject (§7.8(b)). Routes through execOpFilled, which drops the per-piece decomposition of item 2, so it runs one sweep and can hit the coincident-confluence over-trace. Closing items 1–2 closes this.
  4. Performance unmeasured (§7.3). There is no standing benchmark suite, so absolute throughput is uncharacterized. Triangulation is additionally O(n²) (z-order hashing omitted by choice, §7.8(i)). Needs a benchmark harness.
  5. Representational rough edges. RectClip returns a single ring joined by a zero-width seam where a rectangle bisects a concave ring, rather than separate ExPolygon values (same area; Simplify separates them — §7.8(f)). Triangulate requires well-formed input and should be preceded by Simplify (§7.8(i)).

7.10 Refactoring backlog (review 2026-05)

Findings from a perf/UX-focused review of the shipped code. Each is a refactor, not a bug — current behaviour is correct. Ordered by impact. Profiled on BenchmarkUnionManyPieces (400 disjoint output rings) and BrickWallLarge.

Performance

  1. buildContainmentForest X-interval broad phase — DONE. Was O(n²) and the dominant non-sweep cost (12% of total runtime, effectively all of assembleResult on the many-pieces workload): every output ring matched against every other (canContainRing + ringContains) even when the output is fully disjoint (the common slicer case: many islands, no nesting). It is a stabbing query — for each ring's interior point, which other ring bboxes contain it, and of those the smallest-area poly.Contains. Now resolved by the low-risk broad phase without touching nesting semantics: ring indices are sorted by Min.X, each query binary-searches the Min.X ≤ query.X prefix and filters Max.X ≥ query.X, then runs the unchanged canContainRing / ringContains / smallest-area selection over only that window. The candidate set is a sound superset (any real container's X-interval covers the query point), so output is byte-identical; the differential oracle and fuzz corpus confirm. BenchmarkUnionManyPieces −14.5% (13.7→11.7 ms); BrickWallLarge unchanged (sweep-dominated). Worst case (every X-interval overlaps) is still O(n²); an interval tree would make it O(n log n + k) but was judged unjustified at nhundreds. Complemented the existing interiorPoint hoist into classifiedRing; see §7.3 and §7.9 item 4.
  2. Preprocessing reallocates and re-maps three times (sweepSegments, boolean.go). Partly addressed. The within-call churn is fixed: the three passes now share "append into dst" cores driven by clip.Preprocess, which ping-pongs two reusable []Segment buffers across SplitOverlaps → SplitTJunctions → DedupCoincidentEdges instead of allocating one per pass, and the per-segment seen := map[fixed.Point]struct{}{} inside the overlap splitter is replaced by a slices.Contains scan over the (tiny) cut list. Overlap-heavy inputs drop ~20% allocs/op (BrickWall benchmarks) with no behavioural change (differential byte-identical). Remaining: cross-call reuse — pooling the scratch buffers and the per-call byLine/groups maps across the many sweepSegments calls in UnionAll/Offset/Simplify — needs a scratch struct threaded through Builder → runBooleanOp; deferred as the larger, riskier step.

UX / API consistency

  1. Simplify vs SimplifyPaths name collision. Unrelated operations — Simplify resolves self-intersection via the engine; SimplifyPaths is Douglas–Peucker vertex decimation. The names give no hint which is which. Pre-1.0: consider renaming SimplifyPaths (e.g. ReducePaths/Decimate), or lead each doc with an explicit "not the other one" line.

  2. Result aliasing footgun in the boolean short-circuits (execOp, boolean.go). Union(a,empty) returns the caller's own a slice (the disjoint-bbox path splices inputs), so mutating the result mutates the input. The code already knows this — buildPolyTree copies defensively with the comment that short-circuits "can return the caller's own polygons, which Reverse must not mutate". Document on the public functions, or return a shallow copy.

  3. Minor type asymmetry. MinkowskiSum/MinkowskiDiff take path []Point while OffsetPaths takes []Polyline, and Polyline is []Point. Typing the path parameter as Polyline would make the open-path intent explicit.

    (Verified non-issue: RectClip/RectClipLines/SimplifyPaths/Clean/ Triangulate return no error, but each is genuinely sweep-free/geometric — principled, not an oversight.)

8. Conventions and constraints

  • Go version: 1.22+. Concrete types in the engine; generics only where they pay.
  • Dependencies: zero external modules — standard library only. Non-negotiable; the point is to be a clean leaf dependency.
  • Concurrency: the public API is safe for concurrent use on different inputs. A MultiPolygon value is not synchronized (same rule as []int). No internal parallelism in the library itself.
  • Style: gofmt/go vet/staticcheck clean; errors wrap fmt.Errorf("polyclip: …: %w", …); public symbols have doc comments; no package-global mutable state; no working init().
  • Pitfalls that look tempting but are wrong: float64 coordinates in the sweep (breaks topology, §5.1); Greiner-Hormann (can't handle coincident edges); offset via miter math without an engine (the naive approach this library replaces).

9. References

  1. Vatti, B. R. (1992). A Generic Solution to Polygon Clipping. CACM 35(7), 56–63.
  2. Johnson, A. Clipper2. https://github.com/AngusJohnson/Clipper2 — BSL-1.0; the sweep engine's algorithm and data model derive from it (see NOTICE).
  3. Shewchuk, J. R. (1997). Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates. DCG 18(3), 305–363.
  4. Martínez, F., Rueda, A. J., Feito, F. R. (2009). A new algorithm for computing Boolean operations on polygons. (Rejected alternative.)

11. Sweep engine: pipeline, data model, output

11.1 Pipeline

MultiPolygon (subject, clip; float64)
        │  preprocess (§11.2)
[]Segment  (fixed-point, source-tagged; overlaps & T-junctions split)
        │  sweep (§11.5, §12)
OutRec rings (doubly-linked, closed)
        │  postprocess (§11.9)
MultiPolygon (fixed-point → float64)

Each stage lives in its own file and does not know the next stage's internals.

11.2 Preprocess (clip/preprocess.go, boolean.go appendRing)

  1. Compute the union bbox of subject+clip; build one fixed.Scale (§5.1).
  2. Per ring, snap each vertex and emit a Segment per edge, tagged subject/clip. Normalize orientation (CCW outer / CW hole) by reversing a ring whose signed area disagrees, so the engine's "WindDx from traversal direction" assumption holds for any input winding.
  3. Drop degenerate segments; simplifyCollinearRing removes collinear-through input vertices (an exact no-op that removes spurious bound turns).
  4. SplitOverlaps — establishes "no partial collinear overlaps" (only fully coincident pairs remain).
  5. SplitTJunctions — establishes "no vertex lies in the open interior of any edge" (§5.4). Split points are existing grid vertices, so area-preserving.
  6. DedupCoincidentEdges — resolves same-source coincident pairs (§11.7).

11.3 Sweep state: the ActiveEdge

An ActiveEdge carries (see §12.2 for the full struct):

  • WindSelf — signed winding count of this edge's source up to and including this edge.
  • WindOther — signed winding count of the other source to the left (exclusive).
  • WindDx — signed input-traversal direction, ±1, set once at spawn and shared by every segment of the bound (including horizontals). Classify uses WindDx as the contribution; this is what lets a horizontal carry its bound's contribution while in the AEL.
  • Contributing — whether this edge bounds the result (set by Classify).
  • Outrec — non-nil iff the edge is "hot" (building a ring).

Winding is computed at spawn from the left neighbour and updated in place at each crossing by IntersectEdges (§12.5) — no left-walk recompute.

11.4 Classification table

An edge contributes iff inside(left) ≠ inside(right), where inside(side) = inside_subject(side) OP inside_clip(side). The other source's count is identical on both sides (only this edge's source flips across it), so:

Op Contributes iff
Union WindOther == 0 AND self-count flips across the edge
Intersect WindOther != 0 AND self-count flips
Difference subject edge: WindOther == 0 AND flip; clip edge: WindOther != 0 AND flip
Xor self-count flips (every boundary flip contributes)

Classify (clip/classify.go) transcribes Clipper2's SetWindCountForClosedPathEdge (NonZero rule); isContributing is IsContributingClosed.

11.5 The scanline loop

sweep.run() processes events in (Y, X, Kind) order. Per scanline it: resolves all crossings strictly inside the scanbeam from the settled AEL (DoIntersections, §12.11), spawns bounds at local minima, advances/closes bounds at Tops (§12.10), flushes horizontals (§12.6), and reconciles at-vertex crossings. The crossing model is per-scanbeam recompute, not incremental scheduling (§12.11). Ring construction (AddLocalMinPoly/AddLocalMaxPoly/AddOutPt/SwapOutrecs, §12.3–§12.5) happens inside the crossing and close handlers.

11.6 Output ring data structure

type OutPt struct { P fixed.Point; Next, Prev *OutPt; Outrec *OutRec }
type OutRec struct {
    FrontEdge, BackEdge *ActiveEdge // the two edges currently building the ring
    Pts                 *OutPt      // one vertex of the cycle; nil when merged away
    fromInputMin        bool        // spawned at an input local min vs a crossing (§12.11)
    // … Owner/IsHole set by postprocess
}

FrontEdge contributes to the head of the chain (prepend), BackEdge to the tail (append). Both are nil once the ring closes. Two contributing edges of the same ring just emit points on their respective ends; two edges of different rings meeting are spliced by JoinOutrecPaths.

11.7 Coincident edges

After §11.2, the only collinear pairs the sweep sees share both endpoints:

  • Same source, same direction (duplicate) — dropped in preprocess.
  • Same source, opposite direction — cancel; dropped.
  • Different source — handled by the coincident-horizontal rules in §12.11 (a doubled/cancelling boundary skips the transversal-crossing dispatch and is reconnected by the horizontal-join pass), and by the winding rule for sloped coincident pairs.

The bound model places each source's leading horizontal in a separate bound; the at-vertex and coincident-horizontal handling in §12.11 (reconcileSharedVertexCrossings, dispatchIntersect's opposite-interior skip, processHorzJoins) recovers the correct topology. Union(A, A) and analogues — where every edge becomes a same-vertex diff-source coincident pair — are short-circuited at the API level (boolean.go mpolyEqual).

11.8 Horizontal segments

A horizontal has Bot.Y == Top.Y. In the bound model a horizontal is a first-class AEL member carrying its bound's WindDx (§12.6.1), processed by the DoHorizontal pass (§12.6) after the Top events at its scanline. Event ordering at one (Y, X) is Top < Bot/LocalMin < Horiz < Intersection: closing edges leave first, new bounds enter, horizontals then walk the settled AEL. Coincident horizontals are pre-split (§11.2) so the pass never sees partial overlaps.

11.9 Postprocess (clip/bounds.go ring tracing, assembleResult)

After the sweep, each closed OutRec becomes a Polygon (walk the cycle, dedup consecutive equal points). Hole nesting is computed by a containment forest over all output rings (any orientation), classifying each ring by depth parity: even depth = a filled region (ExPolygon outer), odd depth = a hole of its (even-depth) parent. The sweep's own CW/CCW orientation is used only to normalize the final winding (filled→CCW, hole→CW), never to classify — an island inside a hole is CCW yet at depth 2 and must become its own top-level piece.

Containment is sampled at a genuine interior point (interiorPoint: midpoint of the widest interior span on a scanline that grazes no vertex and runs along no horizontal edge), not a vertex centroid — a centroid on a shared/collinear edge would test boundary-inclusive Contains as inside and falsely nest touching rings. Only a strictly larger ring can be a container, except that two equal-area coincident rings (the same boundary emitted once CCW and once CW, as Difference/Xor of identical inputs produce) break the tie by orientation and cancel to zero area. Finally, fixed-point coordinates are unsnapped to float64.

11.10 Invariants

Checked as post-conditions by clip.CheckInvariants (from clip/invariants_test.go):

  1. AEL ordering: after each event the AEL is sorted left-to-right by CurrX (slope tie-break). (clip.CheckAELSorted.)
  2. WindSelf bounded by the number of input rings of that source.
  3. Ring cycles well-formed: every closed ring's Next/Prev links round-trip and OutPt back-pointers are consistent.
  4. Rings close or retire: at sweep end every OutRec.Pts is either a closed cycle or nil (retired via JoinOutrecPaths); no partially-open rings.

12. Sweep engine: bounds, dispatch, horizontals, degeneracies

This chapter distills the parts of the algorithm translated from Clipper2 (CPP/Clipper2Lib/src/clipper.engine.cpp; engine.cpp:line references point into that tree). See NOTICE for attribution.

12.1 Bounds and local minima

Each input polygon is reframed as alternating ascending and descending bounds — chains of edges monotonic in Y. A local minimum is where a descending bound meets an ascending one (the ring turns from down to up); a local maximum is the inverse. A bound is a single AEL entry that advances through its edges via in-place cursor advance (§12.10.4), rather than one event per edge.

BuildLocalMinima (clip/bounds.go) walks each ring, finds every Y-direction reversal (horizontals count toward their non-horizontal neighbours' direction), and emits a LocalMinima record with its two emerging bounds, sorted by Y-ascending (X for ties) — the event processing order. polyclip is non-polytree: hole nesting is recomputed in postprocess (§11.9), open paths are out of scope, and the boolean fill rules over this path are NonZero and EvenOdd (Positive/Negative use the ordered-minima self-union, §7.2).

12.2 ActiveEdge / OutRec fields

ActiveEdge (mirroring Clipper2's Active) carries: Bound + EdgeIdx cursor (geometric, set once at spawn, never reassigned); CurrX; WindSelf/WindOther/WindDx (§11.3); Contributing; Outrec (logical — non-nil iff hot, changes at crossings). Key invariant: Bound is geometric, Outrec is logical — cursor advance consults only Bound/EdgeIdx and never touches Outrec.

OutRec carries FrontEdge/BackEdge (§11.6). IsFront(e) ≡ e.Outrec.FrontEdge == e; many IntersectEdges/AddLocalMaxPoly decisions branch on it.

12.3 AddLocalMinPoly (engine.cpp:1332)

Called when two AEL edges become the two sides of a new contributing ring. Allocates an OutRec, assigns both edges to it, and decides which is FrontEdge/BackEdge from the nearest prior hot edge and the isNew flag (true for a real input minimum, false for a synthetic minimum created by a crossing). fromInputMin is recorded from isNew (used by §12.11's figure-8 discriminator).

Convention note: polyclip's FrontEdge is the RIGHT/descending side (the mirror of Clipper2's "front = leftmost"), so its Pts cycle reads CCW. Callers pass (rightAE, leftAE); downstream code depends only on the FrontEdge/BackEdge identity, and postprocess (§11.9) determines orientation independently from signed area.

12.4 AddLocalMaxPoly & JoinOutrecPaths (engine.cpp:1380, 1435)

Called when two edges meeting at a local maximum close (or merge) their ring(s). If both belong to the same OutRec, the ring closes and both edges uncouple. If they belong to different OutRecs, JoinOutrecPaths splices the two doubly-linked chains into one and discards the second. The same-side (both-front / both-back) cases are the figure-8 and reverse-join handling described in §12.11.

12.5 IntersectEdges dispatch (engine.cpp:1772)

The heart of the engine (clip/poly_ops.go). At a crossing of two adjacent AEL edges it updates both winding counts in place, refreshes Contributing, then dispatches on (e1Hot, e2Hot) and the post-update winding:

  • Both hot: close/join via AddLocalMaxPoly, or (interleave) AddOutPt on each + SwapOutrecs.
  • Exactly one hot: AddOutPt on the hot edge, then SwapOutrecs (the cold edge inherits the ring).
  • Neither hot: AddLocalMinPoly spawns a new ring when the op + winding makes the crossing a region entry.

The AEL position swap is deferred to the end of IntersectEdges (Clipper2 dispatches in pre-crossing order then swaps); AddLocalMinPoly resolves left/right from current AEL positions and walks getPrevHotEdge(left), so orientation is argument-order-independent. dispatchIntersect also handles the coincident-horizontal skip (§12.11).

12.6 DoHorizontal (engine.cpp:2526)

When a bound's cursor reaches a horizontal, DoHorizontal walks the AEL across the horizontal's X-span: at the bound's local-max vertex it calls AddLocalMaxPoly; for a contributing crossing it dispatches through IntersectEdges; otherwise it advances the cursor. Horizontals are queued during their scanline and processed after the Top events (§11.8 ordering), so the AEL is settled when they walk.

12.6.1 Horizontals as first-class AEL edges

Horizontals live in the AEL like any other edge (there is no separate synth-intersect path — every crossing flows through the single IntersectEdges model, §12.5). The crux is the winding model: a horizontal must carry the WindDx (±1) of the bound it belongs to — the sign of the bound's adjacent non-horizontal edge — not 0. A horizontal does not change the winding of a vertical ray it lies along, but it must carry its bound's contribution forward so neighbours classify correctly while it sits in the AEL.

Consequences: spawnBoundActive does not skip a leading horizontal (the bound's ActiveEdge sits on its first segment even when horizontal); advanceBoundCursor walks onto a horizontal in place (§12.10.4); a horizontal local minimum's two ascending bounds enter the AEL first, then the horizontal pass calls AddLocalMinPoly on them. The event order is Top < Bot/LocalMin < Horiz < Intersection (§11.8).

12.7 Local-minima pre-pass

Before the sweep, BuildLocalMinima (§12.1) walks each ring once, finds every Y-direction reversal, and emits sorted LocalMinima records. Horizontals count toward their non-horizontal neighbours' direction.

12.10 ActiveEdge lifecycle

Several state machines coexist in handleTop: cursor advance, intersection swaps, OutRec front/back rewiring, AEL ordering. The rules below are load-bearing.

12.10.1 Scanbeam loop

loop:
  DoIntersections(botY, y)   // ALL crossings strictly inside the beam (§12.11)
  spawn bounds at local minima at y
  advance/close bounds at Tops at y
  flush horizontals queued at y
  reconcile at-vertex crossings

Crossings are processed strictly inside the scanbeam (botY, y) — even an intersection the algebra puts at the exact top is clamped into the beam (engine.cpp:2353); no crossing ever fires at the same Y as a Top.

12.10.4 Cursor advance (advanceBoundCursor)

When a non-horizontal edge reaches its Top without ending its bound, advance the cursor to the next segment in place — emit the local-max vertex if hot, then update Seg/EdgeIdx/CurrX and queue the next Top (or, for a horizontal next segment, queue the horizontal pass). Do not remove/reinsert in the AEL: the slope may change, but AEL order is fixed by the next scanbeam's DoIntersections. This mirrors Clipper2's UpdateEdgeIntoAEL (engine.cpp:1731). After advancing, schedule fresh intersection checks against the new segment's neighbours (its slope differs from the old). A backward bound carries Reversed=true.

12.10.5 Close (closeBound)

Called when a bound's cursor reaches its last segment (or walks through its trailing horizontals). The local-max vertex is the last segment's Top, or the far endpoint of the trailing horizontal. The two bounds of the maximum may reach it at the same event (close together via AddLocalMaxPoly) or at different events (one runs Case A — emit the apex, remove from the AEL, leave the OutRec coupling for the partner's later Case B close). closeBound is also where the degenerate-confluence handlers fire (§12.11): handoff-through-vertex, the maxima/between-maxima pairing, the Intersect/Difference notch-plateau joins, and the figure-8 same-side close.

12.10.7 Load-bearing rules

  • Maxima gate on IsHotEdge, not Contributing. A post-swap reclassification can leave an edge non-contributing yet still hot; its ring must still close/join, or the top half of an overlapping-shapes union is dropped.
  • Cursor advance must reschedule intersections. The new segment may cross neighbours the old one didn't; without maybeScheduleIntersect against the new neighbours, a crossing silently never fires.
  • BuildLocalMinima is tried before ClassifyHorizontals. The bound model handles mid-bound horizontals natively (a staircase); the legacy ClassifyHorizontals rejects them. The bound model is used whenever BuildLocalMinima succeeds.
  • BuildLocalMinima decomposes self-touching rings. Input-direction adjacency reconstructs a ring that touches itself at a vertex (two same-source loops pinched at one grid point — e.g. a polygon and its hole whose corners snap together, or non-simple offset/slicer output) as a single closed walk that revisits the pinch vertex. traceRing follows a same-source unvisited edge at the start vertex (a self-intersecting ring legitimately passes through its own start vertex; a same-source pinched loop must be absorbed) and closes only when the walk returns to the start vertex with no same-source continuation — leaving a different-source touching ring for a separate trace. splitSelfTouchingLoops then splits the closed walk into its simple loops (the input-side analogue of splitSelfTouchingRings), so each loop builds correct bounds. This keeps the bound model — not the staircase-rejecting legacy fallback — handling non-simple axis-aligned input. A genuinely open chain still returns ErrOpenRing and falls back. Contract: the boolean ops therefore accept self-touching / self-intersecting input directly (resolved by non-zero winding), and Simplify cleans it; callers need not pre-Simplify. Transversal self-crossings remain subject to the fixed-point snap limitation of §7.2.

12.11 Degenerate-confluence handling

General-position crossings are handled by the per-scanbeam DoIntersections recompute: for each scanbeam (botY, topY], recompute all crossings from the settled AEL, sort by (pt.Y, pt.X), and dispatch via IntersectEdges; if rounding leaves a node's edges non-adjacent, advance to the next adjacent node first (Clipper2 ProcessIntersectList). This replaced an earlier incremental "schedule-on-adjacency-change" scheduler that silently lost crossings whenever an adjacency formed without a fresh pairwise check.

The residual complexity is degeneracies: shared vertices, vertices on edges, and collinear/coincident edges — especially where a subject hole and the clip meet. Every such failure becomes correct under off-grid perturbation, confirming it is a snap/degeneracy effect, not a structural sweep bug. The mechanisms that handle them (all gated tightly and validated against the differential harness, §6):

  • Input normalization (§11.2): simplifyCollinearRing, winding normalization, SplitOverlaps/SplitTJunctions invariants, order-independent crossing-point rounding (segCanonLess, overlap endpoints taken from input vertices not re-projected).
  • Shared-vertex / through-vertex crossings. handleLocalMin dispatches IntersectEdges at the local minimum. reconcileSharedVertexCrossings dispatches at-vertex crossings (a Touch on the beam boundary, invisible to DoIntersections) by detecting adjacent edges with equal CurrX now out of slope order; run after the Tops phase and again after the horizontal flush. handoffMaxThroughVertex hands a hot maximum edge's ring onto a cold through-edge that continues strictly above the shared vertex (decided from the bound's apex via boundContinuesAbove, not the timing-dependent cursor segment).
  • Maxima pairing. maximaPartner/isMaximaPartner pair by same-source apex identity (Clipper2 GetMaximaPair), scanning the whole AEL so an interleaved confluence (a-L,b-L,a-R,b-R) is matched, guarded by an apex-column test. resolveBetweenMaxima dispatches each between-edge through IntersectEdges before the pair closes. plateauPartnerPending/plateauMaxPartnerPending defer a plateau maximum to its geometric same-source partner so DoHorizontal closes the pair (deferring a cross-source coupling instead mis-times and drops area).
  • Notch-plateau joins (hole∪clip void merges). intersectNotchPlateau (Intersect) and differenceNotchPlateauJoin (Difference) handle a hole bound made hot by a "bite" crossing that rides up to the hole apex: the void boundary must continue along the hole's top plateau to its near end, where a cross-source clip ring re-bounds the void, and the two rings join there. Without this the hot bound is dropped and the hole's uncovered region stays filled.
  • Ring closure / same-side maxima. polyclip's bottom-up sweep, with its mirrored front/back convention, builds rings that meet same-side at an apex where Clipper2's top-down sweep closes a ring on itself. AddLocalMaxPoly resolves this two ways: a figure-8 pinch (emit the apex on each ring, cross-link the two apex OutPts into one self-touching cycle that splitSelfTouchingRings later decomposes — no orientation guess) for a genuine interleaving; and a reverse-one-ring + opposite-side join when the same-side arrival is a mirror artifact. The two are distinguished by whether a ring was spawned at a crossing (fromInputMin == false, the legitimate figure-8) versus two input-minimum rings meeting same-side (the artifact — fromInputMin, equal WindOther, both-back → reverse+join). The both-back continuing case reverses the spawned ring's sides to restore Clipper2's always-opposite-side invariant.
  • Coincident horizontals. A coincident different-source horizontal pair does not cross transversally. dispatchIntersect returns nil for an opposite-interior pair (read from Segment.Reversed) — a doubled/cancelling boundary — for non-Xor ops; processHorzJoins (clip/horzjoin.go) reconnects the skip-separated runs once global topology is known. The skip is suppressed at a boundary exit (one bound continues past the overlap), gated by continuesCollinearHorizontal, respawnHandoffAtOverlap, and an IsBoundLast requirement. For Xor the coincident hot edges interleave instead (the tunnel branch would collapse a shared plateau apex to a 2-point spike), and Xor is excluded from the horizontal-join pass.
  • Postprocess nesting (§11.9) and the traceRing reconstruction: a ring that touches itself at a vertex is traced as one closed walk and decomposed into simple loops by splitSelfTouchingLoops (§12.10.7); only a genuinely open chain returns ErrOpenRing (rather than following a sub-cycle to OOM) and falls back.

Validation — Monte-Carlo oracle, NOT Clipper2. Correctness is measured against a Monte-Carlo area oracle and the noise-free set identities (§6). Clipper2 is not a usable reference for degenerate small-integer inputs: at native scale it rounds fractional crossings to the integer grid and is itself wrong on all four ops (pre-scaling its input by 1e6 confirms the MC values). On these inputs polyclip's fine fixed-point grid is more accurate.

Rejected alternatives (measured against the oracle and refuted — do not retry):

  • Local discriminators on the dispatch-skip and the same-side AddLocalMaxPoly. No single local predicate (both-continue, hotness, WindOther, winding parity) separates touch-vs-overlap or merge-vs-separate at the firing — different coincident crossings within one op need opposite decisions. The signals that do work are structural: the opposite-interior Reversed flag, and the fromInputMin spawn provenance for the figure-8 vs reverse-join choice.
  • WindDx-derived parity in AddLocalMinPoly (replacing the outrecIsAscending proxy): the two do not coincide for legitimately hole-oriented / cross-source-merged rings; regresses badly.
  • Don't-split (whole-horizontal) model (dropping SplitOverlaps' horizontal splitting to match Clipper2): polyclip is built on the no-overlap invariant; reworking winding/ring-construction for whole overlapping horizontals regressed broadly. Keep-split + discriminated skip + join is smaller and sufficient.
  • Clipper2 splits/owner/SwapFrontBackSides machinery is not needed — it is all using_polytree_-gated; polyclip recomputes ownership in postprocess.