Polystrata – High-performance, topologically robust 2D polygon clipping

Interactive Demo & Fuzzer • Live Browser Benchmark Suite • npm • crates.io • docs.rs

Polystrata is a high-performance, topologically robust 2D polygon clipping library implemented in Rust and available in JS via WebAssembly. To my knowledge, it is simultaneously the fastest AND the most robust polygon clipping library available for JS. It will consume low quality, self-intersecting input while still producing predictable results.

npm install polystrata

Rust (crates.io / docs.rs):

cargo add polystrata

Quick Start

import { union, intersect, difference, xor, heal, unionAll, toGeoJSON, initPolystrata, } from "polystrata";

// Optional on Node.js / Bun / Deno / Web Workers; recommended once at startup on browser main threads: await initPolystrata();

// 1. Using { x, y } point loops: const boxA = [ { x: 0, y: 0 }, { x: 20, y: 0 }, { x: 20, y: 20 }, { x: 0, y: 20 }, ]; const boxB = [ { x: 10, y: 5 }, { x: 30, y: 5 }, { x: 30, y: 15 }, { x: 10, y: 15 }, ];

const diff = difference(boxA, boxB); console.log(diff.polygons); // [{ outer: Loop2D, holes: Loop2D[] }] console.log(diff.loops); // Flat array of oriented CCW outer shells & CW holes

// 2. Using [x, y] coordinate tuples or GeoJSON geometries directly: const poly1 = [ [0, 0], [10, 0], [10, 10], [0, 10], ]; const poly2 = { type: "Polygon" as const, coordinates: [ [ [5, 0], [15, 0], [15, 10], [5, 10], [5, 0], ], ], };

const merged = union(poly1, poly2); const geojson = toGeoJSON(merged); // { type: "MultiPolygon", coordinates: number[][][][] }

Quick Start (Rust)

use polystrata::{union, intersect, difference, xor, heal, KernelOptions, WindingRule};

let square_a = [[0.0, 0.0], [10.0, 0.0], [10.0, 10.0], [0.0, 10.0]]; let square_b = [[5.0, 5.0], [15.0, 5.0], [15.0, 15.0], [5.0, 15.0]];

let opts = KernelOptions::default();

let u = union(&square_a, &square_b, opts); let i = intersect(&square_a, &square_b, opts); let d = difference(&square_a, &square_b, opts); let x = xor(&square_a, &square_b, opts);

// Self-intersection healing (e.g. figure-8 bowtie -> 2 simple CCW triangles) let bowtie = [[0.0, 0.0], [10.0, 10.0], [10.0, 0.0], [0.0, 10.0]]; let healed = heal( &bowtie, KernelOptions { winding_rule: WindingRule::NonZero, ..KernelOptions::default() }, );

Supported Input Formats (ShapeInput2D)

Every operation (union, intersect, difference, xor, heal, unionAll, intersectAll, clip, booleanMulti) accepts any of the following shapes:

Binary Boolean Operations

union(a, b, options?): Compute union (A ∪ B).

intersect(a, b, options?): Compute intersection (A ∩ B).

difference(a, b, options?): Compute difference (A \ B).

xor(a, b, options?): Compute symmetric difference (A ⊕ B).

clip(op, a, b?, options?): Dynamic dispatcher where op is "union" | "intersect" | "difference" | "xor" | "heal".

Topological Healing & N-Ary Operations

heal(input, options?): Snap micro-gaps, split self-intersections, cancel zero-winding whiskers, decompose figure-8 pinch vertices, and extract clean manifold shells and holes.

unionAll(shapes, options?): Single-pass N-shape union in WASM.

intersectAll(shapes, options?): Single-pass N-shape intersection in WASM.

booleanMulti(inputs, predicate, options?): Evaluate an arbitrary N-body winding predicate (windings: ReadonlyArray<number>) => boolean over the consolidated planar arrangement in a single pass.

// Example: (A ∪ B) \ C in a single topological arrangement pass const res = booleanMulti( [shapeA, shapeB, shapeC], (w) => ((w[0] ?? 0) > 0 || (w[1] ?? 0) > 0) && (w[2] ?? 0) <= 0, );

Output & Geometry Helpers

signedLoopArea(loop): Signed area via the Shoelace formula (> 0 for CCW outer shells, < 0 for CW holes). Accepts { x, y }[], [x, y][], or Float64Array | Float32Array.

toTupleMultiPolygon(result, closeRings = true): Converts a KernelResult to [number, number][][][].

toGeoJSON(result): Converts a KernelResult to { type: "MultiPolygon", coordinates: number[][][][] }.

prepareBooleanTask(subject, clip): Pre-normalizes a (subject, clip) pair in WASM linear memory for repeated zero-copy Boolean queries (task.run(0 | 1 | 2 | 3)).

Options (KernelOptions)

interface KernelOptions { /** Explicit snap tolerance r0 in world units (default: auto-scaled 1e-9 * bboxDiagonal). / snapTolerance?: number; /* Merge collinear degree-2 vertices on output boundary loops (default: true). / simplifyCollinear?: boolean; /* Winding rule: "positive" | "nonZero" | "evenOdd" (default: "positive" for booleans, "nonZero" for heal). */ windingRule?: "positive" | "nonZero" | "evenOdd"; }

Benchmarks vs. Other JavaScript/TypeScript Libraries

Measured with npm run bench on Node.js v24 across all 4 Boolean operations (union, intersect, difference, xor):

Stage 0 — Scale-Aware Coordinate Normalization: Shifts the global bounding-box center to the origin to maximize IEEE-754 f64 significand bits and derives a scale-aware tolerance r₀ = 1e-9 × L and cap r_max = 4 × r₀.

Stages 1 & 2 — Fixed-Point Tolerance Complex Consolidation: Iteratively applies Vertex Cluster Merging, Degenerate Edge Collapse, Two-Pointer 1D X-Sweep Vertex-On-Edge Splitting (T-junctions), and 1D Sort-and-Sweep Interior Segment Intersection with dirty-AABB pruning until a strict topological fixed point is reached.

Stage 3 — Planar Half-Edge Arrangement: Sorts half-edges counter-clockwise around each consolidated vertex in flat CSR buffers (O(1) twin/next lookup) and traces minimal cycles.

Stage 4 — Dual-Graph BFS Winding Classification & Pinch Decomposition: Evaluates exact integer winding numbers in O(C + E) via Dual-Graph BFS across cycle boundaries, extracts surviving boundary half-edges where the predicate flips, and decomposes higher-genus pinch vertices into simple CCW shells and CW holes.

License

MIT