Robust Triangulation with Louvre 🌙

Louvre is a robust triangulation algorithm, which can handle self-intersecting polygons' triangulation.

▶️ Live demo page

Polygon Triangulation

Simple Polygon vs. Self-Intersecting Polygon

---

Ear-clipping libraries in the mapbox/earcut family are fast, but they assume a simple polygon: feed them a self-intersecting boundary and the output silently loses or double-covers regions.

Louvre closes that gap. It detects every crossing exactly, splits the boundary at the intersection points into simple cycles (switching strands at each crossing), then ear-clips each cycle — with a z-order-indexed ear test and a uniform-grid broad phase for the intersection detection. Degenerate inputs are part of the contract, not an afterthought: vertex touches vs. genuine piercings are distinguished, and even k segments crossing at one exact point are resolved deterministically.

Works in native Rust and wasm.

Usage

use louvre::triangulate_owned;

// a self-intersecting "bowtie"; its two crossing edges meet at (1, 1)
let data: Vec<f64> = vec![0., 0., 2., 2., 2., 0., 0., 2.];

let (coords, indices) = triangulate_owned(data, 2).unwrap();

// the crossing point was detected and appended after the input vertices
assert_eq!(coords, vec![0., 0., 2., 2., 2., 0., 0., 2., /* added: */ 1., 1.]);

// indices point at each corner's x-position in `coords` (point i = coords[i..i+2]),
// flat-packed 3 per triangle: here two triangles meeting at the crossing
assert_eq!(indices, vec![6, 0, 8, 8, 2, 4]);

A borrowing variant keeps the input untouched and returns the added intersection points separately:

use louvre::triangulate;

let data: Vec<f64> = vec![0., 0., 2., 2., 2., 0., 0., 2.];
let (coords, added, indices) = triangulate(&data, 2).unwrap();

assert_eq!(coords, &data[..]);              // simple inputs borrow: zero copy
assert_eq!(added, Some(vec![1., 1.]));      // None when the polygon is simple
assert_eq!(indices, vec![6, 0, 8, 8, 2, 4]);

When the input is simple by construction, triangulate_simple skips the intersection-detection pass entirely and ear-clips directly — earcut-class overhead, earcut-class trust contract (a self-intersecting input yields an unspecified result, no error):

use louvre::triangulate_simple;

let data: Vec<f64> = vec![0., 0., 2., 0., 2., 2., 0., 2.];
let (coords, indices) = triangulate_simple(&data, 2).unwrap();
assert_eq!(indices.len(), 6); // 2 triangles

The louvre crate is a facade over two workspace crates: louvre-tri (the triangulation algorithm) and louvre-utils (geometry primitives).

Performance

Average ms per call, release build, one machine — reproduce with cargo bench -p louvre-tri. The reference is earcutr (the Rust port of mapbox/earcut), compared only on simple polygons — the capability the two share. louvre is the robust default (triangulate, detection included); louvre simple is the trusted fast path (triangulate_simple, no detection — the apples-to-apples column):

input	earcutr	louvre	louvre simple
hilbert (1,027 verts)	0.40	0.49	0.38
water2 (1,006 verts, clipped geography full of boundary touches)	0.51	0.74	0.51
comb (4,002 verts, spiky)	11.1	7.7	0.8
comb (8,002 verts)	49.5	27.6	1.6

The gap between the two louvre columns is the intersection-detection pass — the whole price of robustness, always included in triangulate. On self-intersecting inputs there is no comparison to make: a dense star {101/3} with ~200 genuine crossings triangulates in ~0.15 ms, correctly.

In the browser the story holds: on the same V8 runtime, louvre-wasm matches earcut.js call-for-call on hilbert (~0.7 ms each) — try it on the demo page.

Limitations

• Robustness is paid for on every triangulate call. The intersection scan runs even on provably simple inputs. triangulate_simple opts out of it — at the cost of the same blind-trust contract as earcut-family: it cannot even tell you the input was self-intersecting.
• Holes are out of scope. Louvre takes a single closed boundary; there is no hole_indices-style input. Self-intersecting: yes. Multiply-connected: no.
• The geometry is 2D. Higher dim inputs are accepted, but triangulation happens on x/y; coordinates of added intersection points beyond x/y are zero-filled.
• Exact f64 arithmetic, no epsilon snapping. Collinear overlapping edges are not treated as crossings, and near-degenerate float inputs follow exact-comparison semantics. Extreme degeneracies (many segments through one exact point) are resolved by a deterministic virtual perturbation; this is fuzz-tested, with known imperfection only in pathological cases (7+ concurrent segments).

Logs

• v.0.2.0

  • minor adjustement of module structure.
  • feature html added.

• v.0.2.1

  • minor interior modifications

• v.0.3.0

  • Use vector, not linked array for polygon cycle.
    • no more unsafe code.
  • Boost up overall triangulate efficiency!