Package Exports
- earcut
This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (earcut) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.
Readme
Earcut
The fastest and smallest JavaScript polygon triangulation library. 2.3KB gzipped.
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 like geographical shapes.
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:
| (ops/sec) | pts | earcut | libtess | poly2tri | pnltri |
|---|---|---|---|---|---|
| OSM building | 15 | 580,351 | 27,832 | 28,151 | 216,352 |
| dude shape | 94 | 29,848 | 6,194 | 3,575 | 13,027 |
| holed dude shape | 104 | 18,688 | 5,428 | 3,378 | 2,264 |
| complex OSM water | 2523 | 445 | 63.72 | failure | failure |
| huge OSM water | 5667 | 80.09 | 23.73 | failure | failure |
Earcut may be slow for huge complex shapes, but when it comes to triangulating lots of shapes with relatively low number of vertices on average (the use case earcut was created for), it's much faster.
If you want a library that is more likely to produce correct triangulation even on very bad data, libtess.js is certainly the best choice.
Usage
// input should be an array of rings, where the first is outer ring and others are holes;
// each ring is an array of points, where each point is of the `[x, y]` form
var points = [[[10, 0], [0, 50], [60, 60], [70, 10]]];
var trianglePoints = earcut(points);
// returns an array of points where each group of three forms a triangleInstall
NPM and Browserify:
npm install earcutBrowser builds:
npm install
npm run build-dev # builds dist/earcut.dev.js, a dev version with a source map
npm run build-min # builds dist/earcut.min.js, a minified production buildRunning tests:
npm test
Changelog
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 vertice 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.