mapbox/earcut.hpp: header-only polygon triangulation that trades correctness for speed

A port of earcut.js, and the trade it makes

Earcut is a fast, header-only C++ port of earcut.js, which the README describes as the fastest and smallest JavaScript polygon triangulation library.

The lineage is worth spelling out, because the algorithm's reputation and its limits both come from it. The implementation uses a modified ear slicing algorithm, optimised by z-order curve and spatial hashing, and extended to handle holes, twisted polygons, degeneracies and self-intersections in a way that does not guarantee correctness of triangulation but attempts to always produce acceptable results for practical data. The ideas come from FIST, Fast Industrial-Strength Triangulation of Polygons by Martin Held, and Triangulation by Ear Clipping by David Eberly.

The trade is stated in one sentence near the top of the README. Earcut favors raw speed and simplicity over triangulation quality, while being tough enough to handle most practical datasets without crashing or producing garbage. Originally built for Mapbox GL, it is a good fit for real-time triangulation of geographical shapes and other practical data.

That is a coherent position for a rendering library. A renderer needs triangles that cover the shape and are cheap to produce, and it does not care whether the triangulation is the mathematically ideal one. A geometry library that has to survive arbitrary input is solving a different problem, and the README says so in the section on input assumptions later on.

Rings in, a flat index list out

The usage is compact and the type system does most of the explaining.

#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;

std::vector<N> indices = mapbox::earcut<N>(polygon);

The data model is ordinary. A polygon is a list of rings, the first is the outer boundary and the rest are holes, and the library is forgiving about ordering, since winding order does not matter and rings can be given in any order.

The output is a flat list of indices into the input vertices, numbered ring after ring, three per triangle. There is no output structure to speak of, no triangle objects, no half edge structure, which keeps the allocation count down and the interface trivial.

Two details are easy to get wrong and are spelled out in the comments. The vertex numbering runs ring after ring, so index 6 in the example above is `{25, 75}`, and the output triangles have a consistent winding regardless of the input, counter-clockwise in a y-up coordinate system and clockwise in a y-down or screen space system. If you need the opposite orientation, the answer is `std::reverse` on the result.

Any point type, through the nth accessor

The library does not require a specific point type. Earcut reads coordinates through the `nth` accessor, and the accessors for `std::tuple`, `std::pair` and `std::array` ship by default.

For anything else, you specialise the accessor, and the README gives the example with a custom integer point type:

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::util

Two specialisations, one per coordinate, and the type now works with the triangulation. This matters more than it first appears, because the alternative in a rendering pipeline is often to copy your geometry into a vector of arrays, which is a copy of every vertex on every frame if you are doing it per frame.

The containers are just as flexible. Any type that meets the Container requirements, meaning `size()`, `empty()` and `operator[]`, works in place of `std::vector`, so a packed ring buffer or a custom geometry container can be triangulated in place.

The one hard limit is dimensionality. Earcut works on a 2D plane and only x and y are used, so if you have three or more dimensions you must project onto a 2D surface before triangulation, or use a more suitable library for the task, and the README points at CGAL's 3D triangulation documentation for that case.

refine, the opt-in Delaunay post-pass

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.

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);

The contract is precise. It keeps the same number of triangles and the same index format, and it usually removes many skinny triangles and reduces total triangle edge length. Because it is a post-process, it does not affect the speed of normal `earcut` calls unless you explicitly call it.

The caveats are stated just as precisely, and they are the part to read. It assumes a valid manifold triangulation, such as the output of `earcut`, though any manifold triangle-index array works. It does not repair invalid polygon input and it does not make the mesh conforming. And it uses non-robust predicates, where 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.

That last point is the one to plan for. If you render with it, a not-quite-Delaunay edge is invisible. If you hash the output or compare it between a build and a reference, it is not.

The benchmark is published, and you can run it

The performance section states the workload precisely, which is what makes the number usable.

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 to 16, it triangulates the whole set in about 276 ms on a MacBook Pro M1 Pro from 2021, noticeably faster than the JS original, with the optional Delaunay refinement taking an additional 98 ms.

Two things are worth pulling out of that. The workload is not synthetic, it is vector tile data, which is the pathological case of many small polygons with holes and shared boundaries, and that is the case the z-order curve and spatial hashing were designed for. And the refinement cost is stated separately, so the two numbers together tell you what quality costs: roughly a third more time for a better triangulation.

The benchmark is included in the repository, and the README tells you to run it yourself with `./build/bench`. That matters more than the headline number, because a performance claim you can reproduce on your own data is worth more than a claim you cannot.

The repository itself is small, with an `include/` directory holding the header, a `test/` directory, a `CMakeLists.txt`, a `.clang-format` configuration and a `CODEOWNERS` file, which is what a header-only library that is consumed by vendoring should look like. There is no dependency to manage and no build to integrate unless you want the benchmark.

What earcut does not promise

The section on input assumptions is the most useful part of the README, and it is the reason this library is fast.

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, with rings that do not self-cross or overlap, holes that stay inside the outer ring, and no duplicate or zero-length edges. On input that breaks those assumptions the result can be noticeably wrong, with overlapping triangles, gaps, or triangles outside the polygon, so you should clean your input first if correctness matters.

For a guaranteed correct triangulation even on bad data, the README points at CGAL or libtess2, both of which are slower and larger.

The second limitation is conformity. The output is not conforming, a vertex may land in the middle of another triangle's edge, which is called a T-junction. The README is precise about the consequences. This is harmless for rendering but can break navmesh or FEM use, and if you need a conforming mesh you have to remove T-junctions in a post-process, with a link to a discussion in the project's issue tracker.

So the decision comes down to what you are producing. Triangles for a rasteriser, where coverage and speed are what matter, are the ideal output. Triangles for a navigation mesh or a finite element solver, where the mesh topology has to be valid for the algorithm downstream, are not, and in that case the correct choice is a library that does guarantee the result.

On the release state, the tags are v2.2.4 from 2022, v3.2.3 from 2026-07-03 and v3.2.4 from 2026-09-28, and the last push was on 2026-09-28, with the repository not archived and the licence ISC.

Editorial conclusion

Adopt earcut.hpp if you are triangulating polygon geometry for rendering at interactive rates, since the speed comes from a z-order curve and spatial hashing and the header-only form costs nothing to integrate. Do not adopt it where a guaranteed correct or conforming mesh is required, such as a navmesh or a finite element mesh, because the project states the output is not conforming and T-junctions can break those uses, and the refinement pass does not fix that. Verify first that your input polygons satisfy the assumptions the library makes, that rings do not self-cross or overlap and that holes stay inside the outer ring, and that you have cleaned the geometry yourself if correctness matters to you.

Frequently asked questions

Official sources

1. Issues
2. License: ISC
3. mapbox/earcut.hpp on GitHub
4. README
5. Releases