A fast, header-only C++ port of earcut.js, the fastest and smallest JavaScript polygon triangulation library.
Earcut favors raw speed and simplicity over triangulation quality, while being robust enough to handle most practical datasets without crashing or producing garbage, with an option to refine the result to Delaunay quality at a small cost. Originally built for Mapbox GL, it's a good fit for real-time triangulation of geographical shapes and other practical data.
It implements a modified ear slicing algorithm, optimized by z-order curve and spatial hashing and extended to handle holes, twisted polygons, degeneracies and self-intersections in a way that doesn't guarantee correctness of triangulation, but attempts to always produce acceptable results for practical data. It's based on ideas from FIST: Fast Industrial-Strength Triangulation of Polygons by Martin Held and Triangulation by Ear Clipping by David Eberly.
#include <earcut.hpp>// A point is any type with x/y accessors; std::array works out of the box.
using Point = std::array<double, 2>;
// A polygon is a list of rings. The first ring is the outer boundary; the rest are holes.
// Winding order doesn't matter, and rings can be given in any order.
std::vector<std::vector<Point>> polygon = {
{{100, 0}, {100, 100}, {0, 100}, {0, 0}}, // outer ring
{{75, 25}, {75, 75}, {25, 75}, {25, 25}}, // hole
};
// The index type. Defaults to uint32_t; pass uint16_t if your data never exceeds 65536 vertices.
using N = uint32_t;
// Triangulate. The result is a flat list of indices into the input vertices (numbered ring after
// ring, so index 6 is {25, 75} here), three per triangle. Output triangles have a consistent
// winding regardless of the input: counter-clockwise in a y-up coordinate system (clockwise in
// y-down/screen space). Call std::reverse on the result if you need the opposite orientation.
std::vector<N> indices = mapbox::earcut<N>(polygon);Earcut can triangulate a simple, planar polygon of any winding order including holes. It will even return a robust, acceptable solution for non-simple polygons. Earcut works on a 2D plane: only x and y are used, so if you have three or more dimensions, project them onto a 2D surface before triangulation, or use a more suitable library for the task (e.g. CGAL).
Any point type works as input — earcut reads coordinates through the nth accessor. Accessors for std::tuple, std::pair, and std::array ship by default; for a custom type (like Clipper's IntPoint), specialize nth for it:
struct IntPoint { int64_t X, Y; };
namespace mapbox { namespace util {
template <> struct nth<0, IntPoint> { static auto get(const IntPoint& p) { return p.X; } };
template <> struct nth<1, IntPoint> { static auto get(const IntPoint& p) { return p.Y; } };
}} // namespace mapbox::utilThe polygon and ring containers are just as flexible: any type that meets the Container requirements (size(), empty(), operator[]) works in place of std::vector.
If triangle quality matters, mapbox::refine is an opt-in post-pass that legalizes every interior edge in place with Delaunay flips, converging toward the constrained Delaunay triangulation while preserving the polygon boundary and holes. It keeps the same number of triangles and the same index format, but usually removes many skinny triangles and reduces total triangle edge length. Being a post-process, it doesn't affect the speed of normal earcut calls unless you explicitly call it.
std::vector<N> indices = mapbox::earcut<N>(polygon);
// coords is a random-access container of points indexed by vertex index — i.e. the input
// vertices concatenated ring after ring, in the same order earcut's returned indices refer to.
// indices is refined in place; the triangle count never changes.
mapbox::refine(indices, coords);It assumes a valid manifold triangulation, such as the output of earcut (though any manifold triangle-index array works), and reads coords through the same nth<0>/nth<1> accessors. It doesn't repair invalid polygon input or make the mesh conforming. Note also that refine uses non-robust predicates: float input is fine, and the worst case is a not-quite-Delaunay edge, never an invalid mesh — but unlike earcut it does not promise bit-identical output across compilers.
Earcut is heavily optimized for its primary workload — triangulating polygons from
Mapbox Vector Tiles. On a representative benchmark of
119,680 real-world polygons (1.9M vertices) drawn from a window of map tiles through zooms 4–16,
it triangulates the whole set in ~276 ms on a MacBook Pro M1 Pro (2021) — noticeably faster than
the JS original — with optional Delaunay refinement taking an additional ~98 ms. You can run the
benchmark yourself with ./build/bench.
Earcut does not guarantee a correct triangulation on arbitrary input — it trades quality for speed, aiming to always produce an acceptable result on practical data without crashing or emitting garbage. The input is assumed to be a valid polygon: rings that don't self-cross or overlap, holes that stay inside the outer ring, and no duplicate or zero-length edges. On input that breaks these assumptions the result can be noticeably wrong (overlapping triangles, gaps, or triangles outside the polygon), so clean your input first if correctness matters. For a guaranteed-correct triangulation even on bad data, use a library like CGAL or libtess2 (slower and larger).
The output is also not conforming — a vertex may land in the middle of another triangle's edge (a T-junction). This is harmless for rendering but can break navmesh or FEM use; if you need a conforming mesh, remove T-junctions in a post-process.
In case you just want to use the earcut triangulation library; copy and include the header file <earcut.hpp> in your project and follow the steps documented in the section Usage.
If you want to build the test, benchmark and visualization programs instead, follow these instructions:
Before you continue, make sure to have the following tools installed:
- git (Ubuntu/Windows/macOS)
- cmake 3.16+ (Windows/macOS/Linux)
- A C++17 compiler (GCC 9+, Clang 10+, or MSVC 2019+)
The test/benchmark dependencies (GoogleTest, Google Benchmark, and — for the visualizer — GLFW),
as well as the test fixtures, are fetched automatically at configure time via CMake's FetchContent,
so a plain (non-recursive) clone is all you need. The first configure needs network access to clone
them; set FETCHCONTENT_FULLY_DISCONNECTED=ON (or point FETCHCONTENT_SOURCE_DIR_<name> at a local
checkout) to build offline. The visualizer additionally needs an OpenGL SDK and is off by default.
git clone https://github.com/mapbox/earcut.hpp.git
cd earcut.hpp
cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j
# ./build/tests
# ./build/benchBuild options (all default to their common value): -DEARCUT_BUILD_TESTS=ON,
-DEARCUT_BUILD_BENCH=ON, -DEARCUT_BUILD_VIZ=OFF (needs OpenGL + GLFW),
-DEARCUT_WARNING_IS_ERROR=OFF.
CMake can also generate IDE projects (Visual Studio, Xcode, etc.) — e.g.
cmake -B build -G "Visual Studio 17 2022" — or import the folder directly in CLion / VS.
There's an interactive OpenGL viewer for inspecting the triangulation of the bundled test fixtures. It's off by default (it needs an OpenGL SDK and GLFW); enable and run it with:
cmake -B build -DCMAKE_BUILD_TYPE=Release -DEARCUT_BUILD_VIZ=ON
cmake --build build --target viz -j
./build/vizControls: ←/→ switch fixture, ↑/↓ switch tessellator (earcut / earcut + refine / scanline fill), F/M/O toggle fill/mesh/outline, WASD pan, +/− or scroll to zoom, R reset, Q/Esc quit.
This is currently based on earcut 3.2.3.