Wednesday, 8 June 2016

Javascript: Determine if a point is within a polygon

It uses ray casting algorithm to check whether a point is inside a polygon
 $(function () {  
   var coordinates = "20,20,30,10,20,0,10,10";  
   var x = 15;
   var y = 15;
   var lines = convertCoordinateArraysToLineSegments(coordinates);  
   console.log(pointInsidePolygon(x,y, lines));  
 });  
   
 /**  
  * Check if a point (x,y) is inside a polygon  
  * It uses ray casting algorithm  
  * https://rosettacode.org/wiki/Ray-casting_algorithm  
  * @param x x coordinate of the point  
  * @param y y coordinate of the point  
  * @param lines an array of line segments, each line segment consists of 2 pair of coordinates, representing  
  *    two end points of the line segment. e.g. {x1=20, y1=20, x2=30, y2=10}  
  */  
 function pointInsidePolygon(x, y, lines){  
   var count = 0;  
   $.each(lines, function( index, value ) {  
     if (rayIntersectLineSegment(x, y, value)){  
       count++;  
     }  
   });  
   //If count is even number, the point is outside of polygon  
   //If count is odd number, the point is inside polygon  
   return count % 2 == 1;  
 }  
   
 /**  
  * Checks if a ray (endpoint at (x,y) going off to the right direction) intersects a line segment  
  * If the ray coincides with the line segment (i.e. the line segment is horizontal), it returns false (not intersecting)  
  * If the ray intersects the end point of the line segment,  
  *  a. If the ray intersects the higher end point (i.e. the line segment is below the ray), it returns false  
  *  b. If the ray intersects the lower end point (i.e. the line segment is above the ray), it returns true  
  * @param x x coordinate of the endpoint of the ray  
  * @param y y coordinate of the endpoint of the ray  
  * @param line the line segment, containing 2 pair of coordinates, representing two end points of the line segment  
  */  
 function rayIntersectLineSegment(x, y, line){  
   if (y >= Math.max(line.y1, line.y2)){  
     return false;  
   }  
   if (y < Math.min(line.y1, line.y2)){  
     return false;  
   }  
   // We want the line in linear equation standard form: a*x + b*y + c = 0  
   // See: http://en.wikipedia.org/wiki/Linear_equation  
   // Calculate a,b,c  
   var a = line.y2 - line.y1;  
   var b = line.x1 - line.x2;  
   var c = line.x2 * line.y1 - line.x1 * line.y2;  
   //For horizontal line, always return false  
   if (a == 0){  
     return false;  
   }  
   //Calculate the x coordinate given the same y coordinate as the ray's endpoint on the line segment  
   var x0 = (-c-b*y)/a; //transformed from a*x + b*y + c = 0  
   //Compare the x coordinate on the line segment with the x coordinate of the ray's endpoint  
   return x0 >= x;  
 }  
   
 /**  
  * Convert an array of coordinates into an array of line segments  
  * A line segment is represented by 2 pair of coordinates, e.g. {x1=20, y1=20, x2=30, y2=10}, each pair representing an  
  * end point of the line segment  
  * @param coordinates, a string of coordinates delimited by comma, with even index (starting 0) representing x coordinate, odd index representing y coordinate,  
  * e.g. (20,20,30,10,20,0,10,10)  
  */  
 function convertCoordinateArraysToLineSegments(coordinates){  
   var coords = coordinates.split(',');  
   var points = [];  
   var i;  
   for (i = 0; i < coords.length; i+=2){  
     points.push({x:parseInt(coords[i]), y:parseInt(coords[i+1])});  
   }  
   var lines = [];  
   //Assume points.length always >= 3  
   for (i = 0; i < points.length - 1; i++) {  
     lines.push({x1:points[i].x, y1:points[i].y, x2:points[i+1].x, y2:points[i+1].y});  
   }  
   lines.push({x1:points[points.length - 1].x, y1:points[points.length - 1].y, x2:points[0].x, y2:points[0].y});  
   return lines;  
 }  

No comments:

Post a Comment