codeBlog code is only worth when it is working

24Jun/150

Converting a self intersecting polygon into list of simple polygons [Java Script]

function checkPolygonLineIntersection(line1StartX, line1StartY, line1EndX, line1EndY, line2StartX, line2StartY, line2EndX, line2EndY) {

var denominator, a, b, numerator1, numerator2, result = {
x: null,
y: null,
onLine1: false,
onLine2: false,
line1StartX: Number(line1StartX),
line1StartY:Number(line1StartY),
line1EndX: Number(line1EndX),
line1EndY: Number(line1EndY),
line2StartX:Number(line2StartX),
line2StartY:Number(line2StartY),
line2EndX:Number(line2EndX) ,
line2EndY: Number(line2EndY),
line1Index: 0,
line2Index: 0
};
denominator = ((line2EndY - line2StartY) * (line1EndX - line1StartX)) - ((line2EndX - line2StartX) * (line1EndY - line1StartY));
if (denominator == 0) {
return result;
}
a = line1StartY - line2StartY;
b = line1StartX - line2StartX;
numerator1 = ((line2EndX - line2StartX) * a) - ((line2EndY - line2StartY) * b);
numerator2 = ((line1EndX - line1StartX) * a) - ((line1EndY - line1StartY) * b);
a = numerator1 / denominator;
b = numerator2 / denominator;
result.x = line1StartX + (a * (line1EndX - line1StartX));
result.y = line1StartY + (a * (line1EndY - line1StartY));

if (a > 0 && a < 1) {
result.onLine1 = true;
}

if (b > 0 && b < 1) {
result.onLine2 = true;
}

return result;
};

function checkIntersection(vert){
var ps = vert, i, j, x1, x2, x3, x4, y1, y2, y3, y4;
ps.push(ps[0]);
ps.push(ps[1]);
for(i = 0; i < ps.length -2 ; ) {
x1 = ps[i]; x2 = ps[i+2];
y1 = ps[i+1]; y2 = ps[i+3];
for(j = i + 4; j < ps.length -2 ; ) {
x3 = ps[j]; x4 = ps[j+2];
y3 = ps[j+1]; y4 = ps[j+3];

var retResult = checkPolygonLineIntersection(
Number(x1), Number(y1), Number(x2), Number(y2), Number(x3), Number(y3), Number(x4), Number(y4)
);

if((retResult.onLine1) && (retResult.onLine2)) {
console.log('intersected!'+' ,Line1 start: '+x1+' - '+y1+' ,Line1 End: '+x2+' - '+y2+' ,Line2 start: '+x3+' - '+y3+' ,Line1 END: '+x4+' - '+y4+' ,inx: '+retResult.x+' ,iny: '+retResult.y+' ,i: '+i+' ,j: '+j);

retResult.line1StartX = x1;
retResult.line1StartY = y1;
retResult.line1EndX = x2;
retResult.line1EndY = y2;
retResult.line2StartX = x3;
retResult.line2StartY = y3;
retResult.line2EndX = x4;
retResult.line2EndY = y4;
retResult.line1Index = i;
retResult.line2Index = j;

return retResult;

}
j = j+2;
}
i = i+2;
}
return false;
}

/ * Input Param *****
* pdpPoints is an array of points in following formate
* PolygonPoints = [(a.x,a.y),(b.x,b.y),(c.x,c.y),(d.x,d.y),(a.x,a.y)] // Note first and last points are same.
* var pdpPoints = [a.x,a.y,b.x,b.y,c.x,c.y,d.x,d.y,a.x,a.y];
*
* return List of simple polygons.
*/

function getSimplePolygon(pdpPoints){
var simplePolygonList = [];
var returnResult = checkIntersection(pdpPoints);
if(returnResult != false){
var simplePolygon1 = [];
var simplePolygon2 = [];
var switchPolygonFlag = false;
simplePolygon1.push(returnResult.x.toString());
simplePolygon1.push(returnResult.y.toString());
simplePolygon2.push(returnResult.x.toString());
simplePolygon2.push(returnResult.y.toString());
for(var iLoop = 0,jLoop = returnResult.line1Index ; iLoop < pdpPoints.length-2;){

if(jLoop+1 >= pdpPoints.length-3){
jLoop = 0;
}

if(((pdpPoints[jLoop] == returnResult.line2StartX ) && (pdpPoints[jLoop+1] == returnResult.line2StartY ) ) ||
((pdpPoints[jLoop] == returnResult.line2EndX ) && (pdpPoints[jLoop+1] == returnResult.line2EndY ) )){
switchPolygonFlag = true;
}else{
if(switchPolygonFlag){
simplePolygon2.push(pdpPoints[jLoop]);
simplePolygon2.push(pdpPoints[jLoop+1]);
}else{
simplePolygon1.push(pdpPoints[jLoop]);
simplePolygon1.push(pdpPoints[jLoop+1]);
}
}
iLoop = iLoop + 2;
jLoop = jLoop + 2;
}
simplePolygon1.push(returnResult.x.toString());
simplePolygon1.push(returnResult.y.toString());
simplePolygon2.push(returnResult.x.toString());
simplePolygon2.push(returnResult.y.toString());

var localPoly1List = getSimplePolygon(simplePolygon1);
var localPoly2List = getSimplePolygon(simplePolygon2);

for(var k = 0; k < localPoly1List.length; k++){
simplePolygonList.push(localPoly1List[k]);
}
for(var m = 0; m < localPoly2List.length; m++){
simplePolygonList.push(localPoly2List[m]);
}
}else{
simplePolygonList.push(pdpPoints);
}
return simplePolygonList;
}

Share and Enjoy

  • Facebook
  • Twitter
  • Delicious
  • LinkedIn
  • StumbleUpon
  • Add to favorites
  • Email
  • RSS
Filed under: Code Blog Leave a comment
Comments (0) Trackbacks (0)

No comments yet.


Leave a comment

No trackbacks yet.

Email
Print