Polystrata가 Rust 기반 다각형 연산 라이브러리로 공개됐다

polystrata는 Rust로 구현한 2D 다각형 클리핑 라이브러리로, WebAssembly를 통해 JavaScript에서도 사용할 수 있다. 제작자 측은 저품질 입력과 자기 교차 다각형을 처리하면서 예측 가능한 결과를 내며, JavaScript용 다각형 클리핑 라이브러리 가운데 가장 빠르고 견고하다고 소개한다.

• 인터랙티브 데모 및 퍼저
• 실시간 브라우저 벤치마크 모음
• npm · crates.io · docs.rs

소개 자료에 따르면 이 라이브러리는 의존성이 없으며, 임베디드 WebAssembly를 포함한 ESM·CommonJS 겸용 빌드의 압축 크기는 약 53KB다. 네이티브 Rust 크레이트도 제공한다. 좌표를 정수 격자로 양자화하지 않고 IEEE-754 Float64 좌표를 유지한다.

제작자 측 벤치마크에서는 CAD, 교차가 많은 입력의 규모 확장, 적대적 퍼징 작업에서 clipper2-js보다 2.0~3.1배, polygon-clipping보다 6~22배 빠른 결과를 제시했다. 자기 교차 나비넥타이, 같은 선상에 놓인 벽, T자 교차, 0.08°의 얕은 각도 교차, 1.5 × 10⁶ 좌표 오프셋에 10⁻⁵ 크기의 미세 슬리버가 포함된 퇴화 다각형 쌍 1,000개 이상에서는 100% 통과했다고 설명한다. 이 수치는 제작자 측 자료에 실린 결과다.

입력으로는 { x, y }[] 루프, [x, y][] 좌표 튜플, GeoJSON Polygon·MultiPolygon, PolygonWithHoles2D, Float64Array·Float32Array 평탄 버퍼, 원시 Segment2D[] 선분 모음을 받을 수 있다.

설치와 시작하기

JavaScript·TypeScript에서는 npm으로 설치한다.

npm install polystrata

Rust에서는 다음 명령을 사용한다.

cargo add polystrata

JavaScript·TypeScript의 기본 사용 예시는 다음과 같다.

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[][][][] }

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()
 },
);

ShapeInput2D 형식은 모든 연산에서 사용할 수 있다. 대상 연산은 union, intersect, difference, xor, heal, unionAll, intersectAll, clip, booleanMulti다.

연산과 옵션

이진 불리언 연산은 union(a, b, options?)가 합집합(A ∪ B), intersect(a, b, options?)가 교집합(A ∩ B), difference(a, b, options?)가 차집합(A \\ B), xor(a, b, options?)가 대칭 차집합(A ⊕ B)을 계산한다. clip(op, a, b?, options?)는 "union", "intersect", "difference", "xor", "heal"을 지정해 연산을 선택하는 디스패처다.

heal(input, options?)는 미세한 틈을 맞추고 자기 교차를 나누며, 감김 수가 0인 짧은 선분을 상쇄하고, 8자 모양의 접점 꼭짓점을 분해해 정돈된 매니폴드 외곽과 구멍을 추출한다. unionAll(shapes, options?)와 intersectAll(shapes, options?)는 WebAssembly에서 여러 도형의 합집합·교집합을 한 번에 계산한다. booleanMulti(inputs, predicate, options?)는 하나의 통합된 평면 배치에서 감김 수 배열을 대상으로 임의의 N개 도형 판정 함수를 한 번에 평가한다.

다음 예시는 하나의 위상 배치 처리 단계에서 (A ∪ B) \\ C를 계산한다.

const res = booleanMulti(
 [shapeA, shapeB, shapeC],
 (w) => ((w[0] ?? 0) > 0 || (w[1] ?? 0) > 0) && (w[2] ?? 0) <= 0,
);

기하 도우미에는 부호 있는 면적을 계산하는 signedLoopArea(loop)가 있다. 신발끈 공식으로 면적을 구하며, CCW 외곽은 양수, CW 구멍은 음수로 표시한다. { x, y }[], [x, y][], Float64Array, Float32Array를 받는다. toTupleMultiPolygon(result, closeRings = true)는 KernelResult를 [number, number][][][]로 변환하고, toGeoJSON(result)는 { type: "MultiPolygon", coordinates: number[][][][] }로 변환한다. prepareBooleanTask(subject, clip)은 반복적인 제로 카피 불리언 질의를 위해 WebAssembly 선형 메모리에서 입력 쌍을 사전 정규화한다. 반환된 작업은 task.run(0 | 1 | 2 | 3)으로 실행한다.

KernelOptions에서 스냅 허용 오차는 월드 단위의 snapTolerance로 지정한다. 기본값은 경계 상자 대각선에 1e-9를 곱해 자동 조정한다. simplifyCollinear는 출력 경계 루프의 같은 직선상에 있는 차수 2 꼭짓점을 합치며 기본값은 true다. windingRule은 "positive", "nonZero", "evenOdd" 중에서 고른다. 불리언 연산의 기본값은 "positive", heal의 기본값은 "nonZero"다.

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";
}

제작자 측 벤치마크

다음 결과는 Node.js v24에서 npm run bench로 네 가지 불리언 연산(union, intersect, difference, xor)을 측정한 것이다. 처리량 단위는 초당 연산 수(op/s)다.

처리 구조와 라이선스

제작자 측 설명은 처리 구조를 단계별 허용 오차 복합체로 소개한다. 0단계에서는 전체 경계 상자의 중심을 원점으로 옮겨 IEEE-754 f64 유효숫자 비트를 최대한 활용한다. 이어 규모를 고려한 허용 오차 r₀ = 1e-9 × L과 상한 r_max = 4 × r₀를 계산한다.

1·2단계에서는 꼭짓점 군집 병합, 퇴화한 변 축소, 두 포인터 방식의 1차원 X 스윕을 통한 변 위 꼭짓점 분할(T자 교차), 더티 경계 상자 가지치기를 적용한 1차원 정렬·스윕 방식의 내부 선분 교차 처리를 반복한다. 엄격한 위상 고정점에 도달할 때까지 수행한다.

3단계에서는 평탄한 CSR 버퍼에서 통합된 각 꼭짓점을 중심으로 반변을 반시계 방향으로 정렬한다. 이 구조에서는 쌍둥이·다음 요소를 O(1)에 조회하고 최소 사이클을 추적한다.

4단계에서는 이중 그래프 너비 우선 탐색(BFS)으로 사이클 경계를 가로질러 정확한 정수 감김 수를 O(C + E)에 분류한다. 판정 결과가 바뀌는 경계 반변을 추출한 뒤, 더 높은 속(genus)의 뾰족 접점 꼭짓점을 단순한 CCW 외곽과 CW 구멍으로 분해한다.

Polystrata의 라이선스는 MIT다.