Найти пересечение двух точечных серий?

Question

Линия здесь определена как серия двумерных узлов. Теперь у меня есть две такие строки: A и B.

A=[(0, 0), (1, 1), (2.1, 3), (4,7)] 
B=[(2, 0), (2, 6)] 

Когда один рисует их на бумаге, можно легко увидеть, что две линии пересекаются в точке, которая является НЕ членом узла либо A или B.

Однако, оба A и Bдействительно пересекают этот пункт. То есть точка действительно лежит как на A, так и на B, просто не сталкивайтесь с узлами.

Теперь я хочу найти точку пересечения.

(нежное напоминание еще раз: пересечение на A и B, но это не может быть узлом)

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

Есть ли какой-нибудь умный способ сделать это?

Я говорю на Python, но любые общие ответы также очень приветствуются.

Answer 1

for i in range(0, len(A), 2): 
    line1 = A[i:i+2] 
    for j in range(0, len(B), 2): 
     line1 = A[j:j+2] 
     point_of_intersect = intersection(line1, line2) 
     if point_of_intersect: 
      print point_of_intersect 

где функция intersection определяется в соответствии с this Wikipedia entry.

Answer 2

Имея 2 очка X(x1, x2), Y(y1, y2), можно определить уравнение линии, такие как:

(x-x1)/(x2-x1) = (y-y1)/(y2-y1) 

ли это для линии А и линии В.

Вы получите по строке

A: y = m1*x+n1 
B: y = m2*x+n2 

Теперь вам нужно просто найти значение y и x, которое соответствует двум вышеупомянутым уравнениям.

Answer 3

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

Наиболее распространенным решением этой проблемы является алгоритм Bentley-Ottman. Легко искать в Интернете псевдо-код или даже библиотеки, которые его реализуют; это простой алгоритм развертки, время выполнения которого равно O((n + k) log n), где n - это количество сегментов линии (сумма сегментов в обеих строках) и k - это число пересечений. Если вы хотите узнать, есть ли какие-либо пересечения, вы можете остановиться на первом найденном пересечении, после чего алгоритм сводится к O(n log n).

Предполагается, что вы знаете, что A и B не содержат внутренних переездов. Наивная реализация Bentley-Ottman (где два набора сегментов линии обрабатываются без разбора) будет сообщать обо всех переходах, включая самопересечения.