Обобщение алгоритма Бентли-Оттмана

Question

Алгоритм Бентли-Оттмана используется для определения точки пересечения списка линий. Однако, как упомянуто здесь в Wiki , есть несколько недостатков:

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

У меня вопрос: может ли обобщение этого алгоритма преодолеть / преодолеть вышеуказанные трудности?

Answer 1

Это модификации алгоритма, предложенного Скантаком здесь: .

Алгоритм работает следующим образом: сначала создаются события для всех начальных и конечных точек входных сегментов. Затем он обрабатывает все события в отсортированном порядке.
Для каждого события он выбирает связанный список L сегментов, начинающихся в этой точке и находит и удаляет все сегменты в дереве поиска которые пересекают текущую точку события. Он сообщает все эти сегменты как пересечения в этой точке. Затем он переключает порядок функции сравнения изменив флаг, чтобы он был немного позже текущего события. Он вставляет все ранее удаленные сегменты, которые не имеют своей конечной точки в текущей точке события (потому что они должны быть удалены от структуры на данный момент в любом случае) и дополнительно вставьте сегменты от L (которые начинаются в этой точке). Проверяет верхних и нижних соседей выше и ниже текущей точки события для новых пересечений и добавляет их в качестве точек событий, если они найдены.
Таким образом, алгоритм является надежным против всех видов вырождений, включая вертикальные сегменты и перекрывающиеся сегменты, а также сегменты, пересекающиеся на своих конечных точках.

for all segments s do
  Create events for the endpoints of s
end for
while event queue not empty do
  Remove the smallest event point p from the queue
  Let L be the set of segments that start at p
  I ← all segments in the sweep line structure that contain p
  remove I from sweep line structure
  if |L| + |I| ≥ 2 then
     Report intersections of L ∪ I
  end if
  C ← {s ∈ I | p is not endpoint of s}
  Insert C in sweep line structure in reversed order
  Check for new intersections among segments above and below p
end while

Answer 2

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

• По соглашению точка находится слева от точки, расположенной вертикально над ней; таким образом, «левая» конечная точка вертикальной линии является ее нижней конечной точкой.
• События могут состоять из пересечений двух или более линий.
• Когда точка события достигнута, ее инцидентные сегменты должны быть обращены в линии развертки (не просто поменялись местами, так как их может быть больше двух).
• После обработки пересечения может быть более двух старых точек события, которые нужно удалить, или более двух новых точек события, которые нужно вставить.