earcut

What is earcut?

The earcut npm package is a JavaScript library for triangulating polygons for WebGL rendering. It is a fast, lightweight, and robust library for polygon triangulation, which is the process of converting polygons into triangles that can be used for rendering 3D graphics.

What are earcut's main functionalities?

Polygon Triangulation

This feature allows you to triangulate a polygon with or without holes. The 'vertices' array contains the x and y coordinates of the polygon's vertices, 'holes' is an array of indices that mark the start of each hole in the vertex array, and 'dimensions' is the number of coordinates per vertex (2 for 2D polygons). The 'earcut' function returns an array of indices that map to the triangulated vertices.

const earcut = require('earcut');
const vertices = [10, 0, 0, 50, 60, 60, 70, 10];
const holes = [4];
const dimensions = 2;
const triangles = earcut(vertices, holes, dimensions);

Other packages similar to earcut

poly2tri

poly2tri is another polygon triangulation library for use with WebGL. Unlike earcut, which uses a modified ear clipping algorithm, poly2tri implements a constrained Delaunay triangulation algorithm. It can handle complex polygons with holes and is robust in handling degenerate cases, but it may be slower than earcut for simple polygons.

trianglify

trianglify is a library for generating colorful triangle meshes that can be used as SVG backgrounds. While it also performs triangulation, its primary focus is on creating aesthetically pleasing patterns rather than providing a robust triangulation tool for 3D rendering.

README

Earcut

The fastest and smallest JavaScript polygon triangulation library. 2.3KB 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 like geographical shapes.

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:

(ops/sec)	pts	earcut	libtess	poly2tri	pnltri
OSM building	15	580,351	27,832	28,151	216,352
dude shape	94	29,848	6,194	3,575	13,027
holed dude shape	104	18,688	5,428	3,378	2,264
complex OSM water	2523	445	63.72	failure	failure
huge OSM water	5667	80.09	23.73	failure	failure

Earcut may be slow for huge complex shapes, but when it comes to triangulating lots of shapes with relatively low number of vertices on average (the use case earcut was created for), it's much faster.

If you want a library that is more likely to produce correct triangulation even on very bad data, libtess.js is certainly the best choice.

Usage

// 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]` form
var points = [[[10, 0], [0, 50], [60, 60], [70, 10]]];

var trianglePoints = earcut(points);
// returns an array of points where each group of three forms a triangle

Install

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

Changelog

1.2.2 (Jan 27, 2015)

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

1.2.1 (Jan 26, 2015)

• 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.

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.