Алгоритм поиска пересечений прямой линии

Question

Я хотел бы найти все пересечения прямой (бесконечной). Я пытаюсь изменить алгоритм Бентли-Оттмана, который работает для множества сегментов линии, но я не знаю, как правильно представлять бесконечную прямую линию. Первая идея заключалась в определении граничных точек, которые могли бы имитировать начало и конец каждой из строк, но я полагаю, что это неправильное решение (как найти «бесконечные» точки?). Следующая идея заключается в использовании уравнений для представления прямых линий, но я не знаю, могу ли я использовать алгоритм Бентли-Оттмана (как упорядочить строки и добавить события к графику?). Более того, я, вероятно, должен использовать деление для обнаружения пересечения двух линий (при решении набора уравнений). Я бы хотел этого избежать.

Можете ли вы дать мне совет?

Большое спасибо

Answer 1

Предполагая, что вы делаете это в 2-мерном евклидовом пространстве, вы чрезмерно раздувая проблему. Старшие школьники расскажут вам, что линии могут быть представлены уравнением:

y = m*x + b 

Но он не может представлять вертикальную линию. Вы можете использовать более общие уравнения (см MathWorld):

a*x + b*y = c 

В двумерном евклидовом пространстве, две строки либо:

• Имеют одну общую точку; или
• Нет общей точки: они параллельны друг другу; или
• Имеют бесконечное количество общих точек: они являются одной и той же линией.

Первые 2 случая - это решение уравнения. Третий случай, если верно:

(вы, конечно, нужно обрабатывать случаи, когда a2 = 0 или b2 = 0)

Answer 2

Забудьте Bentley Ottman. Это умение иметь дело с линиями сегментами, которых у вас нет.

Если линии бесконечны, то каждая пара непараллельных линий будет иметь ровно одно пересечение. Так что если {L1, L2, ... Ln} есть множество всех строк, алгоритм:

for Li, i = 1, 2, ... n-1 
    for Lj, j = i+1, ... n 
    if Li parallel to Lj, output <i, j, PARALLEL> 
    else output <i, j, intersection(Li, Lj)> 

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

Самый надежный способ хранения произвольных линий (как уже упоминалось), коэффициент тройная:

<A, B, C> 

такие, что Ax + By + C = 0. Это удобно и хорошая практика, чтобы нормализовать так что^2 + B^2 = 1. Теперь [A, B] - единичная нормаль к прямой.С некоторой векторной математики это довольно легко видеть, что пересечение Р двух линий г и ч дается простой поперечному продукта:

P = [x/w, y/w], where [x,y,w] = [Ag, Bg, Cg] X [Ah, Bh, Ch] 

Обратите внимание, что для параллельного (включая совпадающие) линии, вы получите ш = 0, так что деление завершится неудачно, как вы ожидали. Вы можете использовать очень малые абсолютные значения w для определения параллельного случая выше. Это одна из причин нормализации [A, B]. Это делает его независимым от масштаба.