1 | ## Earcut
|
2 |
|
3 | The fastest and smallest JavaScript polygon triangulation library. 2.5KB gzipped.
|
4 |
|
5 | [![Build Status](https://travis-ci.org/mapbox/earcut.svg?branch=master)](https://travis-ci.org/mapbox/earcut)
|
6 | [![Coverage Status](https://coveralls.io/repos/mapbox/earcut/badge.svg?branch=master)](https://coveralls.io/r/mapbox/earcut?branch=master)
|
7 | [![Average time to resolve an issue](http://isitmaintained.com/badge/resolution/mapbox/earcut.svg)](http://isitmaintained.com/project/mapbox/earcut "Average time to resolve an issue")
|
8 | [![Percentage of issues still open](http://isitmaintained.com/badge/open/mapbox/earcut.svg)](http://isitmaintained.com/project/mapbox/earcut "Percentage of issues still open")
|
9 |
|
10 | #### The algorithm
|
11 |
|
12 | The library implements a modified ear slicing algorithm,
|
13 | optimized by [z-order curve](http://en.wikipedia.org/wiki/Z-order_curve) hashing
|
14 | and extended to handle holes, twisted polygons, degeneracies and self-intersections
|
15 | in a way that doesn't _guarantee_ correctness of triangulation,
|
16 | but attempts to always produce acceptable results for practical data.
|
17 |
|
18 | It's based on ideas from
|
19 | [FIST: Fast Industrial-Strength Triangulation of Polygons](http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html) by Martin Held
|
20 | and [Triangulation by Ear Clipping](http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf) by David Eberly.
|
21 |
|
22 | #### Why another triangulation library?
|
23 |
|
24 | The aim of this project is to create a JS triangulation library
|
25 | that is **fast enough for real-time triangulation in the browser**,
|
26 | sacrificing triangulation quality for raw speed and simplicity,
|
27 | while being robust enough to handle most practical datasets without crashing or producing garbage.
|
28 | Some benchmarks using Node 0.12:
|
29 |
|
30 | (ops/sec) | pts | earcut | libtess | poly2tri | pnltri | polyk
|
31 | ------------------| ---- | --------- | -------- | -------- | --------- | ------
|
32 | OSM building | 15 | _640,635_ | _50,640_ | _61,501_ | _122,966_ | _175,570_
|
33 | dude shape | 94 | _34,379_ | _10,339_ | _8,784_ | _11,172_ | _13,557_
|
34 | holed dude shape | 104 | _26,849_ | _8,883_ | _7,494_ | _2,130_ | n/a
|
35 | complex OSM water | 2523 | _564_ | _77.54_ | failure | failure | n/a
|
36 | huge OSM water | 5667 | _116_ | _29.30_ | failure | failure | n/a
|
37 |
|
38 | The original use case it was created for is [Mapbox GL](https://www.mapbox.com/mapbox-gl), WebGL-based interactive maps.
|
39 |
|
40 | If you want to get correct triangulation even on very bad data with lots of self-intersections
|
41 | and earcut is not precise enough, take a look at [libtess.js](https://github.com/brendankenny/libtess.js).
|
42 |
|
43 | #### Usage
|
44 |
|
45 | ```js
|
46 | var triangles = earcut([10,0, 0,50, 60,60, 70,10]); // returns [1,0,3, 3,2,1]
|
47 | ```
|
48 |
|
49 | Signature: `earcut(coords[, holeIndices, numDimensions = 2])`.
|
50 |
|
51 | * `coords` is a flat array of vertice coordinates like `[x0,y0, x1,y1, x2,y2, ...]`.
|
52 | * `holeIndices` is an array of hole indices if any
|
53 | (e.g. `[5, 8]` for a 12-vertice input would mean one hole with vertices 5–7 and another with 8–11).
|
54 | * `numDimensions` is the number of coordinates per vertice in the input array (`2` by default).
|
55 |
|
56 | Each group of three vertice indices in the resulting array forms a triangle.
|
57 |
|
58 | ```js
|
59 | // triangulating a polygon with a hole
|
60 | earcut([0,0, 100,0, 100,100, 0,100, 20,20, 80,20, 80,80, 20,80], [4]);
|
61 | // [3,0,4, 5,4,0, 3,4,7, 5,0,1, 2,3,7, 6,5,1, 2,7,6, 6,1,2]
|
62 |
|
63 | // triangulating a polygon with 3d coords
|
64 | earcut([10,0,1, 0,50,2, 60,60,3, 70,10,4], null, 3);
|
65 | // [1,0,3, 3,2,1]
|
66 | ```
|
67 |
|
68 | If your input is a multi-dimensional array (e.g. [GeoJSON Polygon](http://geojson.org/geojson-spec.html#polygon)),
|
69 | you can convert it to the format expected by Earcut with [a couple lines of codes](viz/viz.js#L99-L115).
|
70 |
|
71 | If you pass a single vertice as a hole, Earcut treats it as a Steiner point.
|
72 |
|
73 | #### Install
|
74 |
|
75 | NPM and Browserify:
|
76 |
|
77 | ```bash
|
78 | npm install earcut
|
79 | ```
|
80 |
|
81 | Browser builds:
|
82 |
|
83 | ```bash
|
84 | npm install
|
85 | npm run build-dev # builds dist/earcut.dev.js, a dev version with a source map
|
86 | npm run build-min # builds dist/earcut.min.js, a minified production build
|
87 | ```
|
88 |
|
89 | Running tests:
|
90 |
|
91 | ```bash
|
92 | npm test
|
93 | ```
|
94 |
|
95 | ![](https://cloud.githubusercontent.com/assets/25395/5778431/e8ec0c10-9da3-11e4-8d4e-a2ced6a7d2b7.png)
|
96 |
|
97 | #### Ports to other languages
|
98 |
|
99 | - [mapbox/earcut.hpp](https://github.com/mapbox/earcut.hpp) (C++11)
|
100 | - [Cawfree/earcut-j](https://github.com/Cawfree/earcut-j) (Java)
|
101 |
|
102 | #### Changelog
|
103 |
|
104 | ##### 2.0.4 (Oct 8, 2015)
|
105 |
|
106 | - Fixed one more extremely rare race condition, lol!
|
107 |
|
108 | ##### 2.0.3 (Oct 8, 2015)
|
109 |
|
110 | - Fixed yet another rare race condition (multiple holes connected with colinear bridges).
|
111 | - Fixed crash on empty input.
|
112 |
|
113 | ##### 2.0.2 (Jul 8, 2015)
|
114 |
|
115 | - Fixed one more rare race condition with a holed polygon.
|
116 |
|
117 | ##### 2.0.1 (May 11, 2015)
|
118 |
|
119 | - Added Steiner points support.
|
120 |
|
121 | ##### 2.0.0 (Apr 30, 2015)
|
122 |
|
123 | - **Breaking**: changed the API to accept a flat input array of vertices with hole indices and return triangle indices.
|
124 | It makes the indexed output much faster than it was before (up to 30%) and improves memory footprint.
|
125 |
|
126 | ##### 1.4.2 (Mar 18, 2015)
|
127 |
|
128 | - Fixed another rare edge case with a tiny hole in a huge polygon.
|
129 |
|
130 | ##### 1.4.1 (Mar 17, 2015)
|
131 |
|
132 | - Fixed a rare edge case that led to incomplete triangulation.
|
133 |
|
134 | ##### 1.4.0 (Mar 9, 2015)
|
135 |
|
136 | - Fixed indexed output to produce indices not multiplied by dimension and work with any number of dimensions.
|
137 |
|
138 | ##### 1.3.0 (Feb 24, 2015)
|
139 |
|
140 | - Added a second argument to `earcut` that switches output format to flat vertex and index arrays if set to `true`.
|
141 |
|
142 | ##### 1.2.3 (Feb 10, 2015)
|
143 |
|
144 | - Improved performance (especially on recent v8) by avoiding `Array` `push` with multiple arguments.
|
145 |
|
146 | ##### 1.2.2 (Jan 27, 2015)
|
147 |
|
148 | - Significantly improved performance for polygons with self-intersections
|
149 | (e.g. big OSM water polygons are now handled 2-3x faster)
|
150 |
|
151 | ##### 1.2.1 (Jan 26, 2015)
|
152 |
|
153 | - Significantly improved performance on polygons with high number of vertices
|
154 | by using z-order curve hashing for vertice lookup.
|
155 | - Slightly improved overall performance with better point filtering.
|
156 |
|
157 | ##### 1.1.0 (Jan 21, 2015)
|
158 |
|
159 | - Improved performance on polygons with holes by switching from Held to Eberly hole elimination algorithm
|
160 | - More robustness fixes and tests
|
161 |
|
162 | ##### 1.0.1 — 1.0.6 (Jan 20, 2015)
|
163 |
|
164 | - Various robustness improvements and fixes.
|
165 |
|
166 | ##### 1.0.0 (Jan 18, 2015)
|
167 |
|
168 | - Initial release.
|