mourner / Seidel
Programming Languages
The project is now obsolete an superceded by Earcut triangulation library, which is much faster and more robust. The description below is now outdated.
Seidel's polygon triangulation
The fastest and smallest JavaScript polygon triangulation library for your WebGL apps, based on Seidel's incremental randomized algorithm. 2.7KB gzipped.
Initially ported from earlier versions of poly2tri by Mason Green, it since has been heavily optimized and improved.
Usage
var points = [[[10, 0], [0, 50], [60, 60], [70, 10]]];
seidel(points); // returns an array of triangles (arrays of 3 point objects each)
The library only supports strictly simple polygons with holes (no intersecting/overlapping edges). If you need to support weak/complex polygons, preprocess your data with JS Clipper.
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.
Benchmarks show that its by far the fastest among JS triangulation libraries, in addition to being the smallest and simplest:
| (ops/sec) | points | seidel | poly2tri | libtess | fastest vs 2nd fastest |
|---|---|---|---|---|---|
| OSM building | 15 | 80,250 | 28,426 | 22,542 | seidel vs poly2tri, 182% faster |
| dude shape | 94 | 10,212 | 3,725 | 4,504 | seidel vs libtess, 127% faster |
| nazca monkey | 1204 | 616 | 263 | 335 | seidel vs libtess, 84% faster |
Browser builds
npm install
npm run build-dev # builds dist/seidel.dev.js, a dev version with a source map
npm run build-min # builds dist/seidel.min.js, a minified production build
