# poly-decomp

0.3.0 • Public • Published

# poly-decomp.js

Library for decomposing a 2D polygon into convex pieces.

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.

### Install

##### Browser

Then you can use the `decomp` global.

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

Then require it like so:

### Documentation

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

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>>

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

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

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

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.

### Change log

##### 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)`.

### Contribute

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!

## Package Sidebar

### Install

`npm i poly-decomp`

### Repository

github.com/schteppe/poly-decomp.js

5,770

0.3.0

MIT

120 kB

12