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)