polystrata

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. In the benchmark suite below it is the fastest library tested on 7 of 11 workloads and the only one besides the Clipper2 ports to pass every robustness check. It will consume low quality, self-intersecting input while still producing predictable results.

• Zero dependencies, self-contained dual ESM + CommonJS build (~72 KB gzipped, including embedded WASM) and native Rust crate (polystrata on crates.io).
• Up to 3.0x faster than clipper2-js on intersection-heavy workloads (0.8x–3.0x across the suite) and 4.7x–8.6x faster than polygon-clipping, while preserving native IEEE-754 Float64 coordinates (no integer grid quantization).
• 100% pass rate across 1,000+ adversarial degenerate polygon pairs (self-intersecting bowties, shared collinear walls, T-junctions, 0.08° shallow-angle crossings, and 1.5 × 10⁶ coordinate offsets with 10⁻⁵ micro-slivers).
• Crossing-free, correctly classified output under an independent exact-predicate oracle across near-coincident copies, snap-radius slivers, jittered fans, nested holes, iterated Booleans, and coordinates from 10⁻¹² to 10³⁰⁰; non-finite vertices are dropped instead of hanging.
• Flexible inputs: accepts { x, y }[] loops, [x, y][] coordinate tuples, GeoJSON Polygon / MultiPolygon, PolygonWithHoles2D, Float64Array / Float32Array flat buffers, or raw Segment2D[] segment soups.

Installation

JavaScript / TypeScript (npm):

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:

| Format | Type | Description | | :--- | :--- | :--- | | Object Ring | Point2D[] ({ x, y }[]) | Single closed loop (CCW = outer shell, CW = hole) | | Multi-Loop Objects | Point2D[][] | Array of oriented { x, y } loops | | Tuple Ring | [number, number][] | Single closed [x, y] loop (duplicate closing vertex handled automatically) | | Tuple Multi-Loop | [number, number][][] | Array of oriented [x, y] loops | | Tuple MultiPolygon | [number, number][][][] | GeoJSON-style MultiPolygon coordinate array | | GeoJSON Geometry | GeoJSONPolygon \| GeoJSONMultiPolygon | { type: "Polygon" \| "MultiPolygon", coordinates } (rings are auto-oriented) | | Flat TypedArray | Float64Array \| Float32Array | Packed [x0, y0, x1, y1, ...] coordinates (or array of TypedArrays) | | Polygon with Holes | PolygonWithHoles2D \| PolygonWithHoles2D[] | { outer: Loop2D, holes: Loop2D[] } | | Segment Soup | Segment2D[] | { p0: Point2D, p1: Point2D }[] (snaps micro-gaps & removes dangling whiskers) |

API Reference

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. manifold-3d (CrossSection) & Other JavaScript/TypeScript Libraries

Need 3D Planar B-Rep Boolean operations? See polystrata-3d.

Run the 2D benchmark suite locally with npm run bench:

Measured across all 4 Boolean operations (union, intersect, difference, xor) on Node.js; each timing includes producing JS output, and each sample repeats the operations for at least 2 ms. The fastest library per workload is in bold. PASS/FAIL is the inclusion-exclusion area check.

| 2D Workload | Vertices | polystrata (Rust/WASM) | manifold-3d (CrossSection) | clipper2-js (v1.2.4) | polygon-clipping (v0.15.7) | @velipso/polybool (v2.0.11) | martinez (v0.7.3) | | :--- | ---: | ---: | ---: | ---: | ---: | ---: | ---: | | CAD Gears + Bore Holes | 192 | 24,720 op/s (PASS) | 11,914 op/s (PASS) | 12,693 op/s (PASS) | 4,496 op/s (PASS) | 3,413 op/s (PASS) | 11,530 op/s (FAIL) | | Swiss-Cheese 25-Hole Plate | 224 | 15,371 op/s (PASS) | 9,715 op/s (PASS) | 16,182 op/s (PASS) | 3,253 op/s (PASS) | 2,593 op/s (PASS) | 7,920 op/s (FAIL) | | Comb Array x Diagonal Bars | 72 | 13,847 op/s (PASS) | 6,403 op/s (PASS) | 14,589 op/s (PASS) | 2,053 op/s (PASS) | 2,414 op/s (PASS) | 6,296 op/s (FAIL) | | Star Scaling (N = 64) | 64 | 54,549 op/s (PASS) | 24,879 op/s (PASS) | 36,649 op/s (PASS) | 10,624 op/s (PASS) | 11,125 op/s (PASS) | 29,193 op/s (FAIL) | | Star Scaling (N = 256) | 256 | 8,373 op/s (PASS) | 3,798 op/s (PASS) | 3,469 op/s (PASS) | 1,264 op/s (PASS) | 1,350 op/s (PASS) | 3,275 op/s (FAIL) | | Star Scaling (N = 1024) | 1,024 | 627 op/s (PASS) | 275 op/s (PASS) | 239 op/s (PASS) | 97 op/s (PASS) | 107 op/s (PASS) | 230 op/s (FAIL) | | Star Scaling (N = 2048) | 2,048 | 159 op/s (PASS) | 56 op/s (PASS) | 52 op/s (PASS) | 21 op/s (PASS) | 23 op/s (PASS) | 58 op/s (FAIL) | | Shared Collinear Walls | 24 | 167,872 op/s (PASS) | 110,232 op/s (PASS) | 158,272 op/s (PASS) | 23,726 op/s (PASS) | 37,768 op/s (FAIL) | 91,480 op/s (FAIL) | | Shallow-Angle (0.08°) | 8 | 223,525 op/s (PASS) | 94,650 op/s (PASS) | 246,642 op/s (PASS) | 29,343 op/s (PASS) | 70,748 op/s (PASS) | 156,609 op/s (PASS) | | Bowties & Pinch Corners | 12 | 215,604 op/s (PASS) | 153,666 op/s (PASS) | 279,815 op/s (PASS) | 24,988 op/s (FAIL) | 52,300 op/s (FAIL) | 126,308 op/s (FAIL) | | Large Offset (1.5 × 10⁶) | 9 | 413,334 op/s (PASS) | 158,044 op/s (PASS) | 389,496 op/s (PASS) | 70,741 op/s (PASS) | 127,272 op/s (PASS) | 340,008 op/s (PASS) | | 120-Pair Fuzz Suite (480 ops) | — | 182,422 op/s (120/120) | 69,359 op/s (120/120) | 114,906 op/s (120/120) | 36,969 op/s (116/120) | 46,102 op/s (113/120) | 122,489 op/s (68/120) |

Architecture: 4-Stage Stratified Tolerance Complex

1. 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₀.
2. 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.
3. 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.
4. 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