Catches the C++ port up to earcut.js v3.2.3 (from the v2.2.x baseline), with faster triangulation, optional Delaunay refinement, and a fully modernized build.
Added
mapbox::refine()— optional Delaunay post-pass that legalizes interior edges in place, removing skinny triangles while preserving the boundary, holes, triangle count, and index format. Opt-in; adds ~98 ms over the benchmark below and costs nothing otherwise.- MVT benchmark over 119,680 real-world polygons (1.9M vertices), plus a correctness net over the full fixture set.
- earcut + refine view mode in the visualizer.
Changed
- Bit-identical parity with earcut.js v3.2.3, verified against the upstream fixtures.
- ~2× faster — the full MVT set (above) now triangulates in ~276 ms on a MacBook Pro M1 Pro, down from 572 ms pre-optimization. Wins come from a block-index acceleration for holes, replacing the z-order merge sort with
std::sort, and hot-path microoptimizations. - Dependencies (GoogleTest, Google Benchmark, GLFW, libtess2) and test fixtures now fetched via CMake
FetchContent— no submodules, plain clone builds out of the box. - Fixtures read from the JS repo at runtime instead of hand-transcribed C++, keeping the port in lockstep with upstream.
- Rewritten README (Performance, Robustness, Refinement, Visualizer sections) and refreshed logo.
- Hardened CI: dependency caching, sanitizer + coverage jobs, clang-format check,
-Werroracross all jobs.
Compatibility
Header-only and drop-in — copy include/mapbox/earcut.hpp as before; the mapbox::earcut<N>(polygon) API is unchanged. The test/bench/viz tree now requires C++17.