poly2tri.js

Based on the paper "Sweep-line algorithm for constrained Delaunay triangulation" by V. Domiter and and B. Zalik

Poly2Tri Copyright (c) 2009-2014, Poly2Tri Contributors
http://code.google.com/p/poly2tri/

poly2tri.js (JavaScript port) (c) 2009-2017, Poly2Tri Contributors
https://github.com/r3mi/poly2tri.js

This document describes the JavaScript version of poly2tri. Officially supported languages are C++ and Java : poly2tri.js is a community based port, currently based on the "May 1, 2013" C++ version, with patches and JavaScript specificities. You can ask support in the forum.

poly2tri.js is distributed with the same license as other poly2tri ports : the revised BSD License (3-clause BSD), see license.

Before using

Since there are no input validation of the data given for triangulation you need to think about this. poly2tri does not support repeated points within epsilon.

• If you have a cyclic function that generates random points make sure you don't add the same coordinate twice,
• If you are given input and aren't sure same point exist twice you need to check for this yourself,
• Only simple polygons are supported. You may add holes or interior Steiner points,
• Interior holes must not touch other holes, nor touch the polyline boundary,
• Use the library as described in the next paragraph.

Make sure you understand the preceding notice before posting an issue. If you have an issue not covered by the above, include your data-set with the problem.

If you want to triangulate complex or weak polygons, you will need to prepare your data with a polygon clipping library like Javascript Clipper.

You can test your dataset using the online JavaScript demo.

The only easy day was yesterday; have a nice day. -- Mason Green

Install

This module works on both Node.js and browsers.

For Node.js:

For TypeScript: poly2tri types (poly2tri.d.ts) are now directly bundled inside the NPM package, so that they can automatically be consumed from TypeScript applications. You do not need to install types separately from DefinitelyTyped or @types anymore.

For browsers, using Bower:

bower install --save poly2tri

For browsers, manually:

wget http://r3mi.github.io/poly2tri.js/dist/poly2tri.js

The file dist/poly2tri.js can be included directly. It is standalone and has no mandatory dependency. Use dist/poly2tri.min.js for the compressed version.

Usage

1. Get a reference to the library. Thanks to browserify, the module is in UMD format (Universal Module Definition), compatible with the various module systems:

   • CommonJS:

     var poly2tri = require('poly2tri');

   • TypeScript:

     import * as poly2tri from 'poly2tri';

   • RequireJS:

     require('poly2tri', function (poly2tri) {
         ...
     });

   • If you are not using a module system at all, you can access the package as a global variable poly2tri (or window.poly2tri in a browser).

2. Initialize CDT with a simple polyline (this defines the constrained edges)

   var contour = [
       new poly2tri.Point(100, 100),
       new poly2tri.Point(100, 300),
       new poly2tri.Point(300, 300),
       new poly2tri.Point(300, 100)
   ];
   var swctx = new poly2tri.SweepContext(contour);

3. Add holes if necessary (also simple polylines)

   var hole = [
       new poly2tri.Point(200, 200),
       new poly2tri.Point(200, 250),
       new poly2tri.Point(250, 250)
   ];
   swctx.addHole(hole);
   // or swctx.addHoles([hole1, hole2]) for multiple holes

4. Add Steiner points if necessary

   var point = new poly2tri.Point(150, 150);
   swctx.addPoint(point);
   // or swctx.addPoints([p1, p2, p3]) for multiple points

5. Triangulate

   swctx.triangulate();
   var triangles = swctx.getTriangles();

6. Use results

   triangles.forEach(function(t) {
       t.getPoints().forEach(function(p) {
           console.log(p.x, p.y);
       });
       // or t.getPoint(0), t.getPoint(1), t.getPoint(2)
   });

See index.html for a complete example.

Method calls can be chained:

var triangles = swctx.addHoles(holes).addPoints(points).triangulate().getTriangles();

Advanced Options

Error handling

The library methods throw an exception for invalid input data, such as duplicated or collinear points. The exception object will contain a points array attribute with the faulty data, if available.

Custom Point class

poly2tri.js supports using custom point class instead of poly2tri.Point. Any "Point like" object with {x, y} attributes is supported to initialize the SweepContext polylines and points (duck typing).

var contour = [{x:100, y:100}, {x:100, y:300}, {x:300, y:300}, {x:300, y:100}];
var swctx = new poly2tri.SweepContext(contour);

poly2tri.js might add extra fields to the point objects when computing the triangulation : they are prefixed with _p2t_ to avoid collisions with fields in the custom class.

Custom Point fields

The output triangles in getTriangles() have vertices which are references to the initial input points (not copies). Any custom fields in the initial points can be retrieved in the output triangles.

var contour = [{x:100, y:100, id:1}, {x:100, y:300, id:2}, {x:300, y:300, id:3}];
var swctx = new poly2tri.SweepContext(contour);
swctx.triangulate();
var triangles = swctx.getTriangles();
typeof triangles[0].getPoint(0).id
// → "number"

poly2tri.noConflict

Reverts the poly2tri global object back to its original value, and returns a reference to this poly2tri object.

var p = poly2tri.noConflict();

Displaying the samples

Install the dependent packages by running:

bower install

Use index.html (also available online as a demo) to display the result of a triangulation. Polygon contour, holes, and Steiner points can be added. Use any separator between points, e.g.

100 100
[100, 300, 300, 300]
(300;100)

is valid data to describe 4 points.

Some interesting samples can be interactively loaded using the "Load preset data" option menu. You can get additional files from the tests/data directory.

You need a modern browser to draw the results, supporting the HTML5 <canvas>.

Development

Install the dependent packages by running:

npm install

Build the release code in dist/ (library and demo) using:

npm run build
# or safer: npm run test 

The automated tests are built using jasmine, both for browser and for Node.js testing. Run the headless tests (JSHint, Node.js and PhantomJS) with:

npm test

Run all the browser tests (PhantomJS, Firefox, Safari and Chrome) with:

npm run test.browsers

Check JSHint and TSLint with:

npm run check

Performance tests

This jsPerf compares the performances across several versions of the module.

You can also run

npm run bench