earclip

About

The fastest and smallest JavaScript polygon triangulation library with builtin tesselation. 2.9 kB minified and gzipped.

Install

# NPM
npm install earcut
# PNPM
pnpm add earcut
# Yarn
yarn add earcut

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

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

import { earclip } from 'earclip'

const poly = [[[3506,-2048],[7464,402],[-2048,2685],[-2048,-2048],[3506,-2048]],[[-2048,-37],[1235,747],[338,-1464],[-116,-1188],[-2048,-381],[-2048,-37]],[[-1491,-1981],[-1300,-1800],[-1155,-1981],[-1491,-1981]]]
const modulo = 8192 / 2

const res = earclip(poly, modulo)
console.log(res)