• Stars
    star
    2,174
  • Rank 21,215 (Top 0.5 %)
  • Language
    JavaScript
  • License
    ISC License
  • Created almost 10 years ago
  • Updated 4 months ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

The fastest and smallest JavaScript polygon triangulation library for your WebGL apps

Earcut

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

Build Status Coverage Status Average time to resolve an issue Percentage of issues still open

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

var 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:

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

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

var 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

NPM and Browserify:

npm install earcut

Browser builds on CDN:

Running tests:

npm test

Ports to other languages

Changelog

2.2.4 (Jul 5, 2022)
  • Improved performance by 10–15%.
  • Fixed another rare race condition that could lead to an infinite loop.
2.2.3 (Jul 8, 2021)
  • Fixed a rare race condition that could lead to an infinite loop.
2.2.2 (Jan 21, 2020)
  • Fixed yet another rare race condition when a hole shared an edge with an outer ring.
2.2.1 (Sep 19, 2019)
  • Fixed another rare case with touching holes.
2.2.0 (Sep 18, 2019)
  • Fixed a handful of rare race conditions.
2.1.5 (Feb 5, 2019)
  • Fixed a race condition with coincident holes that could lead to bad triangulation.
2.1.4 (Dec 4, 2018)
  • Fixed a race condition that could lead to a freeze on degenerate input.
2.1.3 (Jan 4, 2018)
  • Improved performance for bigger inputs (5-12%).
2.1.2 (Oct 23, 2017)
  • Fixed a few race conditions where bad input would cause an error.
2.1.1 (Mar 17, 2016)
  • Fixed a rare race condition where the split routine would choose bad diagonals.
  • Fixed a rare race condition in the "cure local intersections" routine.
  • Fixed a rare race condition where a hole that shares a point with the outer ring would be handled incorrectly.
  • Fixed a bug where a closing point wouldn't be filtered as duplicate, sometimes breaking triangulation.
2.1.0 (Mar 11, 2016)
  • Added earcut.deviation function for verifying correctness of triangulation.
  • Added earcut.flatten function for converting GeoJSON-like input into a format Earcut expects.
2.0.9 (Mar 10, 2016)
  • Fixed a rare race condition where a hole would be handled incorrectly.
2.0.8 (Jan 19, 2016)
  • Fixed a rare race condition with a hole touching outer ring.
2.0.7 (Nov 18, 2015)
  • Changed the algorithm to avoid filtering colinear/duplicate vertices unless it can't triangulate the polygon otherwise. Improves performance on simpler shapes and fixes some 3D use cases.
2.0.6 (Oct 26, 2015)
  • Improved robustness and reliability of the triangulation algorithm.
  • Improved performance by up to 15%.
  • Significantly improved source code clarity.
2.0.5 (Oct 12, 2015)
  • Fixed a z-curve hashing bug that could lead to unexpected results in very rare cases involving shapes with lots of points.
2.0.4 (Oct 8, 2015)
  • Fixed one more extremely rare race condition, lol!
2.0.3 (Oct 8, 2015)
  • Fixed yet another rare race condition (multiple holes connected with colinear bridges).
  • Fixed crash on empty input.
2.0.2 (Jul 8, 2015)
  • Fixed one more rare race condition with a holed polygon.
2.0.1 (May 11, 2015)
  • Added Steiner points support.
2.0.0 (Apr 30, 2015)
  • Breaking: changed the API to accept a flat input array of vertices with hole indices and return triangle indices. It makes the indexed output much faster than it was before (up to 30%) and improves memory footprint.
1.4.2 (Mar 18, 2015)
  • Fixed another rare edge case with a tiny hole in a huge polygon.
1.4.1 (Mar 17, 2015)
  • Fixed a rare edge case that led to incomplete triangulation.
1.4.0 (Mar 9, 2015)
  • Fixed indexed output to produce indices not multiplied by dimension and work with any number of dimensions.
1.3.0 (Feb 24, 2015)
  • Added a second argument to earcut that switches output format to flat vertex and index arrays if set to true.
1.2.3 (Feb 10, 2015)
  • Improved performance (especially on recent v8) by avoiding Array push with multiple arguments.
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 vertex 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.

More Repositories

1

mapbox-gl-js

Interactive, thoroughly customizable maps in the browser, powered by vector tiles and WebGL
JavaScript
10,264
star
2

pixelmatch

The smallest, simplest and fastest JavaScript pixel-level image comparison library
JavaScript
6,055
star
3

mapbox-gl-native

Interactive, thoroughly customizable maps in native Android, iOS, macOS, Node.js, and Qt applications, powered by vector tiles and OpenGL
C++
4,297
star
4

tippecanoe

Build vector tilesets from large collections of GeoJSON features.
C++
2,423
star
5

awesome-vector-tiles

Awesome implementations of the Mapbox Vector Tile specification
2,311
star
6

delaunator

An incredibly fast JavaScript library for Delaunay triangulation of 2D points
JavaScript
2,255
star
7

supercluster

A very fast geospatial point clustering library for browsers and Node.
JavaScript
2,061
star
8

robosat

Semantic segmentation on aerial and satellite imagery. Extracts features such as: buildings, parking lots, roads, water, clouds
Python
1,997
star
9

mapbox.js

Mapbox JavaScript API, a Leaflet Plugin
HTML
1,902
star
10

geojson.io

A quick, simple tool for creating, viewing, and sharing spatial data
JavaScript
1,740
star
11

geojson-vt

Slice GeoJSON into vector tiles on the fly in the browser
JavaScript
1,731
star
12

flamebearer

Blazing fast flame graph tool for V8 and Node πŸ”₯
JavaScript
1,634
star
13

maki

A POI Icon Set
JavaScript
1,475
star
14

polylabel

A fast algorithm for finding the pole of inaccessibility of a polygon (in JavaScript and C++)
C++
1,312
star
15

togeojson

convert KML and GPX to GeoJSON, without the fuss
JavaScript
1,185
star
16

mapbox-studio-classic

JavaScript
1,136
star
17

node-pre-gyp

Node.js tool for easy binary deployment of C++ addons
JavaScript
1,071
star
18

webgl-wind

Wind power visualization with WebGL particles
JavaScript
943
star
19

geobuf

A compact binary encoding for geographic data.
JavaScript
917
star
20

mapbox-navigation-ios

Turn-by-turn navigation logic and UI in Swift on iOS
Swift
861
star
21

earcut.hpp

Fast, header-only polygon triangulation
C
850
star
22

mapbox-gl-draw

Draw tools for mapbox-gl-js
JavaScript
827
star
23

Fingertips

Touch indicators on external displays for iOS applications.
Swift
809
star
24

XcodeClangFormat

Format code in Xcode 8+ with clang-format
Objective-C++
808
star
25

vector-tile-spec

Mapbox Vector Tile specification
805
star
26

pbf

A low-level, lightweight protocol buffers implementation in JavaScript.
JavaScript
746
star
27

mapbox-android-demo

Google Play demo app for the Mapbox Maps SDK for Android
Java
704
star
28

mbutil

Importer and Exporter of MBTiles
Python
694
star
29

osm-bright

A Carto template for OpenStreetMap data
CartoCSS
690
star
30

mapbox-unity-sdk

Mapbox Unity SDK - https://www.mapbox.com/unity/
C#
677
star
31

mapboxgl-jupyter

Use Mapbox GL JS to visualize data in a Python Jupyter notebook
Python
661
star
32

carto

fast CSS-like map stylesheets
JavaScript
653
star
33

mapbox-sdk-js

A JavaScript client to Mapbox services, supporting Node, browsers, and React Native
JavaScript
652
star
34

concaveman

A very fast 2D concave hull algorithm in JavaScript
JavaScript
640
star
35

leaflet-omnivore

universal format parser for Leaflet & Mapbox.js
JavaScript
625
star
36

mapbox-react-examples

Example patterns for building React apps with Mapbox GL JS
JavaScript
615
star
37

martini

A JavaScript library for real-time RTIN terrain mesh generation
JavaScript
609
star
38

polyline

polyline encoding and decoding in javascript
JavaScript
604
star
39

mapbox-navigation-android

Mapbox Navigation SDK for Android
Kotlin
572
star
40

mbtiles-spec

specification documents for the MBTiles tileset format
569
star
41

tiny-sdf

Browser-side SDF font generator
HTML
562
star
42

mapnik-vector-tile

Mapnik implemention of Mapbox Vector Tile specification
C++
546
star
43

storytelling

Storytelling with maps template
HTML
541
star
44

mapbox-gl-leaflet

binding from Mapbox GL JS to the Leaflet API
JavaScript
518
star
45

tilelive

fast interface to tiles with pluggable backends - NOT ACTIVELY MAINTAINED
JavaScript
514
star
46

cheap-ruler

Fast approximations for common geodesic measurements 🌐
JavaScript
416
star
47

mapbox-java

The Mapbox Java SDK – Java wrappers around Mapbox APIs and other location data
Java
403
star
48

jni.hpp

A modern, type-safe, header-only, C++14 wrapper for JNI
C++
388
star
49

mercantile

Spherical mercator tile and coordinate utilities
Python
381
star
50

mapbox-maps-android

Interactive, thoroughly customizable maps in native Android powered by vector tiles and OpenGL.
Kotlin
368
star
51

variant

C++11/C++14 Variant
C++
365
star
52

leaflet-image

leaflet maps to images
JavaScript
360
star
53

mapbox-gl-geocoder

Geocoder control for mapbox-gl-js using Mapbox Geocoding API
JavaScript
357
star
54

mbview

View mbtiles locally
EJS
353
star
55

csv2geojson

magically convert csv files to geojson files
JavaScript
353
star
56

mbxmapkit

DEPRECATED - Lightweight Mapbox integration with MapKit on iOS
Objective-C
336
star
57

DEPRECATED-mapbox-ios-sdk

REPLACED – use https://www.mapbox.com/ios-sdk instead
Objective-C
325
star
58

mapbox-sdk-py

Python SDK for Mapbox APIs **DEVELOPMENT IS TEMPORARILY PAUSED, SEE CONTRIBUTING.md**
Python
319
star
59

potpack

A tiny rectangle packing JavaScript library (for sprite layouts)
JavaScript
314
star
60

mapbox-maps-ios

Interactive, thoroughly customizable maps for iOS powered by vector tiles and Metal
Swift
313
star
61

vector-tile-js

Parses vector tiles with JavaScript
JavaScript
308
star
62

node-mbtiles

mbtiles utility, renderer, and storage backend for tilelive
JavaScript
285
star
63

mapbox-maps-flutter

Interactive, thoroughly customizable maps for Flutter powered by Mapbox Maps SDK
Swift
282
star
64

mapbox-ar-unity

DEPRECATED! A place to create/learn with Unity, ARKit/ARCore, and Mapbox!
C#
279
star
65

geo-googledocs

Tools to integrate Mapbox with Google Docs
JavaScript
276
star
66

delatin

A fast JavaScript terrain mesh generation tool based on Delaunay triangulation
JavaScript
273
star
67

hubdb

a github-powered database
JavaScript
272
star
68

flutter-mapbox-gl

Moved to https://github.com/tobrun/flutter-mapbox-gl
Java
271
star
69

mapbox-gl-styles

Prebuilt Mapbox GL styles for use in Mapbox GL JS or the Mapbox Mobile SDKs and as a starting point for custom maps built with Mapbox Studio
JavaScript
268
star
70

simplestyle-spec

A simple styling convention for GeoJSON data
266
star
71

postgis-vt-util

postgres helper functions for making vector tiles
PLpgSQL
265
star
72

gzip-hpp

Gzip header-only C++ library
C++
265
star
73

protozero

Minimalist protocol buffer decoder and encoder in C++
C++
261
star
74

sphericalmercator

Spherical Mercator math in Javascript
JavaScript
259
star
75

shp-write

create and write to shapefiles in pure javascript
JavaScript
254
star
76

geojsonhint

IMPORTANT: development of this project has been paused, see the README (Validate GeoJSON against the specification)
JavaScript
253
star
77

mason

Cross platform package manager for C/C++ apps
Python
252
star
78

wellknown

GeoJSON-emitting WKT parser for browsers and node
JavaScript
249
star
79

Hecate

Fast Geospatial Feature Storage API
Rust
247
star
80

pyskel

Skeleton of a Python package
Python
243
star
81

mapbox-plugins-android

Mapbox Android Plugins are a collection of libraries that extend our other SDKs, helping you design powerful mapping features while the plugins handle most of the heavy lifting.
Java
240
star
82

mapbox-gl-directions

Directions plugin for mapbox-gl-js using Mapbox Directions API.
JavaScript
236
star
83

tilejson-spec

JSON format for describing map tilesets.
234
star
84

mapping

OpenStreetMap contributions from the data team at Mapbox
JavaScript
233
star
85

tilebelt

simple tile utilities
JavaScript
230
star
86

geojson-merge

Merge multiple GeoJSON files into one FeatureCollection.
JavaScript
229
star
87

mapbox-arkit-ios

Utilities for combining Mapbox maps and location services with ARKit in your applications.
Swift
224
star
88

mapbox-scenekit

Swift
224
star
89

react-native-mapbox-ar

Location based augmented reality components using React Native, Viro and Mapbox
Objective-C
221
star
90

mapbox-gl-native-android

Interactive, thoroughly customizable maps in native Android powered by vector tiles and OpenGL
Java
211
star
91

mapbox-gl-native-ios

Interactive, thoroughly customizable maps for iOS powered by vector tiles and OpenGL
Objective-C++
211
star
92

Simple-KML

Simple KML is a simple & lightweight parsing library for KML written in Objective-C for the iOS platform.
Objective-C
208
star
93

turf-swift

A Swift language port of Turf.js.
Swift
205
star
94

react-colorpickr

A themeable colorpicker with HSL and RGB support for React
TypeScript
205
star
95

eternal

A C++14 compile-time/constexpr map and hash map with minimal binary footprint
C++
201
star
96

node-fontnik

Fonts β‡’ protobuf-encoded SDF glyphs
JavaScript
201
star
97

ecs-watchbot

Make robots do your work for you
JavaScript
194
star
98

leaflet-pip

point in polygon intersections for leaflet
JavaScript
194
star
99

tile-cover

Generate the minimum number of tiles to cover a geojson geometry
JavaScript
183
star
100

MapboxStatic.swift

Static map snapshots with overlays in Swift or Objective-C on iOS, macOS, tvOS, and watchOS
Swift
183
star