Линии сегментов Пересечение (точка пересечения)

Question

Я создал функцию для вычисления точки пересечения двух сегментов линии.

Unfortunantly код ниже dosen't работы, если один из сегмента вертикалы

public static Point intersection(Segment s1, Segment s2) { 
    double x1 = s1.getP1().getX(); 
    double y1 = s1.getP1().getY() ; 
    double x2 = s1.getP2().getX(); 
    double y2 = s1.getP2().getY() ; 
    double x3 = s2.getP1().getX(); 
    double y3 = s2.getP1().getY(); 
    double x4 = s2.getP2().getX(); 
    double y4 = s2.getP2().getY(); 

    double d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4); 
    if (d == 0) { 
     return null; 
    } 
    double xi = ((x3 - x4) * (x1 * y2 - y1 * x2) - (x1 - x2) * (x3 * y4 - y3 * x4))/d; 
    double yi = ((y3 - y4) * (x1 * y2 - y1 * x2) - (y1 - y2) * (x3 * y4 - y3 * x4))/d; 
    Point p = new Point(xi, yi); 
    if (xi < Math.min(x1, x2) || xi > Math.max(x1, x2)) { 
     return null; 
    } 
    if (xi < Math.min(x3, x4) || xi > Math.max(x3, x4)) { 
     return null; 
    } 
    return p; 
} 

проблема, когда я есть отрезок вертикальной линии, то эта формула

double d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4); 

равно 0 и метод возвращает null.

Как я могу справиться с этим исключением.

Спасибо

Answer 1

линия пересечения без особых случаях

Исходя из фона проективной геометрии, я написал бы точки в однородных координатах:

v1 = [x1, y1, 1] 
v2 = [x2, y2, 1] 
v3 = [x3, y3, 1] 
v4 = [x4, y4, 1] 

Тогда как линия объединение двух точек и пересечение двух линий можно выразить с использованием перекрестного произведения:

[x5, y5, z5] = (v1 × v2) × (v3 × v4) 

, которые вы можете dehomogenize найти результирующую точку как

[x5/z5, y5/z5] 

без необходимости иметь дело с какими-либо особыми случаями. Если ваши строки параллельны, последняя точка приведет к делению на ноль, хотя, возможно, вы захотите поймать этот случай.

Ограничение на сегменты

Выше для бесконечных линий, хотя. Возможно, вы захотите сохранить код, который возвращает null, если точка пересечения выходит за пределы ограничивающей рамки. Но если вам нужны реальные сегменты, этот код неверен: у вас может быть точка пересечения, которая лежит за пределами одного из сегментов, но все еще находится в ограничивающей рамке.

Правильная проверка может быть выполнена с использованием предиката, проверяющего ориентацию. Определитель трех из векторов vi, приведенных выше, будет иметь положительный знак, если образующийся треугольник имеет одну ориентацию и отрицательный знак для противоположной ориентации. Таким образом, точки v3 и v4 лежат на разных сторонах s1 если

det(v1, v2, v3) * det(v1, v2, v4) < 0 

и подобным же образом v1 и v2 лежат на разных сторонах s2 если

det(v3, v4, v1) * det(v3, v4, v2) < 0 

так, если оба из них удовлетворены, у вас есть пересечение между сегментами. Если вы хотите включить конечные точки сегмента, измените значение < на ≤ в этих неравенствах.

Answer 2

Я пробовал код без тестирования ... Надеюсь, это сработает!^^

public static Point intersection(Segment s1, Segment s2) { 
    // Components of the first segment's rect. 
    Point v1 = new Point(s1.p2.x - s1.p1.x, s1.p2.y - s1.p1.y); // Directional vector 
    double a1 = v.y; 
    double b1 = -v.x; 
    double c1 = v1.x * s1.p1.y - s1.v.y * s1.p1.x; 

    // Components of the second segment's rect. 
    Point v2 = new Point(s2.p2.x - s2.p1.x, s2.p2.y - s2.p1.y); 
    double a2 = v2.y; 
    double b2 = -v2.x; 
    double c2 = v2.x * s2.p1.y - s2.v.y * s2.p1.x; 

    // Calc intersection between RECTS. 
    Point intersection = null; 
    double det = a1 * b2 - b1 * a2; 
    if (det != 0) { 
     intersection = new Point(
      (b2 * (-c1) - b1 * (-c2))/det; 
      (a1 * (-c2) - a2 * (-c1))/det; 
     ); 
    } 

    // Checks ff segments collides. 
    if (
     intersection != null && 
     (
      (s1.p1.x <= intersection.x && intersection.x <= s1.p2.x) || 
      (s1.p2.x <= intersection.x && intersection.x <= s1.p1.x) 
     ) && 
     (
      (s1.p1.y <= intersection.y && intersection.y <= s1.p2.y) || 
      (s1.p2.y <= intersection.y && intersection.y <= s1.p1.y) 
     ) && 
     (
      (s2.p1.x <= intersection.x && intersection.x <= s2.p2.x) || 
      (s2.p2.x <= intersection.x && intersection.x <= s2.p1.x) 
     ) && 
     (
      (s2.p1.y <= intersection.y && intersection.y <= s2.p2.y) || 
      (s2.p2.y <= intersection.y && intersection.y <= s2.p1.y) 
     ) 
    ) 
     return intersection; 

    return null; 
};