1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ '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. \$\endgroup\$ – CiaPan Sep 19 '16 at 12:29
  • \$\begingroup\$ @CiaPan Good catch. That is certainly a weakness with the current algorithm. \$\endgroup\$ – Hohmannfan Sep 19 '16 at 12:47
  • \$\begingroup\$ 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. \$\endgroup\$ – CiaPan Sep 19 '16 at 13:45
  • \$\begingroup\$ 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. \$\endgroup\$ – CiaPan Sep 19 '16 at 13:47
  • \$\begingroup\$ 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. \$\endgroup\$ – CiaPan Sep 19 '16 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.