Module retriangulate 

In-plane constrained re-triangulation — phases A–F.

Each input triangle T crossed by other triangles accumulates intersection sub-segments lying in its plane; this module re-triangulates T into a conforming, intersection-free fan of sub-triangles whose vertices are referenced SYMBOLICALLY (via the interner, never a float coordinate), with a topology that is invariant to insertion order and byte-identical across platforms.

PHASE A is the exact projection axis + reference winding; PHASE B the canonical lex-rank work list; phases C–F (point insertion, segment insertion, earcut, emit) build on the canonical list produced here.

Structs

Canonical

PHASE B output — the canonical, order-independent work list.

Constraint

A constraint segment lying in T’s plane (endpoints explicit or implicit).

Mesh2d

The evolving 2D triangulation of T during phases C–E.

RetriInput

Input to the re-triangulation of one triangle T.

Functions

canonicalize

PHASE B — intern T’s corners + every constraint endpoint into the shared interner, order each segment’s endpoints by lex-rank, and sort the segment list canonically (deduplicating). The output is a pure function of the input geometry, independent of the order constraints arrive in.

earcut

PHASE E — triangulate a simple polygon ring (oriented w0) by deterministic ear clipping. An ear is a strictly-convex corner whose triangle contains no other ring vertex; among all ears we always clip the one with the lexicographically-least APEX, so the output is a pure function of the ring (independent of where the ring starts). The two-ears theorem guarantees a simple polygon always has an ear → termination.

projection_axis

PHASE A — pick the drop axis whose projected area is EXACTLY nonzero, plus the reference winding w0 (the orient2d sign of T under that axis, so every output sub-triangle can be emitted with T’s orientation). None ⇒ T is degenerate (zero projected area in every axis).

retriangulation_manifest

Cross-platform re-triangulation determinism manifest: the topology hash of a fixed fixture (a triangle + constraints with explicit/LPI/TPI endpoints, some requiring recovery / on-edge), for the wasm/ARM cross-check (analogous to the predicate sign manifest).

triangulate

Phases A–D: project, canonicalise, insert all constraint points, then force every constraint to appear as an edge (chain). None ⇒ T is degenerate.

triangulation_topology_hash

PHASE F — a deterministic TOPOLOGY fingerprint of the triangulation: every sub-triangle as its sorted Vid triple, the set sorted, FNV-1a-hashed. Vids are symbolic identities assigned in a deterministic (input-driven, exact-cmp_lex dedup) order and every geometric decision is exact, so this hash is byte-identical across x86_64/aarch64/wasm. (We hash Vid CONNECTIVITY, not coordinates — the determinism bar is topology, not coordinates.)

Type Aliases

SubTri

A sub-triangle of T (interned Vids), oriented to match w0.