earclip 1.0.0

Triangle mesh designed to be fast, efficient, and sphere capable.
Documentation

earclip GitHub Actions Workflow Status npm downloads bundle docs-ts docs-rust doc-coverage code-coverage Discord

About

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

Install

# NPM
npm install earcut
# PNPM
pnpm add earcut
# Yarn
yarn add earcut
# Bun
bun 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)

const polyAsPoints = [
    [{ x: 3506, y: -2048 },{ x: 7464, y: 402 },{ x: -2048, y: 2685 },{ x: -2048, y: -2048 },{ 3506, y: -2048 }],
    [{ x: -2048, y: -37 },{ x: 1235, y: 747 },{ x: 338, y: -1464 },{ x: -116, y: -1188 },{ x: -2048, y: -381 },{ x: -2048, y: -37 }],
    [{ x: -1491, y: -1981 },{ x: -1300, y: -1800 },{ x: -1155, y: -1981 },{ x: -1491, y: -1981 }],
]
const res2 = earclip(polyAsPoints, modulo)

assert(res === res2)

Development

Requirements

You need the tool tarpaulin to generate the coverage report. Install it using the following command:

cargo install cargo-tarpaulin

The bacon coverage tool is used to generate the coverage report. To utilize the pycobertura package for a prettier coverage report, install it using the following command:

pip install pycobertura

Running Tests

To run the tests, use the following command:

# TYPESCRIPT
## basic test
bun run test
## live testing
bun run test:dev

# RUST
## basic test
cargo test
# live testing
bacon test

Generating Coverage Report

To generate the coverage report, use the following command:

cargo tarpaulin
# bacon
bacon coverage # or type `l` inside the tool