Earcut
The fastest and smallest JavaScript polygon triangulation library. 2.5KB gzipped.
The algorithm
The library implements a modified ear slicing algorithm, optimized by zorder curve hashing and extended to handle holes, twisted polygons, degeneracies and selfintersections 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 IndustrialStrength Triangulation of Polygons by Martin Held and Triangulation by Ear Clipping by David Eberly.
Why another triangulation library?
The aim of this project is to create a JS triangulation library that is fast enough for realtime triangulation in the browser, sacrificing triangulation quality for raw speed and simplicity, while being robust enough to handle most practical datasets without crashing or producing garbage. Some benchmarks using Node 0.12:
(ops/sec)  pts  earcut  libtess  poly2tri  pnltri  polyk 

OSM building  15  795,935  50,640  61,501  122,966  175,570 
dude shape  94  35,658  10,339  8,784  11,172  13,557 
holed dude shape  104  28,319  8,883  7,494  2,130  n/a 
complex OSM water  2523  543  77.54  failure  failure  n/a 
huge OSM water  5667  95  29.30  failure  failure  n/a 
The original use case it was created for is Mapbox GL, WebGLbased interactive maps.
If you want to get correct triangulation even on very bad data with lots of selfintersections and earcut is not precise enough, take a look at libtess.js.
Usage
var triangles = earcut([10,0, 0,50, 60,60, 70,10]); // returns [1,0,3, 3,2,1]
Signature: 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 12vertex 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).
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]);
// [3,0,4, 5,4,0, 3,4,7, 5,0,1, 2,3,7, 6,5,1, 2,7,6, 6,1,2]
// triangulating a polygon with 3d coords
earcut([10,0,1, 0,50,2, 60,60,3, 70,10,4], null, 3);
// [1,0,3, 3,2,1]
If you pass a single vertex as a hole, Earcut treats it as a Steiner point.
If your input is a multidimensional array (e.g. GeoJSON Polygon),
you can convert it to the format expected by Earcut with earcut.flatten
:
var data = earcut.flatten(geojson.geometry.coordinates);
var triangles = earcut(data.vertices, data.holes, data.dimensions);
After getting a triangulation, you can verify its correctness with earcut.deviation
:
var deviation = earcut.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.
Install
NPM and Browserify:
npm install earcut
Browser builds on CDN:
Running tests:
npm test
Ports to other languages
 mapbox/earcut.hpp (C++11)
 earcut4j/earcut4j (Java)
 the3deers/earcutjava (Java)
 Larpon/earcut (V)
 Cawfree/earcutj (Java, outdated)
Changelog
2.2.2 (Jan 21, 2020)
 Fixed yet another rare race condition when a hole shared an edge with an outer ring.
2.2.1 (Sep 19, 2019)
 Fixed another rare case with touching holes.
2.2.0 (Sep 18, 2019)
 Fixed a handful of rare race conditions.
2.1.5 (Feb 5, 2019)
 Fixed a race condition with coincident holes that could lead to bad triangulation.
2.1.4 (Dec 4, 2018)
 Fixed a race condition that could lead to a freeze on degenerate input.
2.1.3 (Jan 4, 2018)
 Improved performance for bigger inputs (512%).
2.1.2 (Oct 23, 2017)
 Fixed a few race conditions where bad input would cause an error.
2.1.1 (Mar 17, 2016)
 Fixed a rare race condition where the split routine would choose bad diagonals.
 Fixed a rare race condition in the "cure local intersections" routine.
 Fixed a rare race condition where a hole that shares a point with the outer ring would be handled incorrectly.
 Fixed a bug where a closing point wouldn't be filtered as duplicate, sometimes breaking triangulation.
2.1.0 (Mar 11, 2016)
 Added
earcut.deviation
function for verifying correctness of triangulation.  Added
earcut.flatten
function for converting GeoJSONlike input into a format Earcut expects.
2.0.9 (Mar 10, 2016)
 Fixed a rare race condition where a hole would be handled incorrectly.
2.0.8 (Jan 19, 2016)
 Fixed a rare race condition with a hole touching outer ring.
2.0.7 (Nov 18, 2015)
 Changed the algorithm to avoid filtering colinear/duplicate vertices unless it can't triangulate the polygon otherwise. Improves performance on simpler shapes and fixes some 3D use cases.
2.0.6 (Oct 26, 2015)
 Improved robustness and reliability of the triangulation algorithm.
 Improved performance by up to 15%.
 Significantly improved source code clarity.
2.0.5 (Oct 12, 2015)
 Fixed a zcurve hashing bug that could lead to unexpected results in very rare cases involving shapes with lots of points.
2.0.4 (Oct 8, 2015)
 Fixed one more extremely rare race condition, lol!
2.0.3 (Oct 8, 2015)
 Fixed yet another rare race condition (multiple holes connected with colinear bridges).
 Fixed crash on empty input.
2.0.2 (Jul 8, 2015)
 Fixed one more rare race condition with a holed polygon.
2.0.1 (May 11, 2015)
 Added Steiner points support.
2.0.0 (Apr 30, 2015)
 Breaking: changed the API to accept a flat input array of vertices with hole indices and return triangle indices. It makes the indexed output much faster than it was before (up to 30%) and improves memory footprint.
1.4.2 (Mar 18, 2015)
 Fixed another rare edge case with a tiny hole in a huge polygon.
1.4.1 (Mar 17, 2015)
 Fixed a rare edge case that led to incomplete triangulation.
1.4.0 (Mar 9, 2015)
 Fixed indexed output to produce indices not multiplied by dimension and work with any number of dimensions.
1.3.0 (Feb 24, 2015)
 Added a second argument to
earcut
that switches output format to flat vertex and index arrays if set totrue
.
1.2.3 (Feb 10, 2015)
 Improved performance (especially on recent v8) by avoiding
Array
push
with multiple arguments.
1.2.2 (Jan 27, 2015)
 Significantly improved performance for polygons with selfintersections (e.g. big OSM water polygons are now handled 23x faster)
1.2.1 (Jan 26, 2015)
 Significantly improved performance on polygons with high number of vertices by using zorder curve hashing for vertex lookup.
 Slightly improved overall performance with better point filtering.
1.1.0 (Jan 21, 2015)
 Improved performance on polygons with holes by switching from Held to Eberly hole elimination algorithm
 More robustness fixes and tests
1.0.1 — 1.0.6 (Jan 20, 2015)
 Various robustness improvements and fixes.
1.0.0 (Jan 18, 2015)
 Initial release.