Socket
Socket
Sign inDemoInstall

poly-decomp

Package Overview
Dependencies
0
Maintainers
1
Versions
5
Alerts
File Explorer

Advanced tools

npm Scripts
License

Install Socket

Detect and block malicious and high-risk dependencies

Install

Comparing version 0.1.1 to 0.2.0

.jshintrc
test/index.js

497

build/decomp.js

@@ -1,14 +0,11 @@

!function(e){"object"==typeof exports?module.exports=e():"function"==typeof define&&define.amd?define(e):"undefined"!=typeof window?window.decomp=e():"undefined"!=typeof global?global.decomp=e():"undefined"!=typeof self&&(self.decomp=e())}(function(){var define,module,exports;
return (function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);throw new Error("Cannot find module '"+o+"'")}var f=n[o]={exports:{}};t[o][0].call(f.exports,function(e){var n=t[o][1][e];return s(n?n:e)},f,f.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s})({1:[function(require,module,exports){
var Scalar = require('./Scalar');
!function(e){if("object"==typeof exports&&"undefined"!=typeof module)module.exports=e();else if("function"==typeof define&&define.amd)define([],e);else{var f;"undefined"!=typeof window?f=window:"undefined"!=typeof global?f=global:"undefined"!=typeof self&&(f=self),f.decomp=e()}}(function(){var define,module,exports;return (function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);throw new Error("Cannot find module '"+o+"'")}var f=n[o]={exports:{}};t[o][0].call(f.exports,function(e){var n=t[o][1][e];return s(n?n:e)},f,f.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s})({1:[function(_dereq_,module,exports){
module.exports = {
decomp: polygonDecomp,
quickDecomp: polygonQuickDecomp,
isSimple: polygonIsSimple,
removeCollinearPoints: polygonRemoveCollinearPoints,
makeCCW: polygonMakeCCW
};
module.exports = Line;
/**
* Container for line-related functions
* @class Line
*/
function Line(){};
/**
* Compute the intersection between two lines.

@@ -22,3 +19,3 @@ * @static

*/
Line.lineInt = function(l1,l2,precision){
function lineInt(l1,l2,precision){
precision = precision || 0;

@@ -34,3 +31,3 @@ var i = [0,0]; // point

det = a1 * b2 - a2*b1;
if (!Scalar.eq(det, 0, precision)) { // lines are not parallel
if (!scalar_eq(det, 0, precision)) { // lines are not parallel
i[0] = (b2 * c1 - b1 * c2) / det;

@@ -40,3 +37,3 @@ i[1] = (a1 * c2 - a2 * c1) / det;

return i;
};
}

@@ -52,29 +49,20 @@ /**

*/
Line.segmentsIntersect = function(p1, p2, q1, q2){
var dx = p2[0] - p1[0];
var dy = p2[1] - p1[1];
var da = q2[0] - q1[0];
var db = q2[1] - q1[1];
function lineSegmentsIntersect(p1, p2, q1, q2){
var dx = p2[0] - p1[0];
var dy = p2[1] - p1[1];
var da = q2[0] - q1[0];
var db = q2[1] - q1[1];
// segments are parallel
if(da*dy - db*dx == 0)
return false;
// segments are parallel
if((da*dy - db*dx) === 0){
return false;
}
var s = (dx * (q1[1] - p1[1]) + dy * (p1[0] - q1[0])) / (da * dy - db * dx)
var t = (da * (p1[1] - q1[1]) + db * (q1[0] - p1[0])) / (db * dx - da * dy)
var s = (dx * (q1[1] - p1[1]) + dy * (p1[0] - q1[0])) / (da * dy - db * dx);
var t = (da * (p1[1] - q1[1]) + db * (q1[0] - p1[0])) / (db * dx - da * dy);
return (s>=0 && s<=1 && t>=0 && t<=1);
};
return (s>=0 && s<=1 && t>=0 && t<=1);
}
},{"./Scalar":4}],2:[function(require,module,exports){
module.exports = Point;
/**
* Point related functions
* @class Point
*/
function Point(){};
/**
* Get the area of a triangle spanned by the three given points. Note that the area will be negative if the points are not given in counter-clockwise order.

@@ -88,21 +76,21 @@ * @static

*/
Point.area = function(a,b,c){
function triangleArea(a,b,c){
return (((b[0] - a[0])*(c[1] - a[1]))-((c[0] - a[0])*(b[1] - a[1])));
};
}
Point.left = function(a,b,c){
return Point.area(a,b,c) > 0;
};
function isLeft(a,b,c){
return triangleArea(a,b,c) > 0;
}
Point.leftOn = function(a,b,c) {
return Point.area(a, b, c) >= 0;
};
function isLeftOn(a,b,c) {
return triangleArea(a, b, c) >= 0;
}
Point.right = function(a,b,c) {
return Point.area(a, b, c) < 0;
};
function isRight(a,b,c) {
return triangleArea(a, b, c) < 0;
}
Point.rightOn = function(a,b,c) {
return Point.area(a, b, c) <= 0;
};
function isRightOn(a,b,c) {
return triangleArea(a, b, c) <= 0;
}

@@ -121,6 +109,6 @@ var tmpPoint1 = [],

*/
Point.collinear = function(a,b,c,thresholdAngle) {
if(!thresholdAngle)
return Point.area(a, b, c) == 0;
else {
function collinear(a,b,c,thresholdAngle) {
if(!thresholdAngle){
return triangleArea(a, b, c) === 0;
} else {
var ab = tmpPoint1,

@@ -140,30 +128,8 @@ bc = tmpPoint2;

}
};
}
Point.sqdist = function(a,b){
function sqdist(a,b){
var dx = b[0] - a[0];
var dy = b[1] - a[1];
return dx * dx + dy * dy;
};
},{}],3:[function(require,module,exports){
var Line = require("./Line")
, Point = require("./Point")
, Scalar = require("./Scalar")
module.exports = Polygon;
/**
* Polygon class.
* @class Polygon
* @constructor
*/
function Polygon(){
/**
* Vertices that this polygon consists of. An array of array of numbers, example: [[0,0],[1,0],..]
* @property vertices
* @type {Array}
*/
this.vertices = [];
}

@@ -177,27 +143,8 @@

*/
Polygon.prototype.at = function(i){
var v = this.vertices,
s = v.length;
return v[i < 0 ? i % s + s : i % s];
};
function polygonAt(polygon, i){
var s = polygon.length;
return polygon[i < 0 ? i % s + s : i % s];
}
/**
* Get first vertex
* @method first
* @return {Array}
*/
Polygon.prototype.first = function(){
return this.vertices[0];
};
/**
* Get last vertex
* @method last
* @return {Array}
*/
Polygon.prototype.last = function(){
return this.vertices[this.vertices.length-1];
};
/**
* Clear the polygon data

@@ -207,5 +154,5 @@ * @method clear

*/
Polygon.prototype.clear = function(){
this.vertices.length = 0;
};
function polygonClear(polygon){
polygon.length = 0;
}

@@ -220,14 +167,7 @@ /**

*/
Polygon.prototype.append = function(poly,from,to){
if(typeof(from) == "undefined") throw new Error("From is not given!");
if(typeof(to) == "undefined") throw new Error("To is not given!");
if(to-1 < from) throw new Error("lol1");
if(to > poly.vertices.length) throw new Error("lol2");
if(from < 0) throw new Error("lol3");
function polygonAppend(polygon, poly, from, to){
for(var i=from; i<to; i++){
this.vertices.push(poly.vertices[i]);
polygon.push(poly[i]);
}
};
}

@@ -238,9 +178,9 @@ /**

*/
Polygon.prototype.makeCCW = function(){
function polygonMakeCCW(polygon){
var br = 0,
v = this.vertices;
v = polygon;
// find bottom right point
for (var i = 1; i < this.vertices.length; ++i) {
if (v[i][1] < v[br][1] || (v[i][1] == v[br][1] && v[i][0] > v[br][0])) {
for (var i = 1; i < polygon.length; ++i) {
if (v[i][1] < v[br][1] || (v[i][1] === v[br][1] && v[i][0] > v[br][0])) {
br = i;

@@ -251,6 +191,6 @@ }

// reverse poly if clockwise
if (!Point.left(this.at(br - 1), this.at(br), this.at(br + 1))) {
this.reverse();
if (!isLeft(polygonAt(polygon, br - 1), polygonAt(polygon, br), polygonAt(polygon, br + 1))) {
polygonReverse(polygon);
}
};
}

@@ -261,9 +201,12 @@ /**

*/
Polygon.prototype.reverse = function(){
function polygonReverse(polygon){
var tmp = [];
for(var i=0, N=this.vertices.length; i!==N; i++){
tmp.push(this.vertices.pop());
var N = polygon.length;
for(var i=0; i!==N; i++){
tmp.push(polygon.pop());
}
this.vertices = tmp;
};
for(var i=0; i!==N; i++){
polygon[i] = tmp[i];
}
}

@@ -276,5 +219,5 @@ /**

*/
Polygon.prototype.isReflex = function(i){
return Point.right(this.at(i - 1), this.at(i), this.at(i + 1));
};
function polygonIsReflex(polygon, i){
return isRight(polygonAt(polygon, i - 1), polygonAt(polygon, i), polygonAt(polygon, i + 1));
}

@@ -291,19 +234,20 @@ var tmpLine1=[],

*/
Polygon.prototype.canSee = function(a,b) {
function polygonCanSee(polygon, a,b) {
var p, dist, l1=tmpLine1, l2=tmpLine2;
if (Point.leftOn(this.at(a + 1), this.at(a), this.at(b)) && Point.rightOn(this.at(a - 1), this.at(a), this.at(b))) {
if (isLeftOn(polygonAt(polygon, a + 1), polygonAt(polygon, a), polygonAt(polygon, b)) && isRightOn(polygonAt(polygon, a - 1), polygonAt(polygon, a), polygonAt(polygon, b))) {
return false;
}
dist = Point.sqdist(this.at(a), this.at(b));
for (var i = 0; i !== this.vertices.length; ++i) { // for each edge
if ((i + 1) % this.vertices.length === a || i === a) // ignore incident edges
dist = sqdist(polygonAt(polygon, a), polygonAt(polygon, b));
for (var i = 0; i !== polygon.length; ++i) { // for each edge
if ((i + 1) % polygon.length === a || i === a){ // ignore incident edges
continue;
if (Point.leftOn(this.at(a), this.at(b), this.at(i + 1)) && Point.rightOn(this.at(a), this.at(b), this.at(i))) { // if diag intersects an edge
l1[0] = this.at(a);
l1[1] = this.at(b);
l2[0] = this.at(i);
l2[1] = this.at(i + 1);
p = Line.lineInt(l1,l2);
if (Point.sqdist(this.at(a), p) < dist) { // if edge is blocking visibility to b
}
if (isLeftOn(polygonAt(polygon, a), polygonAt(polygon, b), polygonAt(polygon, i + 1)) && isRightOn(polygonAt(polygon, a), polygonAt(polygon, b), polygonAt(polygon, i))) { // if diag intersects an edge
l1[0] = polygonAt(polygon, a);
l1[1] = polygonAt(polygon, b);
l2[0] = polygonAt(polygon, i);
l2[1] = polygonAt(polygon, i + 1);
p = lineInt(l1,l2);
if (sqdist(polygonAt(polygon, a), p) < dist) { // if edge is blocking visibility to b
return false;

@@ -315,3 +259,3 @@ }

return true;
};
}

@@ -326,9 +270,10 @@ /**

*/
Polygon.prototype.copy = function(i,j,targetPoly){
var p = targetPoly || new Polygon();
p.clear();
function polygonCopy(polygon, i,j,targetPoly){
var p = targetPoly || [];
polygonClear(p);
if (i < j) {
// Insert all vertices from i to j
for(var k=i; k<=j; k++)
p.vertices.push(this.vertices[k]);
for(var k=i; k<=j; k++){
p.push(polygon[k]);
}

@@ -338,12 +283,14 @@ } else {

// Insert vertices 0 to j
for(var k=0; k<=j; k++)
p.vertices.push(this.vertices[k]);
for(var k=0; k<=j; k++){
p.push(polygon[k]);
}
// Insert vertices i to end
for(var k=i; k<this.vertices.length; k++)
p.vertices.push(this.vertices[k]);
for(var k=i; k<polygon.length; k++){
p.push(polygon[k]);
}
}
return p;
};
}

@@ -356,15 +303,16 @@ /**

*/
Polygon.prototype.getCutEdges = function() {
var min=[], tmp1=[], tmp2=[], tmpPoly = new Polygon();
function polygonGetCutEdges(polygon) {
var min=[], tmp1=[], tmp2=[], tmpPoly = [];
var nDiags = Number.MAX_VALUE;
for (var i = 0; i < this.vertices.length; ++i) {
if (this.isReflex(i)) {
for (var j = 0; j < this.vertices.length; ++j) {
if (this.canSee(i, j)) {
tmp1 = this.copy(i, j, tmpPoly).getCutEdges();
tmp2 = this.copy(j, i, tmpPoly).getCutEdges();
for (var i = 0; i < polygon.length; ++i) {
if (polygonIsReflex(polygon, i)) {
for (var j = 0; j < polygon.length; ++j) {
if (polygonCanSee(polygon, i, j)) {
tmp1 = polygonGetCutEdges(polygonCopy(polygon, i, j, tmpPoly));
tmp2 = polygonGetCutEdges(polygonCopy(polygon, j, i, tmpPoly));
for(var k=0; k<tmp2.length; k++)
for(var k=0; k<tmp2.length; k++){
tmp1.push(tmp2[k]);
}

@@ -374,3 +322,3 @@ if (tmp1.length < nDiags) {

nDiags = tmp1.length;
min.push([this.at(i), this.at(j)]);
min.push([polygonAt(polygon, i), polygonAt(polygon, j)]);
}

@@ -383,3 +331,3 @@ }

return min;
};
}

@@ -391,9 +339,10 @@ /**

*/
Polygon.prototype.decomp = function(){
var edges = this.getCutEdges();
if(edges.length > 0)
return this.slice(edges);
else
return [this];
};
function polygonDecomp(polygon){
var edges = polygonGetCutEdges(polygon);
if(edges.length > 0){
return polygonSlice(polygon, edges);
} else {
return [polygon];
}
}

@@ -406,7 +355,9 @@ /**

*/
Polygon.prototype.slice = function(cutEdges){
if(cutEdges.length == 0) return [this];
if(cutEdges instanceof Array && cutEdges.length && cutEdges[0] instanceof Array && cutEdges[0].length==2 && cutEdges[0][0] instanceof Array){
function polygonSlice(polygon, cutEdges){
if(cutEdges.length === 0){
return [polygon];
}
if(cutEdges instanceof Array && cutEdges.length && cutEdges[0] instanceof Array && cutEdges[0].length===2 && cutEdges[0][0] instanceof Array){
var polys = [this];
var polys = [polygon];

@@ -418,3 +369,3 @@ for(var i=0; i<cutEdges.length; i++){

var poly = polys[j];
var result = poly.slice(cutEdge);
var result = polygonSlice(poly, cutEdge);
if(result){

@@ -434,8 +385,8 @@ // Found poly! Cut and quit

var cutEdge = cutEdges;
var i = this.vertices.indexOf(cutEdge[0]);
var j = this.vertices.indexOf(cutEdge[1]);
var i = polygon.indexOf(cutEdge[0]);
var j = polygon.indexOf(cutEdge[1]);
if(i != -1 && j != -1){
return [this.copy(i,j),
this.copy(j,i)];
if(i !== -1 && j !== -1){
return [polygonCopy(polygon, i,j),
polygonCopy(polygon, j,i)];
} else {

@@ -445,3 +396,3 @@ return false;

}
};
}

@@ -455,8 +406,8 @@ /**

*/
Polygon.prototype.isSimple = function(){
var path = this.vertices;
function polygonIsSimple(polygon){
var path = polygon, i;
// Check
for(var i=0; i<path.length-1; i++){
for(i=0; i<path.length-1; i++){
for(var j=0; j<i-1; j++){
if(Line.segmentsIntersect(path[i], path[i+1], path[j], path[j+1] )){
if(lineSegmentsIntersect(path[i], path[i+1], path[j], path[j+1] )){
return false;

@@ -468,4 +419,4 @@ }

// Check the segment between the last and the first point to all others
for(var i=1; i<path.length-2; i++){
if(Line.segmentsIntersect(path[0], path[path.length-1], path[i], path[i+1] )){
for(i=1; i<path.length-2; i++){
if(lineSegmentsIntersect(path[0], path[path.length-1], path[i], path[i+1] )){
return false;

@@ -476,18 +427,19 @@ }

return true;
};
}
function getIntersectionPoint(p1, p2, q1, q2, delta){
delta = delta || 0;
var a1 = p2[1] - p1[1];
var b1 = p1[0] - p2[0];
var c1 = (a1 * p1[0]) + (b1 * p1[1]);
var a2 = q2[1] - q1[1];
var b2 = q1[0] - q2[0];
var c2 = (a2 * q1[0]) + (b2 * q1[1]);
var det = (a1 * b2) - (a2 * b1);
delta = delta || 0;
var a1 = p2[1] - p1[1];
var b1 = p1[0] - p2[0];
var c1 = (a1 * p1[0]) + (b1 * p1[1]);
var a2 = q2[1] - q1[1];
var b2 = q1[0] - q2[0];
var c2 = (a2 * q1[0]) + (b2 * q1[1]);
var det = (a1 * b2) - (a2 * b1);
if(!Scalar.eq(det,0,delta))
return [((b2 * c1) - (b1 * c2)) / det, ((a1 * c2) - (a2 * c1)) / det]
else
return [0,0]
if(!scalar_eq(det,0,delta)){
return [((b2 * c1) - (b1 * c2)) / det, ((a1 * c2) - (a2 * c1)) / det];
} else {
return [0,0];
}
}

@@ -506,7 +458,7 @@

*/
Polygon.prototype.quickDecomp = function(result,reflexVertices,steinerPoints,delta,maxlevel,level){
function polygonQuickDecomp(polygon, result,reflexVertices,steinerPoints,delta,maxlevel,level){
maxlevel = maxlevel || 100;
level = level || 0;
delta = delta || 25;
result = typeof(result)!="undefined" ? result : [];
result = typeof(result)!=="undefined" ? result : [];
reflexVertices = reflexVertices || [];

@@ -518,7 +470,9 @@ steinerPoints = steinerPoints || [];

var upperIndex=0, lowerIndex=0, closestIndex=0; // Integers
var lowerPoly=new Polygon(), upperPoly=new Polygon(); // polygons
var poly = this,
v = this.vertices;
var lowerPoly=[], upperPoly=[]; // polygons
var poly = polygon,
v = polygon;
if(v.length < 3) return result;
if(v.length < 3){
return result;
}

@@ -531,14 +485,13 @@ level++;

for (var i = 0; i < this.vertices.length; ++i) {
if (poly.isReflex(i)) {
reflexVertices.push(poly.vertices[i]);
for (var i = 0; i < polygon.length; ++i) {
if (polygonIsReflex(poly, i)) {
reflexVertices.push(poly[i]);
upperDist = lowerDist = Number.MAX_VALUE;
for (var j = 0; j < this.vertices.length; ++j) {
if (Point.left(poly.at(i - 1), poly.at(i), poly.at(j))
&& Point.rightOn(poly.at(i - 1), poly.at(i), poly.at(j - 1))) { // if line intersects with an edge
p = getIntersectionPoint(poly.at(i - 1), poly.at(i), poly.at(j), poly.at(j - 1)); // find the point of intersection
if (Point.right(poly.at(i + 1), poly.at(i), p)) { // make sure it's inside the poly
d = Point.sqdist(poly.vertices[i], p);
for (var j = 0; j < polygon.length; ++j) {
if (isLeft(polygonAt(poly, i - 1), polygonAt(poly, i), polygonAt(poly, j)) && isRightOn(polygonAt(poly, i - 1), polygonAt(poly, i), polygonAt(poly, j - 1))) { // if line intersects with an edge
p = getIntersectionPoint(polygonAt(poly, i - 1), polygonAt(poly, i), polygonAt(poly, j), polygonAt(poly, j - 1)); // find the point of intersection
if (isRight(polygonAt(poly, i + 1), polygonAt(poly, i), p)) { // make sure it's inside the poly
d = sqdist(poly[i], p);
if (d < lowerDist) { // keep only the closest intersection

@@ -551,7 +504,6 @@ lowerDist = d;

}
if (Point.left(poly.at(i + 1), poly.at(i), poly.at(j + 1))
&& Point.rightOn(poly.at(i + 1), poly.at(i), poly.at(j))) {
p = getIntersectionPoint(poly.at(i + 1), poly.at(i), poly.at(j), poly.at(j + 1));
if (Point.left(poly.at(i - 1), poly.at(i), p)) {
d = Point.sqdist(poly.vertices[i], p);
if (isLeft(polygonAt(poly, i + 1), polygonAt(poly, i), polygonAt(poly, j + 1)) && isRightOn(polygonAt(poly, i + 1), polygonAt(poly, i), polygonAt(poly, j))) {
p = getIntersectionPoint(polygonAt(poly, i + 1), polygonAt(poly, i), polygonAt(poly, j), polygonAt(poly, j + 1));
if (isLeft(polygonAt(poly, i - 1), polygonAt(poly, i), p)) {
d = sqdist(poly[i], p);
if (d < upperDist) {

@@ -567,4 +519,4 @@ upperDist = d;

// if there are no vertices to connect to, choose a point in the middle
if (lowerIndex == (upperIndex + 1) % this.vertices.length) {
//console.log("Case 1: Vertex("+i+"), lowerIndex("+lowerIndex+"), upperIndex("+upperIndex+"), poly.size("+this.vertices.length+")");
if (lowerIndex === (upperIndex + 1) % polygon.length) {
//console.log("Case 1: Vertex("+i+"), lowerIndex("+lowerIndex+"), upperIndex("+upperIndex+"), poly.size("+polygon.length+")");
p[0] = (lowerInt[0] + upperInt[0]) / 2;

@@ -576,29 +528,29 @@ p[1] = (lowerInt[1] + upperInt[1]) / 2;

//lowerPoly.insert(lowerPoly.end(), poly.begin() + i, poly.begin() + upperIndex + 1);
lowerPoly.append(poly, i, upperIndex+1);
lowerPoly.vertices.push(p);
upperPoly.vertices.push(p);
if (lowerIndex != 0){
polygonAppend(lowerPoly, poly, i, upperIndex+1);
lowerPoly.push(p);
upperPoly.push(p);
if (lowerIndex !== 0){
//upperPoly.insert(upperPoly.end(), poly.begin() + lowerIndex, poly.end());
upperPoly.append(poly,lowerIndex,poly.vertices.length);
polygonAppend(upperPoly, poly,lowerIndex,poly.length);
}
//upperPoly.insert(upperPoly.end(), poly.begin(), poly.begin() + i + 1);
upperPoly.append(poly,0,i+1);
polygonAppend(upperPoly, poly,0,i+1);
} else {
if (i != 0){
if (i !== 0){
//lowerPoly.insert(lowerPoly.end(), poly.begin() + i, poly.end());
lowerPoly.append(poly,i,poly.vertices.length);
polygonAppend(lowerPoly, poly,i,poly.length);
}
//lowerPoly.insert(lowerPoly.end(), poly.begin(), poly.begin() + upperIndex + 1);
lowerPoly.append(poly,0,upperIndex+1);
lowerPoly.vertices.push(p);
upperPoly.vertices.push(p);
polygonAppend(lowerPoly, poly,0,upperIndex+1);
lowerPoly.push(p);
upperPoly.push(p);
//upperPoly.insert(upperPoly.end(), poly.begin() + lowerIndex, poly.begin() + i + 1);
upperPoly.append(poly,lowerIndex,i+1);
polygonAppend(upperPoly, poly,lowerIndex,i+1);
}
} else {
// connect to the closest point within the triangle
//console.log("Case 2: Vertex("+i+"), closestIndex("+closestIndex+"), poly.size("+this.vertices.length+")\n");
//console.log("Case 2: Vertex("+i+"), closestIndex("+closestIndex+"), poly.size("+polygon.length+")\n");
if (lowerIndex > upperIndex) {
upperIndex += this.vertices.length;
upperIndex += polygon.length;
}

@@ -612,8 +564,7 @@ closestDist = Number.MAX_VALUE;

for (var j = lowerIndex; j <= upperIndex; ++j) {
if (Point.leftOn(poly.at(i - 1), poly.at(i), poly.at(j))
&& Point.rightOn(poly.at(i + 1), poly.at(i), poly.at(j))) {
d = Point.sqdist(poly.at(i), poly.at(j));
if (isLeftOn(polygonAt(poly, i - 1), polygonAt(poly, i), polygonAt(poly, j)) && isRightOn(polygonAt(poly, i + 1), polygonAt(poly, i), polygonAt(poly, j))) {
d = sqdist(polygonAt(poly, i), polygonAt(poly, j));
if (d < closestDist) {
closestDist = d;
closestIndex = j % this.vertices.length;
closestIndex = j % polygon.length;
}

@@ -624,13 +575,13 @@ }

if (i < closestIndex) {
lowerPoly.append(poly,i,closestIndex+1);
if (closestIndex != 0){
upperPoly.append(poly,closestIndex,v.length);
polygonAppend(lowerPoly, poly,i,closestIndex+1);
if (closestIndex !== 0){
polygonAppend(upperPoly, poly,closestIndex,v.length);
}
upperPoly.append(poly,0,i+1);
polygonAppend(upperPoly, poly,0,i+1);
} else {
if (i != 0){
lowerPoly.append(poly,i,v.length);
if (i !== 0){
polygonAppend(lowerPoly, poly,i,v.length);
}
lowerPoly.append(poly,0,closestIndex+1);
upperPoly.append(poly,closestIndex,i+1);
polygonAppend(lowerPoly, poly,0,closestIndex+1);
polygonAppend(upperPoly, poly,closestIndex,i+1);
}

@@ -640,8 +591,8 @@ }

// solve smallest poly first
if (lowerPoly.vertices.length < upperPoly.vertices.length) {
lowerPoly.quickDecomp(result,reflexVertices,steinerPoints,delta,maxlevel,level);
upperPoly.quickDecomp(result,reflexVertices,steinerPoints,delta,maxlevel,level);
if (lowerPoly.length < upperPoly.length) {
polygonQuickDecomp(lowerPoly,result,reflexVertices,steinerPoints,delta,maxlevel,level);
polygonQuickDecomp(upperPoly,result,reflexVertices,steinerPoints,delta,maxlevel,level);
} else {
upperPoly.quickDecomp(result,reflexVertices,steinerPoints,delta,maxlevel,level);
lowerPoly.quickDecomp(result,reflexVertices,steinerPoints,delta,maxlevel,level);
polygonQuickDecomp(upperPoly,result,reflexVertices,steinerPoints,delta,maxlevel,level);
polygonQuickDecomp(lowerPoly,result,reflexVertices,steinerPoints,delta,maxlevel,level);
}

@@ -652,6 +603,6 @@

}
result.push(this);
result.push(polygon);
return result;
};
}

@@ -664,8 +615,8 @@ /**

*/
Polygon.prototype.removeCollinearPoints = function(precision){
function polygonRemoveCollinearPoints(polygon, precision){
var num = 0;
for(var i=this.vertices.length-1; this.vertices.length>3 && i>=0; --i){
if(Point.collinear(this.at(i-1),this.at(i),this.at(i+1),precision)){
for(var i=polygon.length-1; polygon.length>3 && i>=0; --i){
if(collinear(polygonAt(polygon, i-1),polygonAt(polygon, i),polygonAt(polygon, i+1),precision)){
// Remove the middle point
this.vertices.splice(i%this.vertices.length,1);
polygon.splice(i%polygon.length,1);
i--; // Jump one point forward. Otherwise we may get a chain removal

@@ -676,14 +627,5 @@ num++;

return num;
};
}
},{"./Line":1,"./Point":2,"./Scalar":4}],4:[function(require,module,exports){
module.exports = Scalar;
/**
* Scalar functions
* @class Scalar
*/
function Scalar(){}
/**
* Check if two scalars are equal

@@ -697,16 +639,9 @@ * @static

*/
Scalar.eq = function(a,b,precision){
function scalar_eq(a,b,precision){
precision = precision || 0;
return Math.abs(a-b) < precision;
};
}
},{}],5:[function(require,module,exports){
module.exports = {
Polygon : require("./Polygon"),
Point : require("./Point"),
};
},{"./Point":2,"./Polygon":3}]},{},[5])
(5)
});
;
},{}]},{},[1])
(1)
});

2

build/decomp.min.js

@@ -1,1 +0,1 @@

!function(a){"object"==typeof exports?module.exports=a():"function"==typeof define&&define.amd?define(a):"undefined"!=typeof window?window.decomp=a():"undefined"!=typeof global?global.decomp=a():"undefined"!=typeof self&&(self.decomp=a())}(function(){return function a(b,c,d){function e(g,h){if(!c[g]){if(!b[g]){var i="function"==typeof require&&require;if(!h&&i)return i(g,!0);if(f)return f(g,!0);throw new Error("Cannot find module '"+g+"'")}var j=c[g]={exports:{}};b[g][0].call(j.exports,function(a){var c=b[g][1][a];return e(c?c:a)},j,j.exports,a,b,c,d)}return c[g].exports}for(var f="function"==typeof require&&require,g=0;g<d.length;g++)e(d[g]);return e}({1:[function(a,b){function c(){}var d=a("./Scalar");b.exports=c,c.lineInt=function(a,b,c){c=c||0;var e,f,g,h,i,j,k,l=[0,0];return e=a[1][1]-a[0][1],f=a[0][0]-a[1][0],g=e*a[0][0]+f*a[0][1],h=b[1][1]-b[0][1],i=b[0][0]-b[1][0],j=h*b[0][0]+i*b[0][1],k=e*i-h*f,d.eq(k,0,c)||(l[0]=(i*g-f*j)/k,l[1]=(e*j-h*g)/k),l},c.segmentsIntersect=function(a,b,c,d){var e=b[0]-a[0],f=b[1]-a[1],g=d[0]-c[0],h=d[1]-c[1];if(0==g*f-h*e)return!1;var i=(e*(c[1]-a[1])+f*(a[0]-c[0]))/(g*f-h*e),j=(g*(a[1]-c[1])+h*(c[0]-a[0]))/(h*e-g*f);return i>=0&&1>=i&&j>=0&&1>=j}},{"./Scalar":4}],2:[function(a,b){function c(){}b.exports=c,c.area=function(a,b,c){return(b[0]-a[0])*(c[1]-a[1])-(c[0]-a[0])*(b[1]-a[1])},c.left=function(a,b,d){return c.area(a,b,d)>0},c.leftOn=function(a,b,d){return c.area(a,b,d)>=0},c.right=function(a,b,d){return c.area(a,b,d)<0},c.rightOn=function(a,b,d){return c.area(a,b,d)<=0};var d=[],e=[];c.collinear=function(a,b,f,g){if(g){var h=d,i=e;h[0]=b[0]-a[0],h[1]=b[1]-a[1],i[0]=f[0]-b[0],i[1]=f[1]-b[1];var j=h[0]*i[0]+h[1]*i[1],k=Math.sqrt(h[0]*h[0]+h[1]*h[1]),l=Math.sqrt(i[0]*i[0]+i[1]*i[1]),m=Math.acos(j/(k*l));return g>m}return 0==c.area(a,b,f)},c.sqdist=function(a,b){var c=b[0]-a[0],d=b[1]-a[1];return c*c+d*d}},{}],3:[function(a,b){function c(){this.vertices=[]}function d(a,b,c,d,e){e=e||0;var f=b[1]-a[1],h=a[0]-b[0],i=f*a[0]+h*a[1],j=d[1]-c[1],k=c[0]-d[0],l=j*c[0]+k*c[1],m=f*k-j*h;return g.eq(m,0,e)?[0,0]:[(k*i-h*l)/m,(f*l-j*i)/m]}var e=a("./Line"),f=a("./Point"),g=a("./Scalar");b.exports=c,c.prototype.at=function(a){var b=this.vertices,c=b.length;return b[0>a?a%c+c:a%c]},c.prototype.first=function(){return this.vertices[0]},c.prototype.last=function(){return this.vertices[this.vertices.length-1]},c.prototype.clear=function(){this.vertices.length=0},c.prototype.append=function(a,b,c){if("undefined"==typeof b)throw new Error("From is not given!");if("undefined"==typeof c)throw new Error("To is not given!");if(b>c-1)throw new Error("lol1");if(c>a.vertices.length)throw new Error("lol2");if(0>b)throw new Error("lol3");for(var d=b;c>d;d++)this.vertices.push(a.vertices[d])},c.prototype.makeCCW=function(){for(var a=0,b=this.vertices,c=1;c<this.vertices.length;++c)(b[c][1]<b[a][1]||b[c][1]==b[a][1]&&b[c][0]>b[a][0])&&(a=c);f.left(this.at(a-1),this.at(a),this.at(a+1))||this.reverse()},c.prototype.reverse=function(){for(var a=[],b=0,c=this.vertices.length;b!==c;b++)a.push(this.vertices.pop());this.vertices=a},c.prototype.isReflex=function(a){return f.right(this.at(a-1),this.at(a),this.at(a+1))};var h=[],i=[];c.prototype.canSee=function(a,b){var c,d,g=h,j=i;if(f.leftOn(this.at(a+1),this.at(a),this.at(b))&&f.rightOn(this.at(a-1),this.at(a),this.at(b)))return!1;d=f.sqdist(this.at(a),this.at(b));for(var k=0;k!==this.vertices.length;++k)if((k+1)%this.vertices.length!==a&&k!==a&&f.leftOn(this.at(a),this.at(b),this.at(k+1))&&f.rightOn(this.at(a),this.at(b),this.at(k))&&(g[0]=this.at(a),g[1]=this.at(b),j[0]=this.at(k),j[1]=this.at(k+1),c=e.lineInt(g,j),f.sqdist(this.at(a),c)<d))return!1;return!0},c.prototype.copy=function(a,b,d){var e=d||new c;if(e.clear(),b>a)for(var f=a;b>=f;f++)e.vertices.push(this.vertices[f]);else{for(var f=0;b>=f;f++)e.vertices.push(this.vertices[f]);for(var f=a;f<this.vertices.length;f++)e.vertices.push(this.vertices[f])}return e},c.prototype.getCutEdges=function(){for(var a=[],b=[],d=[],e=new c,f=Number.MAX_VALUE,g=0;g<this.vertices.length;++g)if(this.isReflex(g))for(var h=0;h<this.vertices.length;++h)if(this.canSee(g,h)){b=this.copy(g,h,e).getCutEdges(),d=this.copy(h,g,e).getCutEdges();for(var i=0;i<d.length;i++)b.push(d[i]);b.length<f&&(a=b,f=b.length,a.push([this.at(g),this.at(h)]))}return a},c.prototype.decomp=function(){var a=this.getCutEdges();return a.length>0?this.slice(a):[this]},c.prototype.slice=function(a){if(0==a.length)return[this];if(a instanceof Array&&a.length&&a[0]instanceof Array&&2==a[0].length&&a[0][0]instanceof Array){for(var b=[this],c=0;c<a.length;c++)for(var d=a[c],e=0;e<b.length;e++){var f=b[e],g=f.slice(d);if(g){b.splice(e,1),b.push(g[0],g[1]);break}}return b}var d=a,c=this.vertices.indexOf(d[0]),e=this.vertices.indexOf(d[1]);return-1!=c&&-1!=e?[this.copy(c,e),this.copy(e,c)]:!1},c.prototype.isSimple=function(){for(var a=this.vertices,b=0;b<a.length-1;b++)for(var c=0;b-1>c;c++)if(e.segmentsIntersect(a[b],a[b+1],a[c],a[c+1]))return!1;for(var b=1;b<a.length-2;b++)if(e.segmentsIntersect(a[0],a[a.length-1],a[b],a[b+1]))return!1;return!0},c.prototype.quickDecomp=function(a,b,e,g,h,i){h=h||100,i=i||0,g=g||25,a="undefined"!=typeof a?a:[],b=b||[],e=e||[];var j=[0,0],k=[0,0],l=[0,0],m=0,n=0,o=0,p=0,q=0,r=0,s=0,t=new c,u=new c,v=this,w=this.vertices;if(w.length<3)return a;if(i++,i>h)return console.warn("quickDecomp: max level ("+h+") reached."),a;for(var x=0;x<this.vertices.length;++x)if(v.isReflex(x)){b.push(v.vertices[x]),m=n=Number.MAX_VALUE;for(var y=0;y<this.vertices.length;++y)f.left(v.at(x-1),v.at(x),v.at(y))&&f.rightOn(v.at(x-1),v.at(x),v.at(y-1))&&(l=d(v.at(x-1),v.at(x),v.at(y),v.at(y-1)),f.right(v.at(x+1),v.at(x),l)&&(o=f.sqdist(v.vertices[x],l),n>o&&(n=o,k=l,r=y))),f.left(v.at(x+1),v.at(x),v.at(y+1))&&f.rightOn(v.at(x+1),v.at(x),v.at(y))&&(l=d(v.at(x+1),v.at(x),v.at(y),v.at(y+1)),f.left(v.at(x-1),v.at(x),l)&&(o=f.sqdist(v.vertices[x],l),m>o&&(m=o,j=l,q=y)));if(r==(q+1)%this.vertices.length)l[0]=(k[0]+j[0])/2,l[1]=(k[1]+j[1])/2,e.push(l),q>x?(t.append(v,x,q+1),t.vertices.push(l),u.vertices.push(l),0!=r&&u.append(v,r,v.vertices.length),u.append(v,0,x+1)):(0!=x&&t.append(v,x,v.vertices.length),t.append(v,0,q+1),t.vertices.push(l),u.vertices.push(l),u.append(v,r,x+1));else{if(r>q&&(q+=this.vertices.length),p=Number.MAX_VALUE,r>q)return a;for(var y=r;q>=y;++y)f.leftOn(v.at(x-1),v.at(x),v.at(y))&&f.rightOn(v.at(x+1),v.at(x),v.at(y))&&(o=f.sqdist(v.at(x),v.at(y)),p>o&&(p=o,s=y%this.vertices.length));s>x?(t.append(v,x,s+1),0!=s&&u.append(v,s,w.length),u.append(v,0,x+1)):(0!=x&&t.append(v,x,w.length),t.append(v,0,s+1),u.append(v,s,x+1))}return t.vertices.length<u.vertices.length?(t.quickDecomp(a,b,e,g,h,i),u.quickDecomp(a,b,e,g,h,i)):(u.quickDecomp(a,b,e,g,h,i),t.quickDecomp(a,b,e,g,h,i)),a}return a.push(this),a},c.prototype.removeCollinearPoints=function(a){for(var b=0,c=this.vertices.length-1;this.vertices.length>3&&c>=0;--c)f.collinear(this.at(c-1),this.at(c),this.at(c+1),a)&&(this.vertices.splice(c%this.vertices.length,1),c--,b++);return b}},{"./Line":1,"./Point":2,"./Scalar":4}],4:[function(a,b){function c(){}b.exports=c,c.eq=function(a,b,c){return c=c||0,Math.abs(a-b)<c}},{}],5:[function(a,b){b.exports={Polygon:a("./Polygon"),Point:a("./Point")}},{"./Point":2,"./Polygon":3}]},{},[5])(5)});
!function(e){if("object"==typeof exports&&"undefined"!=typeof module)module.exports=e();else if("function"==typeof define&&define.amd)define([],e);else{var f;"undefined"!=typeof window?f=window:"undefined"!=typeof global?f=global:"undefined"!=typeof self&&(f=self),f.decomp=e()}}(function(){return function e(f,o,n){function d(t,l){if(!o[t]){if(!f[t]){var u="function"==typeof require&&require;if(!l&&u)return u(t,!0);if(i)return i(t,!0);throw new Error("Cannot find module '"+t+"'")}var p=o[t]={exports:{}};f[t][0].call(p.exports,function(e){var o=f[t][1][e];return d(o?o:e)},p,p.exports,e,f,o,n)}return o[t].exports}for(var i="function"==typeof require&&require,t=0;t<n.length;t++)d(n[t]);return d}({1:[function(e,f,o){function n(e,f,o){o=o||0;var n,d,i,t,l,u,p,s=[0,0];return n=e[1][1]-e[0][1],d=e[0][0]-e[1][0],i=n*e[0][0]+d*e[0][1],t=f[1][1]-f[0][1],l=f[0][0]-f[1][0],u=t*f[0][0]+l*f[0][1],p=n*l-t*d,B(p,0,o)||(s[0]=(l*i-d*u)/p,s[1]=(n*u-t*i)/p),s}function d(e,f,o,n){var d=f[0]-e[0],i=f[1]-e[1],t=n[0]-o[0],l=n[1]-o[1];if(t*i-l*d===0)return!1;var u=(d*(o[1]-e[1])+i*(e[0]-o[0]))/(t*i-l*d),p=(t*(e[1]-o[1])+l*(o[0]-e[0]))/(l*d-t*i);return u>=0&&1>=u&&p>=0&&1>=p}function i(e,f,o){return(f[0]-e[0])*(o[1]-e[1])-(o[0]-e[0])*(f[1]-e[1])}function t(e,f,o){return i(e,f,o)>0}function l(e,f,o){return i(e,f,o)>=0}function u(e,f,o){return i(e,f,o)<0}function p(e,f,o){return i(e,f,o)<=0}function s(e,f,o,n){if(n){var d=C,t=D;d[0]=f[0]-e[0],d[1]=f[1]-e[1],t[0]=o[0]-f[0],t[1]=o[1]-f[1];var l=d[0]*t[0]+d[1]*t[1],u=Math.sqrt(d[0]*d[0]+d[1]*d[1]),p=Math.sqrt(t[0]*t[0]+t[1]*t[1]),s=Math.acos(l/(u*p));return n>s}return 0===i(e,f,o)}function c(e,f){var o=f[0]-e[0],n=f[1]-e[1];return o*o+n*n}function y(e,f){var o=e.length;return e[0>f?f%o+o:f%o]}function a(e){e.length=0}function m(e,f,o,n){for(var d=o;n>d;d++)e.push(f[d])}function r(e){for(var f=0,o=e,n=1;n<e.length;++n)(o[n][1]<o[f][1]||o[n][1]===o[f][1]&&o[n][0]>o[f][0])&&(f=n);t(y(e,f-1),y(e,f),y(e,f+1))||w(e)}function w(e){for(var f=[],o=e.length,n=0;n!==o;n++)f.push(e.pop());for(var n=0;n!==o;n++)e[n]=f[n]}function b(e,f){return u(y(e,f-1),y(e,f),y(e,f+1))}function g(e,f,o){var d,i,t=E,u=F;if(l(y(e,f+1),y(e,f),y(e,o))&&p(y(e,f-1),y(e,f),y(e,o)))return!1;i=c(y(e,f),y(e,o));for(var s=0;s!==e.length;++s)if((s+1)%e.length!==f&&s!==f&&l(y(e,f),y(e,o),y(e,s+1))&&p(y(e,f),y(e,o),y(e,s))&&(t[0]=y(e,f),t[1]=y(e,o),u[0]=y(e,s),u[1]=y(e,s+1),d=n(t,u),c(y(e,f),d)<i))return!1;return!0}function x(e,f,o,n){var d=n||[];if(a(d),o>f)for(var i=f;o>=i;i++)d.push(e[i]);else{for(var i=0;o>=i;i++)d.push(e[i]);for(var i=f;i<e.length;i++)d.push(e[i])}return d}function j(e){for(var f=[],o=[],n=[],d=[],i=Number.MAX_VALUE,t=0;t<e.length;++t)if(b(e,t))for(var l=0;l<e.length;++l)if(g(e,t,l)){o=j(x(e,t,l,d)),n=j(x(e,l,t,d));for(var u=0;u<n.length;u++)o.push(n[u]);o.length<i&&(f=o,i=o.length,f.push([y(e,t),y(e,l)]))}return f}function v(e){var f=j(e);return f.length>0?h(e,f):[e]}function h(e,f){if(0===f.length)return[e];if(f instanceof Array&&f.length&&f[0]instanceof Array&&2===f[0].length&&f[0][0]instanceof Array){for(var o=[e],n=0;n<f.length;n++)for(var d=f[n],i=0;i<o.length;i++){var t=o[i],l=h(t,d);if(l){o.splice(i,1),o.push(l[0],l[1]);break}}return o}var d=f,n=e.indexOf(d[0]),i=e.indexOf(d[1]);return-1!==n&&-1!==i?[x(e,n,i),x(e,i,n)]:!1}function k(e){var f,o=e;for(f=0;f<o.length-1;f++)for(var n=0;f-1>n;n++)if(d(o[f],o[f+1],o[n],o[n+1]))return!1;for(f=1;f<o.length-2;f++)if(d(o[0],o[o.length-1],o[f],o[f+1]))return!1;return!0}function q(e,f,o,n,d){d=d||0;var i=f[1]-e[1],t=e[0]-f[0],l=i*e[0]+t*e[1],u=n[1]-o[1],p=o[0]-n[0],s=u*o[0]+p*o[1],c=i*p-u*t;return B(c,0,d)?[0,0]:[(p*l-t*s)/c,(i*s-u*l)/c]}function z(e,f,o,n,d,i,s){i=i||100,s=s||0,d=d||25,f="undefined"!=typeof f?f:[],o=o||[],n=n||[];var a=[0,0],r=[0,0],w=[0,0],g=0,x=0,j=0,v=0,h=0,k=0,A=0,B=[],C=[],D=e,E=e;if(E.length<3)return f;if(s++,s>i)return console.warn("quickDecomp: max level ("+i+") reached."),f;for(var F=0;F<e.length;++F)if(b(D,F)){o.push(D[F]),g=x=Number.MAX_VALUE;for(var G=0;G<e.length;++G)t(y(D,F-1),y(D,F),y(D,G))&&p(y(D,F-1),y(D,F),y(D,G-1))&&(w=q(y(D,F-1),y(D,F),y(D,G),y(D,G-1)),u(y(D,F+1),y(D,F),w)&&(j=c(D[F],w),x>j&&(x=j,r=w,k=G))),t(y(D,F+1),y(D,F),y(D,G+1))&&p(y(D,F+1),y(D,F),y(D,G))&&(w=q(y(D,F+1),y(D,F),y(D,G),y(D,G+1)),t(y(D,F-1),y(D,F),w)&&(j=c(D[F],w),g>j&&(g=j,a=w,h=G)));if(k===(h+1)%e.length)w[0]=(r[0]+a[0])/2,w[1]=(r[1]+a[1])/2,n.push(w),h>F?(m(B,D,F,h+1),B.push(w),C.push(w),0!==k&&m(C,D,k,D.length),m(C,D,0,F+1)):(0!==F&&m(B,D,F,D.length),m(B,D,0,h+1),B.push(w),C.push(w),m(C,D,k,F+1));else{if(k>h&&(h+=e.length),v=Number.MAX_VALUE,k>h)return f;for(var G=k;h>=G;++G)l(y(D,F-1),y(D,F),y(D,G))&&p(y(D,F+1),y(D,F),y(D,G))&&(j=c(y(D,F),y(D,G)),v>j&&(v=j,A=G%e.length));A>F?(m(B,D,F,A+1),0!==A&&m(C,D,A,E.length),m(C,D,0,F+1)):(0!==F&&m(B,D,F,E.length),m(B,D,0,A+1),m(C,D,A,F+1))}return B.length<C.length?(z(B,f,o,n,d,i,s),z(C,f,o,n,d,i,s)):(z(C,f,o,n,d,i,s),z(B,f,o,n,d,i,s)),f}return f.push(e),f}function A(e,f){for(var o=0,n=e.length-1;e.length>3&&n>=0;--n)s(y(e,n-1),y(e,n),y(e,n+1),f)&&(e.splice(n%e.length,1),n--,o++);return o}function B(e,f,o){return o=o||0,Math.abs(e-f)<o}f.exports={decomp:v,quickDecomp:z,isSimple:k,removeCollinearPoints:A,makeCCW:r};var C=[],D=[],E=[],F=[]},{}]},{},[1])(1)});

7

Gruntfile.js

@@ -24,2 +24,6 @@ module.exports = function(grunt) {

},
nodeunit: {
all: ['test/**/*.js'],
}
});

@@ -29,5 +33,6 @@

grunt.loadNpmTasks('grunt-contrib-uglify');
grunt.loadNpmTasks('grunt-contrib-nodeunit');
grunt.registerTask('default', ['browserify','uglify']);
grunt.registerTask('default', ['nodeunit', 'browserify','uglify']);
};

63

package.json
{
"name": "poly-decomp",
"version": "0.1.1",
"description": "Convex decomposition in 2D",
"author": "Stefan Hedman <schteppe@gmail.com> (http://steffe.se)",
"keywords": [
"convex",
"decomposition",
"polygon",
"2d"
],
"engines": {
"node": "*"
},
"main": "./src/index.js",
"repository": {
"type": "git",
"url": "https://github.com/schteppe/poly-decomp.js.git"
},
"bugs": {
"url": "https://github.com/schteppe/poly-decomp.js/issues"
},
"licenses" : [{
"type" : "MIT"
}],
"dependencies" : {
},
"devDependencies" : {
"grunt": "~0.4.0",
"grunt-contrib-uglify": "~0.4.0",
"grunt-browserify":"~2.0.8",
"browserify" : "~3.44.2"
}
"name": "poly-decomp",
"version": "0.2.0",
"description": "Convex decomposition for 2D polygons",
"author": "Stefan Hedman <schteppe@gmail.com> (http://steffe.se)",
"keywords": [
"convex",
"decomposition",
"polygon",
"2d"
],
"engines": {
"node": "*"
},
"main": "./src/index.js",
"repository": {
"type": "git",
"url": "https://github.com/schteppe/poly-decomp.js.git"
},
"bugs": {
"url": "https://github.com/schteppe/poly-decomp.js/issues"
},
"license": "MIT",
"dependencies": {},
"devDependencies": {
"browserify": "^3.44.2",
"grunt": "^1.0.1",
"grunt-browserify": "^2.0.8",
"grunt-contrib-nodeunit": "^1.0.0",
"grunt-contrib-uglify": "^0.4.1",
"nodeunit": "^0.9.1"
}
}

148

README.md

@@ -6,54 +6,136 @@ poly-decomp.js

[Demo](http://schteppe.github.io/poly-decomp.js/) - [Documentation](http://schteppe.github.io/poly-decomp.js/docs)
[Launch the demo!](http://schteppe.github.io/poly-decomp.js/)
### About
### Install
##### Browser
Download [decomp.js](build/decomp.js) or [decomp.min.js](build/decomp.min.js) and include the script in your HTML:
```html
<script src="decomp.js" type="text/javascript"></script>
<!-- or: -->
<script src="decomp.min.js" type="text/javascript"></script>
```
The library is a manual port of the C++ library [Poly Decomp](http://mnbayazit.com/406/overview) by [Mark Bayazit](http://mnbayazit.com/).
Then you can use the ```decomp``` global.
It implements two algorithms, one optimal (but slow) and one less optimal (but fast).
##### Node.js
```
npm install poly-decomp
```
### Usage
Then require it like so:
```js
var decomp = require('poly-decomp');
```
### Basic usage
```js
// Create a concave polygon
var concave = new decomp.Polygon();
concave.vertices.push([ -1, 1],
[ -1, 0],
[ 1, 0],
[ 1, 1],
[0.5, 0.5]);
var concavePolygon = [
[ -1, 1],
[ -1, 0],
[ 1, 0],
[ 1, 1],
[0.5, 0.5]
];
// Decompose into convex polygons, using the faster algorithm
var convexes1 = concave.quickDecomp();
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 convexes2 = concave.decomp();
var convexPolygons = decomp.decomp(concavePolygon);
// convexes1 and convexes2 are now arrays of Polygon objects.
// ==> [ [[-1,1],[-1,0],[1,0],[0.5,0.5]], [[1,0],[1,1],[0.5,0.5]] ]
```
### Install
##### Browser
Download [decomp.js](build/decomp.js) and include the script in your HTML:
```html
<script src="decomp.js" type="text/javascript"></script>
### Advanced usage
```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 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();
}
}
```
##### Node.js
Until the code gets somewhat more stable, use the git url to install:
### Documentation
#### quickDecomp(polygon: Array&lt;Point&gt;): Array&lt;Array&lt;Point&gt;&gt;
```js
var convexPolygons = decomp.quickDecomp(polygon);
```
npm install git://github.com/schteppe/poly-decomp.js
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&lt;Point&gt;): Array&lt;Array&lt;Point&gt;&gt;
```js
var convexPolygons = decomp.quickDecomp(polygon);
```
Or add the dependency to your ```package.json```:
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&lt;Point&gt;): boolean
```js
if(decomp.isSimple(polygon)){
// Polygon does not self-intersect - it's safe to decompose.
var convexPolygons = decomp.quickDecomp(polygon);
}
```
...
"dependencies" : {
"poly-decomp" : "git://github.com/schteppe/poly-decomp.js"
}
...
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&lt;Point&gt;): void
```js
console.log('Polygon with clockwise winding:', polygon);
decomp.makeCCW(polygon);
console.log('Polygon with counter-clockwise winding:', polygon);
```
Then require it like so:
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&lt;Point&gt;, thresholdAngle: number): void
```js
var decomp = require('poly-decomp');
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.
### Change log
##### 0.2.0
* Rewrote the class based API to a minimal array-based one. See docs.
##### 0.1

@@ -73,1 +155,7 @@ * Added method ```Polygon.prototype.removeCollinearPoints```.

The most recent commits are currently pushed to the ```master``` branch. Thanks for contributing!
### About
The library is a manual port of the C++ library [Poly Decomp](http://mnbayazit.com/406/overview) by [Mark Bayazit](http://mnbayazit.com/).
It implements two algorithms, one optimal (but slow) and one less optimal (but fast).

600

src/index.js
module.exports = {
Polygon : require("./Polygon"),
Point : require("./Point"),
decomp: polygonDecomp,
quickDecomp: polygonQuickDecomp,
isSimple: polygonIsSimple,
removeCollinearPoints: polygonRemoveCollinearPoints,
makeCCW: polygonMakeCCW
};
/**
* Compute the intersection between two lines.
* @static
* @method lineInt
* @param {Array} l1 Line vector 1
* @param {Array} l2 Line vector 2
* @param {Number} precision Precision to use when checking if the lines are parallel
* @return {Array} The intersection point.
*/
function lineInt(l1,l2,precision){
precision = precision || 0;
var i = [0,0]; // point
var a1, b1, c1, a2, b2, c2, det; // scalars
a1 = l1[1][1] - l1[0][1];
b1 = l1[0][0] - l1[1][0];
c1 = a1 * l1[0][0] + b1 * l1[0][1];
a2 = l2[1][1] - l2[0][1];
b2 = l2[0][0] - l2[1][0];
c2 = a2 * l2[0][0] + b2 * l2[0][1];
det = a1 * b2 - a2*b1;
if (!scalar_eq(det, 0, precision)) { // lines are not parallel
i[0] = (b2 * c1 - b1 * c2) / det;
i[1] = (a1 * c2 - a2 * c1) / det;
}
return i;
}
/**
* Checks if two line segments intersects.
* @method segmentsIntersect
* @param {Array} p1 The start vertex of the first line segment.
* @param {Array} p2 The end vertex of the first line segment.
* @param {Array} q1 The start vertex of the second line segment.
* @param {Array} q2 The end vertex of the second line segment.
* @return {Boolean} True if the two line segments intersect
*/
function lineSegmentsIntersect(p1, p2, q1, q2){
var dx = p2[0] - p1[0];
var dy = p2[1] - p1[1];
var da = q2[0] - q1[0];
var db = q2[1] - q1[1];
// segments are parallel
if((da*dy - db*dx) === 0){
return false;
}
var s = (dx * (q1[1] - p1[1]) + dy * (p1[0] - q1[0])) / (da * dy - db * dx);
var t = (da * (p1[1] - q1[1]) + db * (q1[0] - p1[0])) / (db * dx - da * dy);
return (s>=0 && s<=1 && t>=0 && t<=1);
}
/**
* Get the area of a triangle spanned by the three given points. Note that the area will be negative if the points are not given in counter-clockwise order.
* @static
* @method area
* @param {Array} a
* @param {Array} b
* @param {Array} c
* @return {Number}
*/
function triangleArea(a,b,c){
return (((b[0] - a[0])*(c[1] - a[1]))-((c[0] - a[0])*(b[1] - a[1])));
}
function isLeft(a,b,c){
return triangleArea(a,b,c) > 0;
}
function isLeftOn(a,b,c) {
return triangleArea(a, b, c) >= 0;
}
function isRight(a,b,c) {
return triangleArea(a, b, c) < 0;
}
function isRightOn(a,b,c) {
return triangleArea(a, b, c) <= 0;
}
var tmpPoint1 = [],
tmpPoint2 = [];
/**
* Check if three points are collinear
* @method collinear
* @param {Array} a
* @param {Array} b
* @param {Array} c
* @param {Number} [thresholdAngle=0] Threshold angle to use when comparing the vectors. The function will return true if the angle between the resulting vectors is less than this value. Use zero for max precision.
* @return {Boolean}
*/
function collinear(a,b,c,thresholdAngle) {
if(!thresholdAngle){
return triangleArea(a, b, c) === 0;
} else {
var ab = tmpPoint1,
bc = tmpPoint2;
ab[0] = b[0]-a[0];
ab[1] = b[1]-a[1];
bc[0] = c[0]-b[0];
bc[1] = c[1]-b[1];
var dot = ab[0]*bc[0] + ab[1]*bc[1],
magA = Math.sqrt(ab[0]*ab[0] + ab[1]*ab[1]),
magB = Math.sqrt(bc[0]*bc[0] + bc[1]*bc[1]),
angle = Math.acos(dot/(magA*magB));
return angle < thresholdAngle;
}
}
function sqdist(a,b){
var dx = b[0] - a[0];
var dy = b[1] - a[1];
return dx * dx + dy * dy;
}
/**
* Get a vertex at position i. It does not matter if i is out of bounds, this function will just cycle.
* @method at
* @param {Number} i
* @return {Array}
*/
function polygonAt(polygon, i){
var s = polygon.length;
return polygon[i < 0 ? i % s + s : i % s];
}
/**
* Clear the polygon data
* @method clear
* @return {Array}
*/
function polygonClear(polygon){
polygon.length = 0;
}
/**
* Append points "from" to "to"-1 from an other polygon "poly" onto this one.
* @method append
* @param {Polygon} poly The polygon to get points from.
* @param {Number} from The vertex index in "poly".
* @param {Number} to The end vertex index in "poly". Note that this vertex is NOT included when appending.
* @return {Array}
*/
function polygonAppend(polygon, poly, from, to){
for(var i=from; i<to; i++){
polygon.push(poly[i]);
}
}
/**
* Make sure that the polygon vertices are ordered counter-clockwise.
* @method makeCCW
*/
function polygonMakeCCW(polygon){
var br = 0,
v = polygon;
// find bottom right point
for (var i = 1; i < polygon.length; ++i) {
if (v[i][1] < v[br][1] || (v[i][1] === v[br][1] && v[i][0] > v[br][0])) {
br = i;
}
}
// reverse poly if clockwise
if (!isLeft(polygonAt(polygon, br - 1), polygonAt(polygon, br), polygonAt(polygon, br + 1))) {
polygonReverse(polygon);
}
}
/**
* Reverse the vertices in the polygon
* @method reverse
*/
function polygonReverse(polygon){
var tmp = [];
var N = polygon.length;
for(var i=0; i!==N; i++){
tmp.push(polygon.pop());
}
for(var i=0; i!==N; i++){
polygon[i] = tmp[i];
}
}
/**
* Check if a point in the polygon is a reflex point
* @method isReflex
* @param {Number} i
* @return {Boolean}
*/
function polygonIsReflex(polygon, i){
return isRight(polygonAt(polygon, i - 1), polygonAt(polygon, i), polygonAt(polygon, i + 1));
}
var tmpLine1=[],
tmpLine2=[];
/**
* Check if two vertices in the polygon can see each other
* @method canSee
* @param {Number} a Vertex index 1
* @param {Number} b Vertex index 2
* @return {Boolean}
*/
function polygonCanSee(polygon, a,b) {
var p, dist, l1=tmpLine1, l2=tmpLine2;
if (isLeftOn(polygonAt(polygon, a + 1), polygonAt(polygon, a), polygonAt(polygon, b)) && isRightOn(polygonAt(polygon, a - 1), polygonAt(polygon, a), polygonAt(polygon, b))) {
return false;
}
dist = sqdist(polygonAt(polygon, a), polygonAt(polygon, b));
for (var i = 0; i !== polygon.length; ++i) { // for each edge
if ((i + 1) % polygon.length === a || i === a){ // ignore incident edges
continue;
}
if (isLeftOn(polygonAt(polygon, a), polygonAt(polygon, b), polygonAt(polygon, i + 1)) && isRightOn(polygonAt(polygon, a), polygonAt(polygon, b), polygonAt(polygon, i))) { // if diag intersects an edge
l1[0] = polygonAt(polygon, a);
l1[1] = polygonAt(polygon, b);
l2[0] = polygonAt(polygon, i);
l2[1] = polygonAt(polygon, i + 1);
p = lineInt(l1,l2);
if (sqdist(polygonAt(polygon, a), p) < dist) { // if edge is blocking visibility to b
return false;
}
}
}
return true;
}
/**
* Copy the polygon from vertex i to vertex j.
* @method copy
* @param {Number} i
* @param {Number} j
* @param {Polygon} [targetPoly] Optional target polygon to save in.
* @return {Polygon} The resulting copy.
*/
function polygonCopy(polygon, i,j,targetPoly){
var p = targetPoly || [];
polygonClear(p);
if (i < j) {
// Insert all vertices from i to j
for(var k=i; k<=j; k++){
p.push(polygon[k]);
}
} else {
// Insert vertices 0 to j
for(var k=0; k<=j; k++){
p.push(polygon[k]);
}
// Insert vertices i to end
for(var k=i; k<polygon.length; k++){
p.push(polygon[k]);
}
}
return p;
}
/**
* Decomposes the polygon into convex pieces. Returns a list of edges [[p1,p2],[p2,p3],...] that cuts the polygon.
* Note that this algorithm has complexity O(N^4) and will be very slow for polygons with many vertices.
* @method getCutEdges
* @return {Array}
*/
function polygonGetCutEdges(polygon) {
var min=[], tmp1=[], tmp2=[], tmpPoly = [];
var nDiags = Number.MAX_VALUE;
for (var i = 0; i < polygon.length; ++i) {
if (polygonIsReflex(polygon, i)) {
for (var j = 0; j < polygon.length; ++j) {
if (polygonCanSee(polygon, i, j)) {
tmp1 = polygonGetCutEdges(polygonCopy(polygon, i, j, tmpPoly));
tmp2 = polygonGetCutEdges(polygonCopy(polygon, j, i, tmpPoly));
for(var k=0; k<tmp2.length; k++){
tmp1.push(tmp2[k]);
}
if (tmp1.length < nDiags) {
min = tmp1;
nDiags = tmp1.length;
min.push([polygonAt(polygon, i), polygonAt(polygon, j)]);
}
}
}
}
}
return min;
}
/**
* Decomposes the polygon into one or more convex sub-Polygons.
* @method decomp
* @return {Array} An array or Polygon objects.
*/
function polygonDecomp(polygon){
var edges = polygonGetCutEdges(polygon);
if(edges.length > 0){
return polygonSlice(polygon, edges);
} else {
return [polygon];
}
}
/**
* Slices the polygon given one or more cut edges. If given one, this function will return two polygons (false on failure). If many, an array of polygons.
* @method slice
* @param {Array} cutEdges A list of edges, as returned by .getCutEdges()
* @return {Array}
*/
function polygonSlice(polygon, cutEdges){
if(cutEdges.length === 0){
return [polygon];
}
if(cutEdges instanceof Array && cutEdges.length && cutEdges[0] instanceof Array && cutEdges[0].length===2 && cutEdges[0][0] instanceof Array){
var polys = [polygon];
for(var i=0; i<cutEdges.length; i++){
var cutEdge = cutEdges[i];
// Cut all polys
for(var j=0; j<polys.length; j++){
var poly = polys[j];
var result = polygonSlice(poly, cutEdge);
if(result){
// Found poly! Cut and quit
polys.splice(j,1);
polys.push(result[0],result[1]);
break;
}
}
}
return polys;
} else {
// Was given one edge
var cutEdge = cutEdges;
var i = polygon.indexOf(cutEdge[0]);
var j = polygon.indexOf(cutEdge[1]);
if(i !== -1 && j !== -1){
return [polygonCopy(polygon, i,j),
polygonCopy(polygon, j,i)];
} else {
return false;
}
}
}
/**
* Checks that the line segments of this polygon do not intersect each other.
* @method isSimple
* @param {Array} path An array of vertices e.g. [[0,0],[0,1],...]
* @return {Boolean}
* @todo Should it check all segments with all others?
*/
function polygonIsSimple(polygon){
var path = polygon, i;
// Check
for(i=0; i<path.length-1; i++){
for(var j=0; j<i-1; j++){
if(lineSegmentsIntersect(path[i], path[i+1], path[j], path[j+1] )){
return false;
}
}
}
// Check the segment between the last and the first point to all others
for(i=1; i<path.length-2; i++){
if(lineSegmentsIntersect(path[0], path[path.length-1], path[i], path[i+1] )){
return false;
}
}
return true;
}
function getIntersectionPoint(p1, p2, q1, q2, delta){
delta = delta || 0;
var a1 = p2[1] - p1[1];
var b1 = p1[0] - p2[0];
var c1 = (a1 * p1[0]) + (b1 * p1[1]);
var a2 = q2[1] - q1[1];
var b2 = q1[0] - q2[0];
var c2 = (a2 * q1[0]) + (b2 * q1[1]);
var det = (a1 * b2) - (a2 * b1);
if(!scalar_eq(det,0,delta)){
return [((b2 * c1) - (b1 * c2)) / det, ((a1 * c2) - (a2 * c1)) / det];
} else {
return [0,0];
}
}
/**
* Quickly decompose the Polygon into convex sub-polygons.
* @method quickDecomp
* @param {Array} result
* @param {Array} [reflexVertices]
* @param {Array} [steinerPoints]
* @param {Number} [delta]
* @param {Number} [maxlevel]
* @param {Number} [level]
* @return {Array}
*/
function polygonQuickDecomp(polygon, result,reflexVertices,steinerPoints,delta,maxlevel,level){
maxlevel = maxlevel || 100;
level = level || 0;
delta = delta || 25;
result = typeof(result)!=="undefined" ? result : [];
reflexVertices = reflexVertices || [];
steinerPoints = steinerPoints || [];
var upperInt=[0,0], lowerInt=[0,0], p=[0,0]; // Points
var upperDist=0, lowerDist=0, d=0, closestDist=0; // scalars
var upperIndex=0, lowerIndex=0, closestIndex=0; // Integers
var lowerPoly=[], upperPoly=[]; // polygons
var poly = polygon,
v = polygon;
if(v.length < 3){
return result;
}
level++;
if(level > maxlevel){
console.warn("quickDecomp: max level ("+maxlevel+") reached.");
return result;
}
for (var i = 0; i < polygon.length; ++i) {
if (polygonIsReflex(poly, i)) {
reflexVertices.push(poly[i]);
upperDist = lowerDist = Number.MAX_VALUE;
for (var j = 0; j < polygon.length; ++j) {
if (isLeft(polygonAt(poly, i - 1), polygonAt(poly, i), polygonAt(poly, j)) && isRightOn(polygonAt(poly, i - 1), polygonAt(poly, i), polygonAt(poly, j - 1))) { // if line intersects with an edge
p = getIntersectionPoint(polygonAt(poly, i - 1), polygonAt(poly, i), polygonAt(poly, j), polygonAt(poly, j - 1)); // find the point of intersection
if (isRight(polygonAt(poly, i + 1), polygonAt(poly, i), p)) { // make sure it's inside the poly
d = sqdist(poly[i], p);
if (d < lowerDist) { // keep only the closest intersection
lowerDist = d;
lowerInt = p;
lowerIndex = j;
}
}
}
if (isLeft(polygonAt(poly, i + 1), polygonAt(poly, i), polygonAt(poly, j + 1)) && isRightOn(polygonAt(poly, i + 1), polygonAt(poly, i), polygonAt(poly, j))) {
p = getIntersectionPoint(polygonAt(poly, i + 1), polygonAt(poly, i), polygonAt(poly, j), polygonAt(poly, j + 1));
if (isLeft(polygonAt(poly, i - 1), polygonAt(poly, i), p)) {
d = sqdist(poly[i], p);
if (d < upperDist) {
upperDist = d;
upperInt = p;
upperIndex = j;
}
}
}
}
// if there are no vertices to connect to, choose a point in the middle
if (lowerIndex === (upperIndex + 1) % polygon.length) {
//console.log("Case 1: Vertex("+i+"), lowerIndex("+lowerIndex+"), upperIndex("+upperIndex+"), poly.size("+polygon.length+")");
p[0] = (lowerInt[0] + upperInt[0]) / 2;
p[1] = (lowerInt[1] + upperInt[1]) / 2;
steinerPoints.push(p);
if (i < upperIndex) {
//lowerPoly.insert(lowerPoly.end(), poly.begin() + i, poly.begin() + upperIndex + 1);
polygonAppend(lowerPoly, poly, i, upperIndex+1);
lowerPoly.push(p);
upperPoly.push(p);
if (lowerIndex !== 0){
//upperPoly.insert(upperPoly.end(), poly.begin() + lowerIndex, poly.end());
polygonAppend(upperPoly, poly,lowerIndex,poly.length);
}
//upperPoly.insert(upperPoly.end(), poly.begin(), poly.begin() + i + 1);
polygonAppend(upperPoly, poly,0,i+1);
} else {
if (i !== 0){
//lowerPoly.insert(lowerPoly.end(), poly.begin() + i, poly.end());
polygonAppend(lowerPoly, poly,i,poly.length);
}
//lowerPoly.insert(lowerPoly.end(), poly.begin(), poly.begin() + upperIndex + 1);
polygonAppend(lowerPoly, poly,0,upperIndex+1);
lowerPoly.push(p);
upperPoly.push(p);
//upperPoly.insert(upperPoly.end(), poly.begin() + lowerIndex, poly.begin() + i + 1);
polygonAppend(upperPoly, poly,lowerIndex,i+1);
}
} else {
// connect to the closest point within the triangle
//console.log("Case 2: Vertex("+i+"), closestIndex("+closestIndex+"), poly.size("+polygon.length+")\n");
if (lowerIndex > upperIndex) {
upperIndex += polygon.length;
}
closestDist = Number.MAX_VALUE;
if(upperIndex < lowerIndex){
return result;
}
for (var j = lowerIndex; j <= upperIndex; ++j) {
if (isLeftOn(polygonAt(poly, i - 1), polygonAt(poly, i), polygonAt(poly, j)) && isRightOn(polygonAt(poly, i + 1), polygonAt(poly, i), polygonAt(poly, j))) {
d = sqdist(polygonAt(poly, i), polygonAt(poly, j));
if (d < closestDist) {
closestDist = d;
closestIndex = j % polygon.length;
}
}
}
if (i < closestIndex) {
polygonAppend(lowerPoly, poly,i,closestIndex+1);
if (closestIndex !== 0){
polygonAppend(upperPoly, poly,closestIndex,v.length);
}
polygonAppend(upperPoly, poly,0,i+1);
} else {
if (i !== 0){
polygonAppend(lowerPoly, poly,i,v.length);
}
polygonAppend(lowerPoly, poly,0,closestIndex+1);
polygonAppend(upperPoly, poly,closestIndex,i+1);
}
}
// solve smallest poly first
if (lowerPoly.length < upperPoly.length) {
polygonQuickDecomp(lowerPoly,result,reflexVertices,steinerPoints,delta,maxlevel,level);
polygonQuickDecomp(upperPoly,result,reflexVertices,steinerPoints,delta,maxlevel,level);
} else {
polygonQuickDecomp(upperPoly,result,reflexVertices,steinerPoints,delta,maxlevel,level);
polygonQuickDecomp(lowerPoly,result,reflexVertices,steinerPoints,delta,maxlevel,level);
}
return result;
}
}
result.push(polygon);
return result;
}
/**
* Remove collinear points in the polygon.
* @method removeCollinearPoints
* @param {Number} [precision] The threshold angle to use when determining whether two edges are collinear. Use zero for finest precision.
* @return {Number} The number of points removed
*/
function polygonRemoveCollinearPoints(polygon, precision){
var num = 0;
for(var i=polygon.length-1; polygon.length>3 && i>=0; --i){
if(collinear(polygonAt(polygon, i-1),polygonAt(polygon, i),polygonAt(polygon, i+1),precision)){
// Remove the middle point
polygon.splice(i%polygon.length,1);
i--; // Jump one point forward. Otherwise we may get a chain removal
num++;
}
}
return num;
}
/**
* Check if two scalars are equal
* @static
* @method eq
* @param {Number} a
* @param {Number} b
* @param {Number} [precision]
* @return {Boolean}
*/
function scalar_eq(a,b,precision){
precision = precision || 0;
return Math.abs(a-b) < precision;
}
docs/api.js
docs/assets/css/external-small.png
docs/assets/css/logo.png
docs/assets/css/main.css
docs/assets/favicon.png
docs/assets/img/spinner.gif
docs/assets/index.html
docs/assets/js/api-filter.js
docs/assets/js/api-list.js
docs/assets/js/api-search.js
docs/assets/js/apidocs.js
docs/assets/js/yui-prettify.js
docs/assets/vendor/prettify/CHANGES.html
docs/assets/vendor/prettify/COPYING
docs/assets/vendor/prettify/prettify-min.css
docs/assets/vendor/prettify/prettify-min.js
docs/assets/vendor/prettify/README.html
docs/classes/index.html
docs/classes/Line.html
docs/classes/Point.html
docs/classes/Polygon.html
docs/classes/Scalar.html
docs/data.json
docs/files/index.html
docs/files/src_Line.js.html
docs/files/src_Point.js.html
docs/files/src_Polygon.js.html
docs/files/src_Scalar.js.html
docs/modules/index.html
src/Line.js
src/Point.js
src/Polygon.js
src/Scalar.js
test/Polygon.js
yuidoc.json
docs/index.html

Sorry, the diff of this file is not supported yet

index.html

Sorry, the diff of this file is not supported yet

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap

About

Packages

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc