Library for decomposing a 2D polygon into convex pieces.
<!-- or: -->
Then you can use the
npm install poly-decomp
Then require it like so:
var decomp = ;
// Create a concave polygonvar concavePolygon =-1 1-1 01 01 105 05;// Make sure the polygon has counter-clockwise winding. Skip this step if you know it's already counter-clockwise.decomp;// Decompose into convex polygons, using the faster algorithmvar convexPolygons = decomp;// ==> [ [[1,0],[1,1],[0.5,0.5]], [[0.5,0.5],[-1,1],[-1,0],[1,0]] ]// Decompose using the slow (but optimal) algorithmvar convexPolygons = decomp;// ==> [ [[-1,1],[-1,0],[1,0],[0.5,0.5]], [[1,0],[1,1],[0.5,0.5]] ]
// Get user input as an array of points.var polygon = ;// Check if the polygon self-intersectsifdecomp// Reverse the polygon to make sure it uses counter-clockwise windingdecomp;// Decompose into convex piecesvar convexPolygons = decomp;// Draw each point on an HTML5 Canvas contextforvar i=0; i<convexPolygonslength; i++var convexPolygon = convexPolygonsi;ctx;var firstPoint = convexPolygon0;ctx;forvar j=1; j<convexPolygonlength; j++var point = convexPolygonj;var x = point0;var y = point1;c;ctx;ctx;
quickDecomp(polygon: Array<Point>): Array<Array<Point>>
var convexPolygons = decomp;
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>>
var convexPolygons = decomp;
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
ifdecomp// Polygon does not self-intersect - it's safe to decompose.var convexPolygons = decomp;
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
var before = polygonlength;decomp;var numRemoved = before - polygonlength;console;
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
var polygon =00112200;decomp;// polygon is now [[1,1],[2,2],[0,0]]
makeCCWnow returns true if the polygon was changed.
- Fixed case 5 mentioned here and discussed here.
- Fixed bug in the collinear point removal, after this fix the algorithm is more agressive and more correct.
- Rewrote the class based API to a minimal array-based one. See docs.
- Added method
- Added optional parameter
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!