Small polygons
Up to 64 vertices, without holes: ear cutting with a compact mask of live reflex vertices.
C++17 / JULIA / MIT LICENSE
Simple polygons. Interior holes. No added points.
Triage combines three algorithms to handle small polygons and large geographic boundaries.
Explore the codeStencil 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.
Faster than Earcut
on large geographic rings
Faster than Earcut
on geographic domains with holes
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
Up to 64 vertices, without holes: ear cutting with a compact mask of live reflex vertices.
Up to 32 total vertices: join a hole when it blocks an ear, then continue cutting.
Sweep monotone chains, insert diagonals between original vertices, and triangulate compact boundary ranges.
Read how chain-monotone triangulation works ↗
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
Compared with Mapbox Earcut on identical prepared inputs. Times are milliseconds for a whole batch; lower is better.
| Corpus | Polygons | C++ Triage (ms) | Julia Triage (ms) | Earcut C++ (ms) |
|---|---|---|---|---|
| Single-ring tiles | 111539 | 44.369 | 93.229 | 46.451 |
| Holed tiles | 5799 | 37.170 | 58.035 | 44.270 |
| Large geographic rings | 19 | 224.932 | 272.317 | 855.080 |
| Geographic domains with holes | 10 | 13.778 | 20.419 | 93.124 |
| Accepted named fixtures | 12 | 0.665 | 2.220 | 0.651 |
| Synthetic holed domains | 36 | 358.216 | 403.816 | 6386.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.
03 / ADVERSARIAL 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 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.
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.
| Domain | Vertices | Triage default (ms) | Triage bounded (ms) | Earcut (ms) |
|---|---|---|---|---|
| Comb, no holes | 65540 | 1452.159 | 36.163 | 2.774 |
| 64 stacked holes | 260 | 0.572 | 0.240 | 0.667 |
| 256 stacked holes | 1028 | 2.576 | 1.189 | 39.070 |
| 1,024 stacked holes | 4100 | 14.105 | 5.260 | 2691.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
#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.
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
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 ↗