exact-poly

Live demo: exact-poly.merca.earth

Integer polygon geometry for deterministic on-chain validation. Rust library compiled to WebAssembly.

Used by

• mercaearth/mercator — reverse side, Move VM polygon validation on-chain
• merca.earth — production land registry frontend

All arithmetic uses i64 coordinates in fixed-point representation (1 unit = 1 micrometer at SCALE = 1,000,000). No floats anywhere — results are bit-exact and reproducible across every platform.

Why

Floating-point polygon math is nondeterministic across architectures. On-chain land registry needs geometry operations that produce identical results on every validator node, in every browser, and in every Move VM execution. exact-poly solves this by using integer-only arithmetic with 128-bit intermediates where needed.

Features

Convex decomposition — split any simple polygon into convex parts:

• Cascade strategy: tries ExactPartition → Bayazit → EarClip+Hertel-Mehlhorn, picks the first valid result
• Ring rotation for difficult geometries
• Minimize-parts mode: exhaustive search across all strategies and rotations
• Steiner point tracking

Area & perimeter — exact computation without division:

• twice_area returns 2× the area (avoids the ÷2 that would lose precision)
• Signed area for winding detection
• L1 (Manhattan) perimeter
• Area conservation verification across decomposed parts

Ring operations:

• CCW/CW winding detection and normalization
• Simplicity check (self-intersection detection)
• Convexity check
• Collinear vertex removal
• Canonical normalization (rotation to smallest vertex)

Spatial queries:

• Point-in-convex-polygon (strict interior)
• Point-on-boundary
• Point-inside-or-on-boundary (inclusive)

Overlap detection:

• SAT (Separating Axis Theorem) for convex pairs
• AABB pre-filter for early rejection
• Multi-part overlap search

Topology validation:

• Shared edge detection between adjacent parts
• BFS connectivity check
• Hole detection via boundary graph analysis
• Vertex-only contact detection
• T-junction / partial overlap classification
• Compactness (isoperimetric ratio) validation

Geometric primitives:

• Cross product, orientation (CCW / CW / Collinear)
• Point-on-segment, segment intersection
• Reflex vertex detection

Install

npm (WASM)

npm install exact-poly

Package ships three wasm-bindgen targets — picked automatically via conditional exports:

All functions accept BigInt64Array for polygon rings encoded as flat [x0, y0, x1, y1, ...].

Node / bundler:

import { decompose_polygon, twice_area, is_convex } from "exact-poly";

const ring = BigInt64Array.from([0n, 0n, 60n, 0n, 60n, 40n, 30n, 40n, 30n, 80n, 0n, 80n]);

const result = decompose_polygon(ring, true);
console.log(result.parts.length); // convex parts

const area = twice_area(ring);
console.log(area); // "7200" (2× the actual area)

console.log(is_convex(ring)); // false (L-shape)

Browser direct:

import init, { twice_area } from "exact-poly/web";

await init();
const ring = BigInt64Array.from([0n, 0n, 60n, 0n, 60n, 40n, 30n, 40n, 30n, 80n, 0n, 80n]);
console.log(twice_area(ring)); // "7200"

Rust (crate)

[dependencies]
exact-poly = { git = "https://github.com/mercaearth/exact-poly" }

use exact_poly::decompose::decompose;
use exact_poly::types::{DecomposeOptions, ProtocolConfig};

let ring = vec![[0, 0], [60, 0], [60, 40], [30, 40], [30, 80], [0, 80]];
let result = decompose(&ring, &DecomposeOptions::default(), &ProtocolConfig::default()).unwrap();
println!("{} parts", result.parts.len());

Build

Requires wasm-pack:

bash build.sh

Builds three wasm-bindgen targets in parallel — pkg/bundler/, pkg/node/, pkg/web/. Run tests with:

cargo test

222 tests covering decomposition strategies, area conservation, topology validation, edge cases, and geometric primitives.

Demo

Interactive demo app with 7 tabs visualizing every feature:

cd demo && npm install && npm run dev

Draw polygons or pick presets. See decomposition results, area metrics, reflex vertices, point-in-polygon testing, SAT overlap detection, topology validation, and primitive operations — all running the WASM module in the browser.

Coordinate convention

Areas are returned as 2 × area (string-encoded u128 / i128) to avoid precision loss from division.

Protocol config

Validation functions accept an optional ProtocolConfig controlling on-chain limits:

Use ProtocolConfig::permissive() (Rust) or omit the config parameter (JS) for demo/testing with no validation limits.

API reference

Decomposition

Area & metrics

Ring operations

Spatial queries

Overlap

Topology

Primitives

Architecture

src/
  lib.rs              WASM bindings (#[wasm_bindgen] exports)
  types.rs            Core types: Point, Part, DecomposeResult, ProtocolConfig
  constants.rs        On-chain protocol constants
  decompose.rs        Cascade decomposition engine
  exact_partition.rs  Diagonal-only convex partition
  bayazit.rs          Bayazit convex decomposition
  ear_clip.rs         Ear clipping triangulation
  hertel_mehlhorn.rs  Triangle merge optimization
  area.rs             Exact area computation (i128)
  ring.rs             Ring operations (CCW, simple, normalize)
  spatial.rs          Point-in-polygon queries
  sat.rs              Separating Axis Theorem
  aabb.rs             Axis-aligned bounding boxes
  overlap.rs          Multi-part overlap detection
  containment.rs      Polygon containment
  shared_edge.rs      Edge sharing and contact classification
  topology.rs         Multipart topology validation
  validation.rs       Per-part structural validation
  validate_onchain.rs End-to-end on-chain validation
  primitives.rs       Cross product, orientation, segment ops
  signed.rs           Signed integer helpers (i128)

License

MIT — see LICENSE.