Далекие точки пересечения для почти параллельных линий

Question

Я рисую большое количество связанных ребер на холсте, все из которых расположены таким образом, что некоторое конкретное расширение этих краев всегда дает точку пересечения с другим расширенным краем , Эта точка необходима для дальнейших вычислений - она ​​не актуальна в контексте того, что появляется на холсте. Мой код отлично подходит для общего случая, но если соответствующие расширения края выходят далеко, пересечения не всегда существуют (однако строки не параллельны) - по крайней мере, не в рамках этой программы. У кого-нибудь есть идеи улучшить точность этого кода? Я действительно работаю с BigDecimals позже, но для шагов построения я изначально думал, что достаточно использовать double.

Этот расширяет край к обеим сторонам:

public Line2D.Double ExteLine(Point2D p, Point2D q){ 
    double slope, y3, y4; 
    slope = (q.getY() - p.getY())/(q.getX() - p.getX()); 
    y3 = (slope * (100000 - p.getX())) + p.getY(); 
    y4 = (slope * (-100000 - p.getX())) + p.getY(); 
    Point2D out1 = new Point2D.Double(100000, y3); 
    Point2D out2 = new Point2D.Double(-100000, y4); 
    Line2D.Double line = new Line2D.Double(out1, out2); 
    return line; } 

Это один находит пересечение:

public Point2D.Double getIntersectionPoint(Line2D.Double line1, Line2D.Double line2) { 
if (! line1.intersectsLine(line2)) { 
    System.out.println("No intersection"); 
    return null;} 
    double s1 = line1.getX1(), 
     sp2 = line1.getY1(), 
     rx = line1.getX2()-s1, 
     ry = line1.getY2()-sp2; 
    double qx = line2.getX1(), 
     qy = line2.getY1(), 
     sx = line2.getX2()-qx, 
     sy = line2.getY2()-qy; 
    double det = sx*ry - sy*rx; 
    if (det == 0) { System.out.println("Det = 0"); 
    return null;} 
    else { 
    double z = (sx*(qy-sp2)+sy*(s1-qx))/det; 
    if (z==0 || z==1) return null; 
    return new Point2D.Double(
     (double)(s1+z*rx), (double)(sp2+z*ry)); 
    } 
} 

Answer 1

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

• Точка (x, y) в плоскости будет гомогенизирована (x, y, 1).
• Умножения, представляющие одну и ту же точку, поэтому вы можете написать это как (2x, 2y, 2).
• Линия ax + by + c = 0 представляется в виде (a, b, c).
• Точка с однородными координатами p = (x, y, z) лежит на прямой g = (a, b, c) тогда и только тогда, когда их точечный продукт p · g = ax + на + cz равен нулю. (Вам, вероятно, это не понадобится, поскольку сравнение для равенства с удвоениями всегда сложно, но это объясняет, почему другие шаги работают так же, как и они.)
• Линия, соединяющая две точки, может быть вычислена как перекрестное произведение их однородных координаты.
• Точка пересечения между двумя линиями также может быть вычислена как поперечный разрез координат этих линий.
• Поскольку вышеупомянутые шаги всегда умножаются, ваши двойные числа могут переполняться, если вы объедините несколько из них. Поэтому время от времени масштабируйте свои векторы, например. умножая их на некоторый скаляр, так что их запись с наибольшим абсолютным значением становится 1 или что-то еще.
• Если вы хотите нарисовать точку (x, y, z) на холсте, вы вычислите (x/z, y/z) и нарисуете это.
• Если z = 0, то предыдущий шаг невозможен. Это представляет собой точку «на бесконечности».
• Если x = y = z = 0 или a = b = c = 0, то вектор не представляет собой точку или. а вместо этого - вырожденная ситуация. Например. вы пытались вычислить линию, соединяющую точку с самим собой.

Как вы можете видеть, это довольно просто реализовать, и что еще лучше: вам не нужны какие-либо различия в любом случае! Для фактического рисования вам может понадобиться пересечь строки с границами вашего холста, а затем использовать линии, соединяющие эти пересечения, в качестве определения ваших графических примитивов.