81
правка
Изменения
тире
Алгоритм Бентли-Оттмана(англ. Bentley-Ottmann) - — алгоритм, позволяющий по множеству отрезков на плоскости получить множество точек, в которых эти отрезки пересекаются, при этом для каждой точки алгоритм выдает множество отрезков, пересекающихся в ней.
==Постановка задачи==
===СНМ вместо отрезков===
'''Внимание! Этот раздел должен интересовать только <s>задротов</s> любознательных, так как он описывает разбор случая, который нам, по обещанию Ковалева, не встретится.'''
Нам остался последний сложный случай: наложение двух или более отрезков друг для друга. Давайте теперь вместо просто отрезков будем класть в СНМ следующее: множество отрезков, которые на данном этапе накладываются друг на друга. Понятно, что при добавлении нового отрезка он или создает свое множество, или добавляется в уже существующее. При удалении удаляется из множества, если оно осталось пустым - — удаляется и само множество. А при пересечении с другим множеством попарно пересекаются все отрезки из двух множеств. При этом важно, что все отрезки, накладывающиеся друг на друга, должны занимать в статусе одну ячейку, т. е. являться одним множеством.
==Реализация алгоритма==
===Реализация множества необработанных событий===
====Приоритетная очередь====
Опять же, эта идея возникает в процессе описания этого множества. При этом понятно, что точки сравниваются сначала по абсциссе, в случае равенства - — по ординате.
====Двоичное дерево поиска====
В принципе, вполне себе вариант реализации упорядоченного множества. Но его стоит использовать только тогда, когда мы хотим рассматривать пересечение нескольких отрезков в одной точке в качестве отдельного случая, а не как несколько попарных пересечений. Заметим, что это существенно усложняет реализацию.
