Awesome

Earcut

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

The algorithm

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.

Why another triangulation library?

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:

(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, 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.

Usage

const 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 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). Only two are used for triangulation (x and y), and the rest are ignored.

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.

Note that Earcut is a 2D triangulation algorithm, and handles 3D data as if it was projected onto the XY plane (with Z component ignored).

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

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

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

const 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

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

import earcut 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>