# Robust Triangulation with Louvre 🌙
[](https://crates.io/crates/louvre)
[](https://docs.rs/louvre)
Louvre is a robust triangulation algorithm, which can handle self-intersecting polygons' triangulation.
▶️ [Live demo page](https://acheul.github.io/louvre)
> [Polygon Triangulation](https://en.wikipedia.org/wiki/Polygon_triangulation)
> [Simple Polygon](https://en.wikipedia.org/wiki/Simple_polygon) vs. [Self-Intersecting Polygon](https://en.wikipedia.org/wiki/List_of_self-intersecting_polygons)
---
Ear-clipping libraries in the [mapbox/earcut](https://github.com/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
```rust
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:
```rust
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):
```rust
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](https://crates.io/crates/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):
| 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](https://acheul.github.io/louvre).
## 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!