Simplifying a polygon
As you may know, polygons are sensitive to the ordering in which vertices are put in. What is more, the normals of a polygon face depend on the direction of the face.
This usually is not a problem when the polygon is constructed by a graphics-savvy person. If, however (as in my case), the polygons are edited in a user frontend, and if the target audience for that UI may not be aware of the problem, you might run into trouble.
I strongly believe, that details like this should be hidden from the less technically-inclined people, so they can get thei job done without swearing at the UI. And therefore be more productive. This piece of javascript allows you to “simplify”an array of 2D-Points by sorting it accordingly. The resulting array will construct a simple polygon with always outward-facing normals.
This uses the well-known paradigm of taking a reference point and then “swiping” counter-clockwise over the available points. Depending on the reference point (and the available vertices), the end-results may vary. So it may not really result in what the user expected. Having an undo ready at hand should prove useful. However, this algorithm assumes the most likely case, in which the reference point is set to the centroid of the polygon.
The entry-point function is this algorithm is “simplify_polygon”. Feel free to play around with it. Documentation is sparse, but if you know your trig you should figure it out by yourself. It’s fairly straightforward.
Note: The 4-way branch in the “angle” function could be simplified. It is as it is because my mind was locked in the 4 quadrants when writing it. Didn’t feel like changing it yet 😉
* Calculate the centroid of an array of 2D points
*/
function centroid(arr){
var sumx=0;
var sumy=0;
var count=0;
for (i in arr){
sumx += arr[i][0];
sumy += arr[i][1];
count++;
}
return new Array( sumx/count, sumy/count );
}
/*
* Calculate the dotproduct of 2 2D vectors
*/
function dotproduct(a, b){
return a[0]*b[0]+a[1]*b[1];
}
/*
* Return the euclidian distance between 2 2D-points
*/
function distance(a, b){
var dx = a[0]-b[0];
var dy = a[1]-b[1];
return Math.sqrt(Math.pow(dx,2) + Math.pow(dy,2));
}
/*
* Convert radians to degrees
*/
function deg(rad){
return (180 / Math.PI) * rad;
}
/*
* Calculate the angle between two 2D-Vectors with an optional reference point
*/
function angle(a, b, ref){
if (ref == undefined) { ref = new Array(0,0); }
var shifted_a = new Array( a[0]-ref[0], a[1]-ref[1] );
var shifted_b = new Array( b[0]-ref[0], b[1]-ref[1] );
var dx = b[0] - ref[0];
var dy = b[1] - ref[1];
var origin = new Array(0,0);
if (dx >= 0 && dy >= 0){
var dp = dotproduct(shifted_a, shifted_b);
var norm = distance(origin, shifted_a) * distance(origin, shifted_b);
return deg( Math.acos( dp / ( norm )));
} else if (dx < 0 && dy > 0) {
var dp = dotproduct(shifted_a, shifted_b);
var norm = distance(origin, shifted_a)*distance(origin, shifted_b);
return deg( Math.acos( dp / ( norm )));
} else if (dx < 0 && dy < 0) {
var dp = dotproduct(shifted_a, shifted_b);
var norm = distance(origin, shifted_a)*distance(origin, shifted_b);
return 360-deg( Math.acos( dp / ( norm )));
} else if (dx > 0 && dy < 0) {
var dp = dotproduct(shifted_a, shifted_b);
var norm = distance(origin, shifted_a)*distance(origin, shifted_b);
return 360-deg( Math.acos( dp / ( norm )));
}
}
/*
* Re-orders the vertices given in <pts> such that a simple polygon
* will be constructed.
*/
function simplify_polygon(pts){
var pts2 = new Array();
var c = centroid(pts);
var r = new Array(c[0]+10, c[1]);
for (i in pts){
pts2[pts2.length] = new Array(pts[i][0], pts[i][1], angle(r, pts[i], c));
}
pts2.sort(function compare(a,b){ return a[2]-b[2]; });
for (i in pts2){
pts[i] = pts2[i];
}
return pts;
}
Posted in Coding Voodoo | 1 Comment »