In polygon test, hit test, is a point in a polygon? method

Question

I have created a method called isInPoly that receives the x and y coordinates of 2 lines (so 8 coordinates) and determines where the 2 lines intersect. I know I should have called the method something like intersectLocation or something, but the reason why created it was to see if a point was in a polygon. If you know of a point that is not in the polygon and make a line between that point and the point that you want to test to see if it is inside the polygon, then count how many intersections there are. If the number of intersections are even then the point is not in the polygon and if the number is odd then the point is in the polygon. Anyway I am not getting the right output for this method. My program only shows me that the point is inside the polygon if the test point is at a -1 slope to the known point. I know what I just wrote might be hard to follow can you see if there is any problems with my method?

public static boolean isInPoly(float l1x1, float l1y1, float l1x2, float l1y2, float l2x1, float l2y1, float l2x2, float l2y2) {
    // TODO Auto-generated method stub

    // l1x1 = the first lines first x coordinate 
    // l1y1 = the first lines first x coordinate 
    //.....
    //l1m = the first lines slope represented as "m" in the equation y=mx+b
    //l1b = the first lines y intercept represented as "b" in the equation y=mx+b
    // x = the x coordinate of the intersection on the 2 lines  
    // y = the x coordinate of the intersection on the 2 lines 



    float l1m,l2m,l1b,l2b,x,y;

    //y=mx+b
    //x=(y2-y1)/(x2-x1)
    //b=y/(mx)


    //slopes of each line
    l1m = (l1y2-l1y1)/(l1x2-l1x1);
    l2m = (l2y2-l2y1)/(l2x2-l2x1);

    //y-intercepts of each line
    l1b = l1y2/(l1m*l1x2);
    l2b = l2y2/(l2m*l2x2);

    //m1x+b1=m2x+b2
    //m1x=m2x+b2-b1
    //x=(m2/m1)x+((b2-b1)/m1)
    //x-(m2/m1)x=((b2-b1)/m1)
    //(1-(m2/m1))x=((b2-b1)/m1)
    //x=((b2-b1)/m1)/(1-(m2/m1))


    //finding the x coordinate of the intersection
    x=((l2b-l1b)/l1m)/(1-(l2m/l1m));

    //y=mx+b


    //finding the x coordinate of the intersection
    y=(l1m*x)+l1b;

    if(y>=l1y1 && y<=l1y2  && x>=l1x1 && x<=l1x2){
        return true;
    }
    else{
        return false;
    }

}

Answer 1

The slope calculation is right.

However the b equation transformation is wrong. It should rather be:

//l1y1=l1m*l1x1+l1b
l1b=l1y1-l1m*l1x1

The calculation of the x coordinate is also wrong (EDIT: in fact it is right, but more complex than necessary). The right transformation is:

//l1m*x+l1b = l2m*x+l2b
//l1m*x-l2m*x = l2b-l1b
// x*(l1m-l2m) = l2b - l1b
x = (l2b-l1b) / (l1m-l2m)

The rest of your algorithm is right. But also remember you also have to take things like completely same lines (infinite intersections) into account. And also catch divide-by-zero exceptions in your equations (e.g.) for lines parallel to the y-axis.

The validation in the if clause is only valid for some lines. You might also take into the account that the coordinates of the lines may be swapped so the x coordinate of the intersection always has to be smaller than the maximum of the two x coordinates of the line and greater than the minimum of the x coordinates. The same goes for the y coordinate.

x_max = l1x1 > l1x2 ? l1x1 : l1x2;
x_min = l1x1 < l1x2 ? l1x2 : l1x1;

y_max = l1y1 > l1y2 ? l1y1 : l1y2;
y_min = l1y1 < l1y2 ? l1y2 : l1y1;

if ((y_min <= y) && (y_max => y) && (x_min <= x) && (x_max >= x))
    return true;