poly-decomp

poly-decomp.js
==============

Library for decomposing a 2D polygon into convex pieces.

!Decomposing a convcave polygon into convex regions

Launch the demo!

The library implements two algorithms, one optimal (but slow) and one less optimal (but fast).
It's is a manual port of the C++ library Poly Decomp by Mark Penner.

$3

##### Browser
Download decomp.js or decomp.min.js and include the script in your HTML:
``html



`

Then you can use the `decomp` global.

##### Node.js
`
npm install poly-decomp
`

Then require it like so:

`js
var decomp = require('poly-decomp');
`

$3


`js
// Create a concave polygon
var concavePolygon = [
[ -1, 1],
[ -1, 0],
[ 1, 0],
[ 1, 1],
[0.5, 0.5]
];

// Make sure the polygon has counter-clockwise winding. Skip this step if you know it's already counter-clockwise.
decomp.makeCCW(concavePolygon);

// Decompose into convex polygons, using the faster algorithm
var convexPolygons = decomp.quickDecomp(concavePolygon);

// ==> [ [[1,0],[1,1],[0.5,0.5]], [[0.5,0.5],[-1,1],[-1,0],[1,0]] ]

// Decompose using the slow (but optimal) algorithm
var convexPolygons = decomp.decomp(concavePolygon);

// ==> [ [[-1,1],[-1,0],[1,0],[0.5,0.5]], [[1,0],[1,1],[0.5,0.5]] ]
`

$3


`js
// Get user input as an array of points.
var polygon = getUserInput();

// Check if the polygon self-intersects
if(decomp.isSimple(polygon)){

// Reverse the polygon to make sure it uses counter-clockwise winding
decomp.makeCCW(polygon);

// Decompose into convex pieces
var convexPolygons = decomp.quickDecomp(polygon);

// Draw each point on an HTML5 Canvas context
for(var i=0; i var convexPolygon = convexPolygons[i];

ctx.beginPath();
var firstPoint = convexPolygon[0];
ctx.moveTo(firstPoint[0], firstPoint[1]);

for(var j=1; j var point = convexPolygon[j];
var x = point[0];
var y = point[1];
c.lineTo(x, y);
}
ctx.closePath();
ctx.fill();
}
}
`

$3

#### quickDecomp(polygon: Array<Point>): Array<Array<Point>>

`js
var convexPolygons = decomp.quickDecomp(polygon);
`

Slices the polygon into convex sub-polygons, using a fast algorithm. Note that the input points objects will be re-used in the result array.

#### decomp(polygon: Array<Point>): Array<Array<Point>>

`js
var convexPolygons = decomp.quickDecomp(polygon);
`

Decomposes the polygon into one or more convex sub-polygons using an optimal algorithm. Note that the input points objects will be re-used in the result array.

#### isSimple(polygon: Array<Point>): boolean

`js
if(decomp.isSimple(polygon)){
// Polygon does not self-intersect - it's safe to decompose.
var convexPolygons = decomp.quickDecomp(polygon);
}
`

Returns true if any of the line segments in the polygon intersects. Use this to check if the input polygon is OK to decompose.

#### makeCCW(polygon: Array<Point>): void

`js
console.log('Polygon with clockwise winding:', polygon);
decomp.makeCCW(polygon);
console.log('Polygon with counter-clockwise winding:', polygon);
`

Reverses the polygon, if its vertices are not ordered counter-clockwise. Note that the input polygon array will be modified in place.

#### removeCollinearPoints(polygon: Array<Point>, thresholdAngle: number): void

`js
var before = polygon.length;
decomp.removeCollinearPoints(polygon, 0.1);
var numRemoved = before - polygon.length;
console.log(numRemoved + ' collinear points could be removed');
`

Removes collinear points in the polygon. This means that if three points are placed along the same line, the middle one will be removed. The `thresholdAngle` is measured in radians and determines whether the points are collinear or not. Note that the input array will be modified in place.

#### removeDuplicatePoints(polygon: Array<Point>, precision: number): void

`js
var polygon = [
[0,0],
[1,1],
[2,2],
[0,0]
];
decomp.removeDuplicatePoints(polygon, 0.01);

// polygon is now [[1,1],[2,2],[0,0]]
`

$3


##### 0.3.0
* Added removeDuplicatePoints.
* makeCCW now returns true if the polygon was changed.
* Fixed case 5 mentioned here and discussed here.

##### 0.2.1
* Fixed bug in the collinear point removal, after this fix the algorithm is more agressive and more correct.

##### 0.2.0
* Rewrote the class based API to a minimal array-based one. See docs.

##### 0.1
* Added method `Polygon.prototype.removeCollinearPoints`.
* Added optional parameter `thresholdAngle` to `Point.collinear(a,b,c,thresholdAngle)`.

$3


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!