Home

Awesome

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)pointsseidelpoly2trilibtessfastest vs 2nd fastest
OSM building1580,25028,42622,542seidel vs poly2tri, 182% faster
dude shape9410,2123,7254,504seidel vs libtess, 127% faster
nazca monkey1204616263335seidel 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