Created using Codex. This project is the result of vibe programming.
TRIAGE

C++17  /  JULIA  /  MIT LICENSE

Fast triangulation of polygons (simple and with holes).

Simple polygons. Interior holes. No added points.

Triage combines three algorithms to handle small polygons and large geographic boundaries.

Explore the code
TRIAGE, cut out of a triangulated rectangle Six stencil letters are polygon holes. Triage computed 99 triangles using 89 original vertices, with no added points.
A rectangle with six letter-shaped holes. This mesh was computed by Triage.

Stencil lettering keeps each hole simple. Only original boundary vertices are used. Reproduce this figure ↗

Triage draws on ideas from theoretical computational geometry, including monotone chains and implicit vertical decomposition, whose practical benefits emerge on sufficiently large inputs. Such polygons arise in GIS applications, for example in detailed country, state, and county boundaries.

3.8×

Faster than Earcut
on large geographic rings

6.8×

Faster than Earcut
on geographic domains with holes

0

Added vertices
across the verified corpus

C++ batch medians on the published November 2026 benchmark. Speed depends on the input and hardware. See every result ↓

01 / THE ALGORITHM

Three paths.
One triangulator.

01

Small polygons

Up to 64 vertices, without holes: ear cutting with a compact mask of live reflex vertices.

02

Small domains with holes

Up to 32 total vertices: join a hole when it blocks an ear, then continue cutting.

03

Larger inputs

Sweep monotone chains, insert diagonals between original vertices, and triangulate compact boundary ranges.

Also available in C++ and Julia: triangulate_bounded, a separate strategy with an O(n log n) worst-case time bound. It uses a balanced sweep status and sorted endpoint directions. The C++ version now combines Triage's chains with a BCG-style preallocated AVL tree: about 9% less time on large geographic rings and 39% less on the largest comb than the previous bounded backend. Julia's corresponding experiment was mixed, so its public backend stays unchanged. Measurements ↗ · Algorithm ↗

02 / THE MEASUREMENTS

Measured, with the
data to reproduce it.

Compared with Mapbox Earcut on identical prepared inputs. Times are milliseconds for a whole batch; lower is better.

CorpusPolygonsC++ Triage (ms)Julia Triage (ms)Earcut C++ (ms)
Single-ring tiles11153944.36993.22946.451
Holed tiles579937.17058.03544.270
Large geographic rings19224.932272.317855.080
Geographic domains with holes1013.77820.41993.124
Accepted named fixtures120.6652.2200.651
Synthetic holed domains36358.216403.8166386.496

The tradeoff: C++ Triage wins the tile and geographic batches in this run, but is about 2% slower on accepted named fixtures. Julia is competitive on large geometry and slower than Earcut on small tiles.

Intel Core i7-11700 · GCC 16.2 · Julia 1.13.3 · one thread · 12 warmed samples. Preparation is excluded. C++ and Julia were measured serially.

Raw samples, input hashes, and verification logs ↗

03 / ADVERSARIAL INPUTS

Worst-case inputs.

Two constructed families expose different weaknesses. These are stress tests, not a representative GIS workload or a claim to be the slowest possible inputs.

A comb: bad for default Triage

A simple polygon with many teeth creates a large active set before earlier intervals disappear. Repeated scans cost quadratic time, even with no holes. The bounded strategy uses tree searches; Earcut finds easy local ears and wins on this family.

Stacked holes: bad for Earcut

A rectangle containing a vertical stack of small rectangular holes produces sharply increasing Earcut times. Quadrupling the hole count increases its measured time about 60–69×. This suggests cubic growth over these sizes; we have not proved an asymptotic lower bound or isolated the dominant internal stage.

C++ median timings in milliseconds for one domain, with 12 warmed samples. All reported outputs pass exact coverage checks. An exact dyadic shear resolves x-coordinate ties.

DomainVerticesTriage default (ms)Triage bounded (ms)Earcut (ms)
Comb, no holes655401452.15936.1632.774
64 stacked holes2600.5720.2400.667
256 stacked holes10282.5761.18939.070
1,024 stacked holes410014.1055.2602691.557

These original measurements use the previous C++ bounded backend, before the array-tree optimization. It is about 40× faster than default Triage on the largest comb, while Earcut remains much faster there. At 1,024 stacked holes, it is about 512× faster than Earcut. The largest Earcut runs were stopped or omitted; no missing timings are extrapolated.

Both families, all sizes, Julia results, and reproduction commands ↗

04 / GET STARTED

Two implementations.
The same geometry.

C++17

Header-only · Boost headers
#include <triage/triage.hpp>

std::vector<triage::Point> points{
    {0,0}, {4,0}, {5,4}, {1,5},
    {1.5,1}, {2,2}, {3,1}
};
auto mesh = triage::triangulate(
    points, {0,4,7});

Zero-based indices. Flat coordinate storage.

Julia

Native Julia · no runtime dependencies
using Triage

points = Point[
    (0,0), (4,0), (5,4), (1,5),
    (1.5,1), (2,2), (3,1)
]
triangles = triangulate(
    points, [1,5,8])

One-based indices. Inline coordinate tuples.

Call triangulate_bounded explicitly to select the optional strategy in either language. It is available on main; the earlier v0.1.0 release predates this API.

05 / CHECKS & SCOPE

Vibe programming.
Explicit verification.

Created using Codex, with the algorithms, tests, scripts, and measurements available for inspection.

117,425 certified domains. The bounded C++ and Julia implementations produce byte-identical meshes on 117,415 corpus domains and ten adversarial domains. Independent exact-arithmetic checks certify orientation and boundary coverage. ASan/UBSan passed 118,708 generated and corpus cases. The default still reproduces every published corpus mesh.

Input assumptions matter. Triage expects simple boundaries and disjoint interior holes. The current chain path requires distinct x coordinates. It does not implement Earcut’s malformed-input recovery. The default can incur quadratic work; the optional bounded strategy guarantees O(n log n) arithmetic operations under the same input assumptions.

Read the input format and limitations ↗