В тесте полигонов, тест на попадание, точка в полигоне? метод

Question

Я создал метод с именем isInPoly, который получает координаты x и y двух линий (то есть 8 координат) и определяет, где эти две линии пересекаются. Я знаю, что должен был назвать метод что-то вроде 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;