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:

| Runtime | Resolved entry | Notes | |---|---|---| | Node.js (import/require) | pkg/node/ | Sync init, works out of the box | | Bundlers (Vite, webpack, Rollup) | pkg/bundler/ | Vite needs vite-plugin-wasm + vite-plugin-top-level-await; webpack 5 supports WASM natively | | Browser direct (no bundler) | import "exact-poly/web" | Returns an init() you must await before calling 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

| Property | Value | |---|---| | Type | i64 (signed 64-bit integer) | | Scale | 1,000,000 units = 1 meter | | Winding | Counter-clockwise (CCW) | | Encoding | Flat array: [x0, y0, x1, y1, ...] | | JS type | BigInt64Array |

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:

| Parameter | Default (Merca) | Description | |---|---|---| | max_parts | 10 | Maximum convex parts per polygon | | max_vertices_per_part | 64 | Maximum vertices per convex part | | min_edge_length_squared | 10^12 | Minimum edge length² (1 meter²) | | min_compactness_ppm | 150,000 | Isoperimetric ratio floor (ppm) | | area_divisor | 2 × 10^12 | Converts 2×area to display m² |

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

API reference

Decomposition

| Function | Description | |---|---| | decompose_polygon(ring, allow_steiner, trace?, minimize?, config?) | Cascade decomposition into convex parts | | bayazit_decompose_polygon(ring, allow_steiner) | Bayazit algorithm only | | exact_vertex_partition_polygon(ring) | Diagonal-only partition (no Steiner points) | | ear_clip_triangulate_polygon(ring) | Ear clipping triangulation | | optimize_partition(parts) | Hertel-Mehlhorn merge of triangulated parts |

Area & metrics

| Function | Returns | |---|---| | twice_area_ring(ring) | Unsigned 2×area as string | | signed_area_2x_ring(ring) | Signed 2×area (positive = CCW) | | areas_conserved_values(original, part_areas) | true if sum of parts equals original | | perimeter_l1_ring(ring) | Manhattan perimeter as string |

Ring operations

| Function | Description | |---|---| | is_ccw_ring(ring) | Winding direction check | | ensure_ccw_ring(ring) | Reverse if CW → return CCW | | is_simple_ring(ring) | No self-intersections | | is_convex_ring(ring) | All vertices convex | | remove_collinear_ring(ring) | Strip collinear vertices | | normalize_polygon_ring(ring) | Canonical form (rotate to smallest vertex) |

Spatial queries

| Function | Description | |---|---| | point_strictly_inside_convex_ring(px, py, ring) | Strict interior (convex only) | | point_on_polygon_boundary_ring(px, py, ring) | On any edge | | point_inside_or_on_boundary_ring(px, py, ring) | Interior or boundary | | point_inside_any_part(parts, x, y) | Point in any convex part | | contains_polygon(outer_parts, inner_parts) | Full polygon containment |

Overlap

| Function | Description | |---|---| | sat_overlap(a, b) | SAT overlap for two convex polygons | | sat_overlap_with_aabb(a, b) | SAT with AABB early-out | | convex_parts_overlap(a, b) | Interior overlap (touching OK) | | parts_overlap(a_parts, b_parts) | Any part pair overlaps |

Topology

| Function | Description | |---|---| | validate_multipart_topology(parts, allow_vertex_contact?, config?) | Full topology validation | | has_exact_shared_edge(a, b) | Shared edge between two parts | | classify_contact(a, b) | "shared_edge" / "partial_contact" / "none" | | validate_decomposition(ring, parts, config?) | End-to-end on-chain validation |

Primitives

| Function | Description | |---|---| | orientation(ax, ay, bx, by, cx, cy) | "CounterClockwise" / "Clockwise" / "Collinear" | | cross2d(ax, ay, bx, by, cx, cy) | Cross product as string | | is_left(ax, ay, bx, by, px, py) | Point left of directed line | | is_reflex(prev_x, prev_y, curr_x, curr_y, next_x, next_y) | Reflex vertex test | | segments_intersect(a1x, a1y, a2x, a2y, b1x, b1y, b2x, b2y) | Segment intersection (including endpoints) | | segments_properly_intersect(...) | Strict crossing (excluding endpoints) | | point_on_segment(px, py, ax, ay, bx, by) | Point lies on segment |

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.