Алгоритм Бентли – Оттмана

В вычислительной геометрии алгоритм Бентли-Оттмана представляет собой алгоритм прогонки линии для перечисления всех пересечений в наборе отрезков прямой , т.е. он находит точки пересечения (или, проще говоря, пересечения ) отрезков прямой. Он расширяет алгоритм Шамоса-Хоуи , аналогичный предыдущий алгоритм для проверки того, имеет ли набор отрезков прямых пересечения. Для входа, состоящего из $n$ отрезки линии с $k$ пересечениях (или пересечениях), алгоритм Бентли – Оттмана требует времени ${\mathcal {O}}((n+k)\log n)$. В случаях, когда $k={\mathcal {o}}\left({\frac {n^{2}}{\log n}}\right)$, это усовершенствование простого алгоритма, проверяющего каждую пару сегментов, что требует $\Theta (n^{2})$.

Алгоритм был первоначально разработан Джоном Бентли и Томасом Оттманном ( 1979 ); более подробно оно описано в учебниках Preparata & Shamos (1985) , O'Rourke (1998) и de Berg et al. (2000) . Хотя асимптотически более быстрые алгоритмы теперь известны Chazelle & Edelsbrunner (1992) и Balaban (1995) , алгоритм Бентли-Оттмана остается практическим выбором из-за его простоты и низких требований к памяти. .

Общая стратегия

Основная идея алгоритма Бентли-Оттмана заключается в использовании подхода с разверткой линии , при котором вертикальная линия L перемещается слева направо (или, например, сверху вниз) поперек плоскости, пересекая сегменты входной линии последовательно как оно движется. Алгоритм проще всего описать в его общем положении , означающем:

1. Никакие две конечные точки или пересечения отрезков не имеют одинаковой x. координаты
2. Ни одна конечная точка сегмента не лежит на другом сегменте.
3. Никакие три отрезка линии не пересекаются в одной точке.

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

В ходе симуляции могут произойти события двух типов. Когда L пересекает конечную точку отрезка s , пересечение L с s добавляется или удаляется из вертикально упорядоченного набора точек пересечения. Эти события легко предсказать, поскольку конечные точки уже известны из входных данных алгоритма. Остальные события происходят, когда L пересекает пересечение (или пересечение) двух отрезков s и t . Эти события также можно предсказать на основании того факта, что непосредственно перед событием точки пересечения L с s и t являются соседними в вертикальном порядке точек пересечения. .

Сам алгоритм Бентли-Оттмана поддерживает структуры данных, представляющие текущий вертикальный порядок точек пересечения линии развертки с входными сегментами линии, а также набор потенциальных будущих событий, образованных соседними парами точек пересечения. Он обрабатывает каждое событие по очереди, обновляя свои структуры данных для представления нового набора точек пересечения.

Структуры данных

Чтобы эффективно поддерживать точки пересечения линии развертки L с входными сегментами линии и последовательностью будущих событий, алгоритм Бентли-Оттмана поддерживает две структуры данных :

• Дерево двоичного поиска («дерево состояния линии развертки»), содержащее набор сегментов входной линии, которые пересекают L , упорядоченных по координатам y точек, где эти сегменты пересекают L . Сами точки пересечения не представлены явно в бинарном дереве поиска. Алгоритм Бентли-Оттмана вставит новый сегмент s в эту структуру данных, когда линия развертки L пересекает левую конечную точку p этого сегмента (т. е. конечную точку сегмента с наименьшей координатой x , при условии, что линия развертки L начинается с слева, как описано выше в этой статье). Правильное положение сегмента s в дереве двоичного поиска может быть определено с помощью двоичного поиска, каждый шаг которого проверяет, находится ли p выше или ниже какого-либо другого сегмента, который пересекает L . Таким образом, вставка может выполняться за логарифмическое время. Алгоритм Бентли-Оттмана также удаляет сегменты из двоичного дерева поиска и использует двоичное дерево поиска для определения сегментов, которые находятся непосредственно выше или ниже других сегментов; эти операции могут выполняться, используя только саму древовидную структуру, без привязки к базовой геометрии сегментов.

• Очередь приоритетов («очередь событий»), используемая для поддержания последовательности потенциальных будущих событий в алгоритме Бентли-Оттмана. Каждое событие связано с точкой p на плоскости, либо конечной точкой сегмента, либо точкой пересечения, и событие происходит, когда линия L проходит через p . Таким образом, событиям может быть присвоен приоритет по координатам x точек, связанных с каждым событием. В алгоритме Бентли-Оттмана потенциальные будущие события состоят из конечных точек сегментов прямой, которые еще не были пройдены, и точек пересечения пар линий, содержащих пары сегментов, которые находятся непосредственно выше или ниже друг друга.

Алгоритму не требуется явно поддерживать представление линии развертки L или ее положения в плоскости. Скорее, положение L представлено косвенно: это вертикальная линия, проходящая через точку, связанную с последним обработанным событием.

Дерево двоичного поиска может представлять собой любую сбалансированную структуру данных двоичного дерева поиска , например красно-черное дерево ; все, что требуется, это чтобы вставки, удаления и поиск занимали логарифмическое время. Аналогично, приоритетная очередь может представлять собой двоичную кучу или любую другую приоритетную очередь с логарифмическим временем; более сложные очереди приоритетов, такие как куча Фибоначчи, не нужны. Обратите внимание, что сложность пространства приоритетной очереди зависит от структуры данных, используемой для ее реализации.

Подробный алгоритм

Алгоритм Бентли-Оттмана выполняет следующие шаги.

1. Инициализируйте приоритетную очередь Q потенциальных будущих событий, каждое из которых связано с точкой на плоскости и имеет приоритет по координате x точки. Итак, изначально Q содержит событие для каждой конечной точки входных сегментов.
2. Инициализируйте самобалансирующееся двоичное дерево поиска T сегментов линии, которые пересекают линию развертки L , упорядоченную по координатам y точек пересечения. Первоначально T пуст. (Хотя линия L не представлена ​​явно, может быть полезно представить ее как вертикальную линию, которая изначально находится слева от всех входных сегментов.)
3. Пока Q непусто, найдите и удалите событие из Q , связанное с точкой p с минимальной координатой x . Определите тип события и обработайте его в соответствии со следующим анализом случая:
   • Если p конечная точка отрезка s , вставьте s в T. — левая Найдите отрезки r и t , которые находятся непосредственно выше и ниже s в T (если они существуют); если пересечение r и t (соседей s в структуре данных состояния) образует потенциальное будущее событие в очереди событий, удалите это возможное будущее событие из очереди событий. Если s пересекает r или t , добавьте эти точки пересечения как потенциальные будущие события в очередь событий.
   • Если p отрезка s , удалите s из T. — правая конечная точка Найдите отрезки r и t , которые (до удаления s ) находились соответственно непосредственно над и под ним в T (если они существуют). Если r и t пересекаются, добавьте эту точку пересечения как потенциальное будущее событие в очередь событий.
   • Если p — точка пересечения двух сегментов s и t (при этом s ниже t слева от пересечения), поменяйте местами s и t в T . После замены найдите сегменты r и u (если они существуют), которые находятся непосредственно ниже и выше t и s соответственно. Удалите все точки пересечения rs (т. е. точку пересечения между r и s ) и tu (т. е. точку пересечения между t и u ) из очереди событий, и, если r и t пересекаются или s и u пересекаются, добавьте эти точки пересечения в очередь событий.

Анализ

Алгоритм обрабатывает одно событие для каждой конечной точки или точки пересечения сегмента в отсортированном порядке. $x$-координаты этих точек, что можно доказать по индукции. Это следует из того, что, как только $i$событие было обработано, следующее событие (если это точка пересечения) должно быть пересечением двух сегментов, соседних в порядке сегментов, представленных $T$и поскольку алгоритм сохраняет все пересечения между соседними сегментами как потенциальные будущие события в очереди событий; поэтому правильное следующее событие всегда будет присутствовать в очереди событий. Как следствие, он правильно находит все пересечения входных сегментов линии — проблема, для решения которой он был разработан.

Алгоритм Бентли–Оттмана обрабатывает последовательность $2n+k$ события, где $n$ обозначает количество сегментов входной линии и $k$ обозначает количество пересечений. Каждое событие обрабатывается постоянным числом операций в дереве двоичного поиска и очереди событий, и (поскольку оно содержит только конечные точки сегментов и пересечения между соседними сегментами) очередь событий никогда не содержит более $3n$ события. Все операции требуют времени ${\mathcal {O}}(\log n)$. Следовательно, общее время работы алгоритма равно ${\mathcal {O}}((n+k)\log n)$.

Если пересечения, найденные алгоритмом, не нужно сохранять после того, как они были найдены, пространство, используемое алгоритмом в любой момент времени, равно ${\mathcal {O}}(n)$: каждый из $n$ сегменты входной строки соответствуют не более одному узлу двоичного дерева поиска T и, как указано выше, очередь событий содержит не более $3n$ элементы. Эта пространственная граница принадлежит Брауну (1981) ; исходная версия алгоритма была немного другой (она не убирала события пересечения из $Q$ когда какое-то другое событие приводит к тому, что два пересекающихся сегмента становятся несмежными), что приводит к использованию большего пространства.

Чен и Чан (2003) описали высокоэффективную версию алгоритма Бентли-Оттмана, которая кодирует большую часть информации путем упорядочивания сегментов в массиве, представляющем входные данные, требуя только ${\mathcal {O}}(\log ^{2}n)$ дополнительные ячейки памяти. Однако для доступа к закодированной информации алгоритм замедляется на логарифмический коэффициент.

Особое положение

В приведенном выше описании алгоритма предполагается, что сегменты линий не вертикальны, что конечные точки сегментов не лежат на других сегментах линий, что пересечения образуются только двумя сегментами линий и что никакие две точки событий не имеют одинаковую координату x . Другими словами, он не учитывает угловые случаи, т.е. предполагает общее положение концов входных отрезков. Однако эти общие предположения о положении неприемлемы для большинства применений пересечения отрезков прямой. Бентли и Оттманн (1979) предложили слегка исказить входные данные, чтобы избежать такого рода числовых совпадений, но не описали подробно, как выполнять эти возмущения. де Берг и др. (2000) более подробно описывают следующие меры по обработке входных данных особого положения:

• Разорвите связи между точками событий с одинаковой координатой x , используя координату y . События с разными координатами y обрабатываются, как и раньше. Эта модификация решает как проблему нескольких точек событий с одной и той же координатой x , так и проблему вертикальных сегментов: левая конечная точка вертикального сегмента определяется как точка с нижней координатой y , а также шаги, необходимые для обработки такого сегмента по существу такие же, как и для обработки невертикального сегмента с очень большим наклоном.
• Определите сегмент линии как замкнутый набор , содержащий его конечные точки. Таким образом, два сегмента линии, имеющие общую конечную точку, или сегмент линии, содержащий конечную точку другого сегмента, считаются пересечением двух сегментов линии.
• Если несколько сегментов линии пересекаются в одной точке, создайте и обработайте одну точку события для этого пересечения. Обновления двоичного дерева поиска, вызванные этим событием, могут включать удаление любых сегментов линий, для которых это правая конечная точка, вставку новых сегментов линий, для которых это левая конечная точка, и изменение порядка остальных сегментов линий, содержащих эту точку события. . Результат версии алгоритма, описанного де Бергом и др. (2000) состоит из набора точек пересечения отрезков прямой, помеченных сегментами, которым они принадлежат, а не из набора пар пересекающихся отрезков линии.

Похожий подход к вырождениям был использован в LEDA . реализации алгоритма Бентли – Оттмана в

Проблемы числовой точности

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

Более быстрые алгоритмы

O( n log n ) часть времени, ограниченная для алгоритма Бентли – Оттмана, необходима, поскольку существуют соответствующие нижние оценки для задачи обнаружения пересекающихся отрезков прямой в алгебраических моделях вычислений в виде дерева решений. Однако зависимость от k числа пересечений можно улучшить. Кларксон (1988) и Малмули (1988) предложили рандомизированные алгоритмы для построения плоского графа , вершины которого являются конечными точками и пересечениями отрезков прямых, а ребра — частями сегментов, соединяющих эти вершины, за ожидаемое время O( n log n + k ), и эта проблема построения аранжировки была решена детерминированно за то же время O( n log n + k ), ограниченное Шазелем и Эдельсбруннером. (1992) . Однако построение этой схемы в целом требует пространства O( n + k ), большего, чем граница пространства O( n ) алгоритма Бентли – Оттмана; Балабан (1995) описал другой алгоритм, который перечисляет все пересечения во времени O( n log n + k ) и пространстве O( n ).

Если входные отрезки прямой и их конечные точки образуют ребра и вершины связного графа O( n log n (возможно, с пересечениями), часть времени, ограниченного алгоритмом Бентли-Оттмана, также может быть уменьшена за ). Как показывают Кларксон, Коул и Тарьян (1992) , в этом случае существует рандомизированный алгоритм решения задачи за ожидаемое время O( n log* n + k ), где log * обозначает повторный логарифм , функцию, растущую гораздо медленнее. чем логарифм. Близкий рандомизированный алгоритм Эппштейна, Гудрича и Страша (2009) решает ту же проблему за время O( n + k log ^{( я )} n ) для любой константы i , где log ^{( я )} обозначает функцию, полученную путем итерации функции логарифма i раз. Первый из этих алгоритмов требует линейного времени, если k больше n в логарифмическом отношении. ^{( я )} n коэффициент для любой константы i , в то время как второй алгоритм занимает линейное время всякий раз, когда k меньше n в логарифмическом масштабе. ^{( я )} n фактор. Оба этих алгоритма включают применение алгоритма Бентли – Оттмана к небольшим случайным выборкам входных данных.

Ссылки

• Балабан, И.Дж. (1995), "Оптимальный алгоритм поиска пересечений отрезков", Proc. 11-й симпозиум ACM. Вычислительная геометрия , стр. 211–219, doi : 10.1145/220279.220302 , ISBN.  0-89791-724-3 , S2CID   6342118 .
• Бартушка, У.; Мельхорн, К. ; Нэхер, С. (1997), «Надежная и эффективная реализация алгоритма развертки линии для задачи пересечения отрезков прямой» , на итальянском языке, GF ; Орландо, С. (ред.), Proc. Воркш. Алгоритмическая разработка , заархивировано из оригинала 6 июня 2017 г. , получено 27 мая 2009 г. .
• Бентли, Джей Лей ; Оттманн, Т.А. (1979), «Алгоритмы отчетности и подсчета геометрических пересечений», IEEE Transactions on Computers , C-28 (9): 643–647, doi : 10.1109/TC.1979.1675432 , S2CID   1618521 .
• де Берг, Марк; ван Кревелд, Марк; Овермарс, Марк ; Шварцкопф, Отфрид (2000), «Глава 2: Пересечение отрезков прямой» , Вычислительная геометрия (2-е изд.), Springer-Verlag, стр. 19–44 , ISBN  978-3-540-65620-3 .
• Буассона, Ж.-Д.; Препарата, Ф.П. (2000), «Надежная развертка плоскости для пересекающихся сегментов» (PDF) , SIAM Journal on Computing , 29 (5): 1401–1421, doi : 10.1137/S0097539797329373 .
• Браун, KQ (1981), «Комментарии к «Алгоритмам отчетности и подсчета геометрических пересечений» », IEEE Transactions on Computers , C-30 (2): 147, doi : 10.1109/tc.1981.6312179 , S2CID   206622367 .
• Шазель, Бернар ; Эдельсбруннер, Герберт (1992), «Оптимальный алгоритм пересечения отрезков прямой на плоскости», Журнал ACM , 39 (1): 1–54, doi : 10.1145/147508.147511 , S2CID   785741 .
• Чен, EY; Чан, Т.М. (2003), «Экономичный алгоритм пересечения сегментов», Proc. 15-я Канадская конференция по вычислительной геометрии (PDF) .
• Кларксон, К.Л. (1988), "Применение случайной выборки в вычислительной геометрии, II", Proc. 4-й симпозиум ACM. Вычислительная геометрия , стр. 1–11, doi : 10.1145/73393.73394 , ISBN  0-89791-270-5 , S2CID   15134654 .
• Кларксон, КЛ ; Коул, Р.; Тарьян, Р.Э. (1992), «Рандомизированные параллельные алгоритмы для трапециевидных диаграмм», Международный журнал вычислительной геометрии и приложений , 2 (2): 117–133, doi : 10.1142/S0218195992000081 . Исправление, 2 (3): 341–343.
• Эппштейн, Д .; Гудрич, М .; Страш, Д. (2009), «Алгоритмы линейного времени для геометрических графов с сублинейным количеством пересечений», Proc. 20-й симпозиум ACM-SIAM. Дискретные алгоритмы (SODA 2009) , стр. 150–159, arXiv : 0812.0893 , Bibcode : 2008arXiv0812.0893E , doi : 10.1137/090759112 , S2CID   13044724 .
• Малмули, К. (1988), «Алгоритм быстрого планарного разбиения, I», Proc. 29-й симпозиум IEEE. Основы информатики (FOCS 1988) , стр. 580–589, doi : 10.1109/SFCS.1988.21974 , ISBN  0-8186-0877-3 , S2CID   34582594 .
• О'Рурк, Дж. (1998), «Раздел 7.7: Пересечение сегментов», Вычислительная геометрия на C (2-е изд.), Cambridge University Press, стр. 263–265, ISBN  978-0-521-64976-6 .
• Препарата, ФП ; Шамос, М.И. (1985), «Раздел 7.2.3: Пересечение отрезков прямых», Вычислительная геометрия: Введение , Springer-Verlag, стр. 278–287, Bibcode : 1985cgai.book.....P .
• Пах, Дж .; Шарир, М. (1991), «О вертикальной видимости в расположении сегментов и размере очереди в алгоритме очистки строк Бентли-Оттмана», SIAM Journal on Computing , 20 (3): 460–470, doi : 10.1137/0220029 , МР   1094525 .
• Шамос, Мичиган ; Хоуи, Дэн (1976), «Геометрические задачи пересечения», 17-я конференция IEEE. Основы информатики (FOCS 1976) , стр. 208–215, doi : 10.1109/SFCS.1976.16 , S2CID   124804 .

Внешние ссылки

• Смид, Михил (2003), Вычисление пересечений в наборе отрезков: алгоритм Бентли – Оттмана (PDF) .