Существует ли эффективный алгоритм для нахождения всех пересечений множества бесконечных линий?

Question

Существуют эффективные (по сравнению с O (n ² ) парное тестирование) алгоритмы для нахождения всех пересечений в наборе отрезков, такие как алгоритм Бентли-Оттмана.Тем не менее, я хочу найти все пересечения во множестве бесконечных линий.Когда интересующая область является чем-то конечным, например, прямоугольником, алгоритмы пересечения отрезков линий могут применяться после обрезки линий.Но

• Есть ли более простой или более эффективный способ, чем просто обрезка линий и применение алгоритмов пересечения отрезков?
• Существует ли эффективный алгоритм для всех пересечений по всей плоскости длянабор линий?

Answer 1

В общем случае (не все линии параллельны) есть O (n ^ 2) пересечений, поэтому простой цикл с вычислением пересечений является лучшим подходом
(нет способа получить n*(n-1)/2 точек без вычислений)

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

Answer 2

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