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:
|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, 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]); // returns [1,0,3, 3,2,1]
earcut(vertices[, holes, dimensions = 2]).
verticesis a flat array of vertex coordinates like
[x0,y0, x1,y1, x2,y2, ...].
holesis 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).
dimensionsis the number of coordinates per vertex in the input array (
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], ); // [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 multi-dimensional array (e.g. GeoJSON Polygon),
you can convert it to the format expected by Earcut with
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
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.
NPM and Browserify:
npm install earcut
Browser builds on CDN:
earcut.deviationfunction for verifying correctness of triangulation.
earcut.flattenfunction for converting GeoJSON-like input into a format Earcut expects.
earcutthat switches output format to flat vertex and index arrays if set to
pushwith multiple arguments.