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

The library implements a modified ear slicing algorithm, optimized by z-order curve 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.

The aim of this project is to create a JS triangulation library that is fast enough for real-time 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:

The original use case it was created for is Mapbox GL, WebGL-based interactive maps.

If you want to get correct triangulation even on very bad data with lots of self-intersections and earcut is not precise enough, take a look at libtess.js.

var triangles = earcut([[[10,0],[0,50],[60,60],[70,10]]]);
// [[0,50],[10,0],[70,10], [70,10],[60,60],[0,50]]

Input should be an array of rings, where the first is outer ring and others are holes; each ring is an array of points, where each point is of the [x, y] or [x, y, z] form.

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

Alternatively, you can get triangulation results in the form of flat index and vertex arrays by passing true as a second argument to earcut (convenient for uploading results directly to WebGL as buffers):

var triangles = earcut([[[10,0],[0,50],[60,60],[70,10]]], true);
// {vertices: [0,50, 10,0, 70,10, 60,60], indices: [1,0,2, 3,2,1]}

NPM and Browserify:

npm install earcut

Browser builds:

npm install
npm run build-dev # builds dist/earcut.dev.js, a dev version with a source map
npm run build-min # builds dist/earcut.min.js, a minified production build

Running tests:

npm test

• mapbox/earcut.hpp (C++11)
• Cawfree/earcut-j (Java)

• Fixed another rare edge case with a tiny hole in a huge polygon.

• Fixed a rare edge case that led to incomplete triangulation.

• Fixed indexed output to produce indices not multiplied by dimension and work with any number of dimensions.

• Added a second argument to earcut that switches output format to flat vertex and index arrays if set to true.

• Improved performance (especially on recent v8) by avoiding Array push with multiple arguments.

• Significantly improved performance for polygons with self-intersections (e.g. big OSM water polygons are now handled 2-3x faster)

• Significantly improved performance on polygons with high number of vertices by using z-order curve hashing for vertice lookup.
• Slightly improved overall performance with better point filtering.

• Improved performance on polygons with holes by switching from Held to Eberly hole elimination algorithm
• More robustness fixes and tests

• Various robustness improvements and fixes.

• Initial release.