1632
правки
Изменения
м
[[Файл:tmp.gif]]
rollbackEdits.php mass rollback
Алгоритм Бентли-Оттмана(англ. Bentley-Ottmann) - — алгоритм, позволяющий по множеству отрезков на плоскости получить множество точек, в которых эти отрезки пересекаются, при этом для каждой точки алгоритм выдает множество отрезков, пересекающихся в ней.
==Постановка задачи==
[[Файл:pic1.jpg|right|391560|thumb|Пример результата работы алгоритма]]
На плоскости лежит <tex>n</tex> отрезков, каждый из них задан координатами своих концов. Требуется по этим данным определить множество точек, в которых эти отрезки пересекаются. Однако, не всегда координаты точки можно абсолютно точно представить с помощью вещественных типов данных. Поэтому характеризовать каждую точку будем множеством отрезков, которые пересекаются в этой точке.
Для упрощения понимания введем два три ограничения на входные данные:
* не существует вертикальных отрезков
* не существует пары отрезков, имеющих более одной общей точки
* никакие три отрезка не пересекаются в одной точке
Как обрабатывать эти случаи , будет объяснено позднее.
==Алгоритм==
===Статус===
[[Файл:pic2.jpg|right|391560|thumb|Иллюстрация определения статуса]]Назовем статусом множество, в которой котором содержатся все отрезки, пересекающие нашу сканирующую прямую. Важно, что эти отрезки должны быть упорядочены по возрастанию (или убыванию) координаты их пересечения с прямой. Заметим, что в процессе работы алгоритма отрезки могут добавляться в произвольные места этого упорядоченной упорядоченного множества, удаляться из произвольных мест или меняться местами друг с другом.
===Важная мысль===
===В итоге===
[[Файл:anim1.gif|right|560|thumb|Пример работы алгоритма]]
Изначально у нас есть только события вида "начался отрезок" и "закончился отрезок". События вида "пересекаются два отрезка" будут добавляться нами в множество еще не обработанных событий. Соответственно, алгоритм выглядит так: выбираем то событие из множества необработанных, у которого наименьшая координата <tex>X</tex>, обрабатываем, делаем так, пока множество необработанных событий непустое. Плюс, на протяжении всего алгоритма должен поддерживаться следующий инвариант: в множество необработанных событий уже добавлены все пересечения отрезков, которые в текущем статусе текущие.
==Обработка "нехороших случаев"==
===Сканирующая точка===
Решим, для начала, вопрос с вертикальными отрезками. Важно, что заодно пропадет и проблема с обработкой событий, имеющих одинаковую координату по оси <tex>X</tex>.
[[Файл:anim2.gif|right|560|thumb|Сканирующая точка]]Слегка поменяем нашу концепцию. Сканирующая прямая теперь становится не совсем прямой. Теперь у нас появляется, скорее, сканирующая точка. Суть изменения в следующем: в случае, если несколько событий попадают на одну вертикальную прямую, мы их обрабатываем в порядке возрастания координаты по оси <tex>XY</tex>. Внимательный читатель сейчас, наверное, воскликнет: "А как же тогда наш статус? Ведь отрезки не могут пересекать точку!". Однако и это не является проблемой. Если отрезок, который лежит в статусе, не вертикален, то он сортируется по своей координате <tex>Y</tex>, в которой он пересекается с вертикальной прямой, проведенной через нашу точку (да, это бывшая сканирующая прямая). А вот если отрезок вертикален, то его параметром является как раз ордината "сканирующей точки". <s>Если внимательно подумать, то все будет корректно.</s>Здесь должна быть анимашка, в которой показывается, что все будет корректно.
===Несколько отрезков в одной точке===
===СНМ вместо отрезков===
'''Внимание! Этот раздел должен интересовать только <s>задротов</s> любознательных, так как он описывает разбор случая, который нам, по обещанию Ковалева, не встретится.'''
Нам остался последний сложный случай: наложение двух или более отрезков друг для друга. Давайте теперь вместо просто отрезков будем класть в СНМ следующее: множество отрезков, которые на данном этапе накладываются друг на друга. Понятно, что при добавлении нового отрезка он или создает свое множество, или добавляется в уже существующее. При удалении удаляется из множества, если оно осталось пустым - — удаляется и само множество. А при пересечении с другим множеством попарно пересекаются все отрезки из двух множеств. При этом важно, что все отрезки, накладывающиеся друг на друга, должны занимать в статусе одну ячейку, т. е. являться одним множеством.
==Реализация алгоритма==
===Двоичное дерево поиска в качестве статуса===
Из определения статуса ясно, какую структуру удобно использовать в качестве статуса: двоичное дерево поиска. В нем удобно делать все необходимые операции, и выполняться они будут за <tex>O(\log_2(n))</tex>.
===Реализация множества необработанных событий===
====Приоритетная очередь====
Опять же, эта идея возникает в процессе описания этого множества. При этом понятно, что точки сравниваются сначала по абсциссе, в случае равенства - — по ординате.
====Двоичное дерево поиска====
В принципе, вполне себе вариант реализации упорядоченного множества. Но его стоит использовать только тогда, когда мы хотим рассматривать пересечение нескольких отрезков в одной точке в качестве отдельного случая, а не как несколько попарных пересечений. Заметим, что это существенно усложняет реализацию.
===Наконец, абсолютная точность===
Заметим, что мы не умеем получать абсолютно точные координаты пересечения двух отрезков. Однако, мы умеем представлять эти координаты в качестве суммы произведений нескольких чисел (просто пересечение прямых и раскрытие скобок в верхней части дроби). А сами координаты нам и не требуются, нам необходимо только уметь сравнивать эти координаты друг с другом. Сравнивать же эти суммы произведений с другими такими же суммами и с обычными числами (в обобщенном представлении тоже такими же суммами) мы тоже умеем. Победа!
[[Категория: Вычислительная геометрия]]
