Алгоритм Бентли-Оттмана для двух групп отрезков линий

Question

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

Однако вместо того, чтобы находить точки пересечения всех линий между собой, я хочу найти точки пересечения между двумя группами линий.Это значит, что для каждой линии в группе A я хочу знать точки пересечения между этими линиями и линиями в группе B.

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

Редактировать: любые другие алгоритмы (не обязательно основанные на Bentley-Ottmann) приветствуются.Было бы лучше, если бы эти алгоритмы уже были реализованы в существующей библиотеке.

Answer 1

Вы можете найти все пересечения между всеми линиями в A+B, а затем удалить пересечения между линиями в одном наборе.Вы не сильно увеличиваете сложность, и это позволяет вам использовать библиотечную функцию CGAL без изменений только с помощью простой функции-оболочки.

Answer 2

Да Алгоритм Бентли-Оттмана может быть расширен для этого вместе с другими методами.

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

Вот статья, расширяющая развертку B-O до оптимального алгоритма. http://www.cs.unc.edu/~snoeyink/demos/rbseg/jcdcg25.pdf

Я бы не согласился с заявлением @ marcog о сложности. Связанная статья требует оптимального времени O (n log (n + k)), если вы отфильтруете пересечения, вам придется выполнить очистку BO по всем линиям, и это будет ((n + k) log n).

Существуют другие аналогичные алгоритмы, которые могут не требовать сложных структур данных http://www.cs.swarthmore.edu/~adanner/cs97/s08/pdf/palazzi93counting.pdf

Для меньшего числа ребер и меньшего количества пересечений между ребрами решение в ответе @ marcog может работать хорошо. (Вот пример из CGAL http://doc.cgal.org/latest/Arrangement_on_surface_2/Arrangement_on_surface_2_2consolidated_curve_data_8cpp-example.html).

Если вам нужно обработать сложные полигоны (данные ГИС и т. Д.) Или вам нужен общий алгоритм, этот класс алгоритмов может стоить того.

Answer 3

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

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

Рабочий пример (код C).https://developer.blender.org/diffusion/B/browse/master/source/blender/blenlib/intern/BLI_kdopbvh.c;3b4a8f1cfa7339f3db9ddd4a7974b8cc30d7ff0b$1089

Если имеется много небольших сегментов (например, путь нарисованной от руки линии), это будет достаточно эффективным.Однако, если есть много длинных ребер (подумайте, пикапы) ... это будет работать плохо, и вы захотите разделить конечные узлы в дереве BVH, чтобы получить лучшую производительность.Однако, если это так, вероятно, лучше использовать другой метод, как предлагается в других ответах.

Answer 4

Там, где Bentley-Ottman хранит дерево отрезков, упорядоченное по их текущему вертикальному положению, вы не могли бы сохранить два дерева, по одному для групп A и B?Затем, когда исходный алгоритм проверяет соседей выше и ниже текущей точки, вы проверяете соседа А сверху и соседа В ниже и наоборот.

Это основано на быстром просмотреСтатья в википедии;За последнее десятилетие я не написал много геометрического кода.