To check if a given point is inside a polygon or not is a very useful piece of code.
Here is my implementation in JavaScript of an algorithm counting the number of times a ray crosses the perimeter of the polygon, and subsequently checking the parity. I have included an initial test doing a fast comparison with the rectangular bounding box of the polygon, and also support for the possibility that the bounding box and/or if the polygon is convex is precalculated.
Here is my function:
pointInsidePolygon = function(x,y,polygon){//returns true/false
//also consider to use the'pointInsiderectangle' function for simpler tasks
/* sturcture of the polygon object:
{
corners:[
{
x:number,
y:number
}//repeat for any number of corners > 2
]
//optional, if it has a precomputed bounding box, it has these properties as well:
xmin:number,
xmax:number,
ymin:number,
ymax:number,
convex:boolean
}
*/
//fast "false/maybe" test: check if the point is inside the outer bounding box of the polygon.
if(polygon.xmin === undefined){//if the bounding box of the polygon is not precomputed, then compute it.
var xmin = xmax = polygon.corners[0].x;
var ymin = ymax = polygon.corners[0].y;
for(var i = polygon.corners.length;--i;){
if(polygon.corners[i].x < xmin){
xmin = polygon.corners[i].x;
}
else if(polygon.corners[i].x > xmax){
xmax = polygon.corners[i].x;
};
if(polygon.corners[i].y < ymin){
ymin = polygon.corners[i].y;
}
else if(polygon.corners[i].y > ymax){
ymax = polygon.corners[i].y;
};
};
polygon.xmin = xmin;
polygon.xmax = xmax;
polygon.ymin = ymin;
polygon.ymax = ymax;
};
if(x < polygon.xmin || x > polygon.xmax){
return false;
}
else if(y < polygon.xmin || x > polygon.ymax){
return false;
};
/* complete "true/false" test: check the number of times a ray from the point intersects the perimeter of the polygon
* odd number == inside
* even number == outside
* I cast the ray along the x axis
*/
var intersections = 0;
for(var i = polygon.corners.length;i--;){
var xpos = polygon.corners[i].x - x;//the polygon is translated with the test point in origo
var ypos = polygon.corners[i].y - y;
if(i){
var xpos2 = polygon.corners[i - 1].x - x;
var ypos2 = polygon.corners[i - 1].y - y;
}
else{//the last side of the polygon wraps around to the first point of the corner list, it requires special handling.
var xpos2 = polygon.corners[polygon.corners.length - 1].x - x;
var ypos2 = polygon.corners[polygon.corners.length - 1].y - y;
};
//each side of the polygon does potentially intersect the ray. I skip the iteration for those that do not.
if(xpos < 0 && xpos2 < 0){//the ray can not cross a side starting and ending at negative x, so no intersection then
continue;
}
else if(ypos * ypos2 > 0){//still no intersection if both y's have the same sign
continue;
}
else if(xpos + (xpos2 - xpos) * ypos/(ypos - ypos2) < 0){//intersections of the x-axis before x=0 do not count
continue;
}
else if(ypos === 0){//a corner may be exactly at the ray
continue;
};
alert(xpos+","+ypos+","+xpos2+","+ypos2);
intersections++;
if(polygon.convex && intersections === 2){//a ray through a convex polygon can intersect at most 2 times
return false;
};
};
if(intersections % 2 === 0){
return false;
};
return true;
};
It seems like somebody has already posted something similar in Python, but it was implemented quite differently.