Security News
NIST Misses 2024 Deadline to Clear NVD Backlog
NIST has failed to meet its self-imposed deadline of clearing the NVD's backlog by the end of the fiscal year. Meanwhile, CVE's awaiting analysis have increased by 33% since June.
poly-decomp
Advanced tools
Library for decomposing 2D polygons into convex regions.
Download decomp.js or decomp.min.js and include the script in your HTML:
<script src="decomp.js" type="text/javascript"></script>
<!-- or: -->
<script src="decomp.min.js" type="text/javascript"></script>
Then you can use the decomp
global.
npm install poly-decomp
Then require it like so:
var decomp = require('poly-decomp');
// Create a concave polygon
var concavePolygon = [
[ -1, 1],
[ -1, 0],
[ 1, 0],
[ 1, 1],
[0.5, 0.5]
];
// 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]] ]
// 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 in each on a HTML5 Canvas context
for(var i=0; i<convexPolygons.length; i++){
var convexPolygon = convexPolygons[i];
ctx.beginPath();
var firstPoint = convexPolygon[0];
ctx.moveTo(firstPoint[0], firstPoint[1]);
for(var j=1; j<convexPolygon.length; j++){
var point = convexPolygon[j];
var x = point[0];
var y = point[1];
c.lineTo(x, y);
}
ctx.closePath();
ctx.fill();
}
}
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.
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.
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.
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.
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.
Polygon.prototype.removeCollinearPoints
.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!
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).
FAQs
Convex decomposition for 2D polygons
The npm package poly-decomp receives a total of 3,495 weekly downloads. As such, poly-decomp popularity was classified as popular.
We found that poly-decomp demonstrated a not healthy version release cadence and project activity because the last version was released a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
NIST has failed to meet its self-imposed deadline of clearing the NVD's backlog by the end of the fiscal year. Meanwhile, CVE's awaiting analysis have increased by 33% since June.
Security News
Cloudflare has launched a setup wizard allowing users to easily create and manage a security.txt file for vulnerability disclosure on their websites.
Security News
The Socket Research team breaks down a malicious npm package targeting the legitimate DOMPurify library. It uses obfuscated code to hide that it is exfiltrating browser and crypto wallet data.