Check if a point is inside a polygon

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;
};
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.

• 'A corner is exactly at the ray' is the trickiest point. Consider 3 consecutive corners, all with positive x and (case 1) negative, zero and negative y or (case 2) negative, zero and positive y. You should get a single intersection in the case 1 and no (or two) intersections in case 2. – CiaPan Sep 19 '16 at 12:29
• @CiaPan Good catch. That is certainly a weakness with the current algorithm. – Hohmannfan Sep 19 '16 at 12:47
• Whoops, I have mismatched example data and results: case 1 (minus, zero, minus) should give no intersection (the polygon's edge turns back at the ray) while case 2 (minus, zero, plus) should give a single intersection (the edge actually crosses the ray). I'm sorry for that. – CiaPan Sep 19 '16 at 13:45
• There are even more complicated cases when several consecutive vertices lay at the ray... However, you can easily solve them all at once: treat each vertex at the ray as if it lays slightly above the ray. :) Simply replace y==0 with some constant epsilon. – CiaPan Sep 19 '16 at 13:47
• The real problem would be a polygon's side coincident with the ray with one vertex at negative and the other one at positive x (that is your point belonging to a 'horizontal' line segment being the polygon's side). That however appears a special case of a general decision whether the point on the border is inside or outside the polygon. – CiaPan Sep 19 '16 at 13:50