mapbox/earcut

Earcut

The fastest and smallest JavaScript polygon triangulation library. 4KB gzipped.

Earcut is designed to be fast enough for real-time triangulation in the browser, favoring 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 JS (WebGL-based interactive maps), it's now also used by Three.js and many other projects.

Demo

Usage

import earcut from 'earcut';
const triangles = earcut([10,0, 0,50, 60,60, 70,10]); // returns [1,0,3, 1,3,2]

Algorithm

The library 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.

Performance

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 ~445 ms on a MacBook Pro M1 Pro (2021), with optional Delaunay refinement taking additional ~168 ms. You can run the benchmark yourself with npm run bench.

Robustness

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. If correctness matters, clean your input first; for a guaranteed-correct triangulation even on bad data, see libtess.js (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.

Install

Install with NPM: npm install earcut, then import as a module:

import earcut, {flatten, deviation, refine} from 'earcut';

Or use as a module directly in the browser with jsDelivr:

<script type="module">
    import earcut from 'https://cdn.jsdelivr.net/npm/earcut/+esm';
</script>

Alternatively, there's a UMD browser bundle with an earcut global variable (exposing the main function as earcut.default):

<script src="https://cdn.jsdelivr.net/npm/earcut/dist/earcut.min.js"></script>

API

earcut(vertices[, holes, dimensions = 2])

• vertices is a flat array of vertex coordinates like [x0,y0, x1,y1, x2,y2, ...].
• holes is an array of hole indices if any (e.g. [5, 8] for a 12-vertex input would mean one hole with vertices 5–7 and another with 8–11).
• dimensions is the number of coordinates per vertex in the input array (2 by default). Earcut is a 2D algorithm: only x and y are used for triangulation, and any extra coordinates are ignored (3D data is treated as projected onto the XY plane).

Each group of three vertex indices in the resulting array forms a triangle.

// triangulating a polygon with a hole
earcut([0,0, 100,0, 100,100, 0,100,  20,20, 80,20, 80,80, 20,80], [4]);
// [0,4,7, 5,4,0, 5,0,1, 5,1,2, 3,0,7, 3,7,6, 6,5,2, 6,2,3]

// triangulating a polygon with 3d coords
earcut([10,0,1, 0,50,2, 60,60,3, 70,10,4], null, 3);
// [1,0,3, 1,3,2]

If you pass a single vertex as a hole, Earcut treats it as a Steiner point.

Output triangles always have a consistent winding order regardless of the input polygon's winding — counter-clockwise in a y-up coordinate system (clockwise in y-down/screen space). If you need the opposite orientation (e.g. for back-face culling or normals in 3D), call .reverse() on the result.

refine(triangles, vertices[, dimensions = 2])

If triangle quality matters, you can run an optional refinement pass after triangulation:

const triangles = earcut(vertices, holes, dimensions);
refine(triangles, vertices, dimensions);

This mutates triangles in place, legalizing interior edges with Delaunay flips 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.

Refinement is a post-process, so it doesn't affect the speed of normal earcut calls unless you explicitly call it. It assumes a valid manifold triangulation, such as the output of earcut, and doesn't repair invalid polygon input or make the mesh conforming.

flatten(data)

If your input is a multi-dimensional array (e.g. GeoJSON Polygon), you can convert it to the format expected by Earcut with flatten:

const data = flatten(geojson.geometry.coordinates);
const triangles = earcut(data.vertices, data.holes, data.dimensions);

deviation(vertices, holes, dimensions, triangles)

After getting a triangulation, you can verify its correctness with deviation:

const d = deviation(vertices, holes, dimensions, triangles);

Returns the relative difference between the total area of triangles and the area of the input polygon. 0 means the triangulation is fully correct.

Ports to other languages

• mapbox/earcut.hpp (C++11)
• JaffaKetchup/dart_earcut (Dart)
• earcut4j/earcut4j (Java)
• Larpon/earcut (V)
• measuredweighed/SwiftEarcut (Swift)
• goswinr/Earcut (F# / .NET)
• tenyoru/earcut.zig (Zig)
• MichaCo/Earcut (C# / .NET)