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