在多边形测试中，命中测试，一个点在多边形中吗?方法

Question

我创建了一个名为isInPoly的方法，该方法接收2条线(所以8个坐标)的x和y坐标，并确定2条线相交的位置。我知道我应该调用类似于intersectLocation之类的方法，但创建它的原因是看一个点是否在一个多边形中。如果你知道一个点不在多边形中，并在该点和你想要测试的点之间画一条线，看看它是否在多边形内，然后计算有多少个交点。如果交点的数目是偶数，则该点不在多边形中;如果交点的数目是奇数，则该点在多边形中。不管怎样，我没有得到这个方法的正确输出。我的程序只告诉我，如果测试点与已知点的斜率为-1，则该点在多边形内。我知道我刚刚写的东西可能很难理解，你能看看我的方法有什么问题吗?

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

坡度计算正确

但是b方程变换是错误的。它应该是:

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

x坐标的计算也是错误的(编辑:实际上它是正确的，但比必要的更复杂)。正确的转换是:

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

你的算法的其余部分是正确的。但也要记住，你还必须考虑到完全相同的直线(无限相交)。同时也要抓住方程中除零的例外(例如)平行于y轴的线。

if子句中的验证仅对某些行有效。你也可以考虑到直线的坐标可能会交换，所以交点的x坐标总是要小于直线的两个x坐标的最大值，大于x坐标的最小值。对于y坐标也是如此。

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;