poly-decomp

Convex decomposition in 2D

poly-decomp.js

Library for decomposing 2D polygons into convex regions.

Demo - Documentation

The library is a manual port of the C++ library Poly Decomp by Mark Bayazit.

It implements two algorithms, one optimal (but slow) and one less optimal (but fast).

// Create a concave polygon 
var concave = new decomp.Polygon();
concave.vertices.push([ -1,   1],
                      [ -1,   0],
                      [  1,   0],
                      [  1,   1],
                      [0.5, 0.5]);
 
// Decompose into convex polygons, using the faster algorithm 
var convexes1 = concave.quickDecomp();
 
// Decompose using the slow (but optimal) algorithm 
var convexes2 = concave.decomp();
 
// convexes1 and convexes2 are now arrays of Polygon objects. 

Download decomp.js and include the script in your HTML:

<script src="decomp.js" type="text/javascript"></script>

Until the code gets somewhat more stable, use the git url to install:

npm install git://github.com/schteppe/poly-decomp.js

Or add the dependency to your package.json:

    ...
    "dependencies" : {
        "poly-decomp" : "git://github.com/schteppe/poly-decomp.js"
    }
    ...

Then require it like so:

var decomp = require('poly-decomp');
  • Added method Polygon.prototype.removeCollinearPoints.
  • Added optional parameter thresholdAngle to Point.collinear(a,b,c,thresholdAngle).

Make sure you have git, Node.js, NPM and grunt installed.

git clone https://github.com/schteppe/poly-decomp.js.git; # Clone the repo
cd poly-decomp.js;
npm install;                                     # Install dependencies
                                                 # (make changes to source)
grunt;                                           # Builds build/decomp.js

The most recent commits are currently pushed to the master branch. Thanks for contributing!