Алгоритм Бентли-Оттмана
Алгоритм Бентли-Оттмана(англ. Bentley-Ottmann) - алгоритм, позволяющий по множеству отрезков на плоскости получить множество точек, в которых эти отрезки пересекаются, при этом для каждой точки алгоритм выдает множество отрезков, пересекающихся в ней.
Постановка задачи
На плоскости лежит отрезков, каждый из них задан координатами своих концов. Требуется по этим данным определить множество точек, в которых эти отрезки пересекаются. Однако, не всегда координаты точки можно абсолютно точно представить с помощью вещественных типов данных. Поэтому характеризовать каждую точку будем множеством отрезков, которые пересекаются в этой точке.
Для входных данных, представленных на рисунке, ответ будет следующий:Файл:Pic1.1
Для упрощения понимания введем два ограничения на входные данные:
- не существует вертикальных отрезков
- не существует пары отрезков, имеющих более одной общей точки
- никакие три отрезка не пересекаются в одной точке
Как обрабатывать эти случаи будет объяснено позднее.
Алгоритм
Основная идея
Алгоритм будет основан на идее сканирующей прямой. Опишем три типа событий, которые мы и будем обрабатывать:
- начался новый отрезок
- два отрезка пересеклись
- отрезок закончился
Сканирующая прямая будет расположена параллельно оси ординат, и двигаться вдоль оси абсцисс в сторону ее положительного направления. Учитывая введенные ограничения на входные данные, прямая никогда не будет проходить через два события одновременно.
Статус
Назовем статусом множество, в которой содержатся все отрезки, пересекающие нашу сканирующую прямую. Важно, что эти отрезки должны быть упорядочены по возрастанию (или убыванию) координаты их пересечения с прямой. Заметим, что в процессе работы алгоритма отрезки могут добавляться в произвольные места этого упорядоченной множества, удаляться из произвольных мест или меняться местами друг с другом.
Важная мысль
Попробуем найти событие, которое случится раньше всех других, если наша прямая уже пересекает какие-то отрезки. Нам, в данный момент, интересен случай, когда это событие является пересечением отрезков. Важно, что в этом пересечении участвуют два отрезка, которые обязательно являются соседними в нашем статусе.
Доказательство
Предположим, что это не так. Значит, между этими двумя пересекающимися отрезками существует еще хотя бы один. Поскольку эти два отрезка пересекаются, то или третий пересекает перед их пересечением один из них, или пересекается с ними в той же точке. В любом случае, Важная мысль верна
В итоге
Изначально у нас есть только события вида "начался отрезок" и "закончился отрезок". События вида "пересекаются два отрезка" будут добавляться нами в множество еще не обработанных событий. Соответственно, алгоритм выглядит так: выбираем то событие из множества необработанных, у которого наименьшая координата , обрабатываем, делаем так, пока множество необработанных событий непустое. Плюс, на протяжении всего алгоритма должен поддерживаться следующий инвариант: в множество необработанных событий уже добавлены все пересечения отрезков, которые в текущем статусе текущие.
Обработка событий
Событие "начало отрезка"
Находим в статусе два отрезка, между которыми будет находится тот, который начинается. После этого добавляем его в статус на это место и точки его пересечения с соседними добавляем в множество необработанных событий.
Событие "конец отрезка"
Находим в статусе отрезок, который заканчивается. Удаляем его оттуда, после чего в множество необработанных событий добавляем точку, в которой пересекаются отрезки, которые были соседями заканчивающегося в старом статусе. Это необходимо, потому что в новом статусе они станут соседними. Заметим, что добавляемое событие может уже находиться в множестве, но нас это совершенно не напрягает.
Событие "пересечение отрезков"
Находим в статусе два отрезка, которые пересекаются. Меняем их местами (это действительно происходит). После этого добавляем в множество пересечения двух новых пар соседей, которые появились после перестановки пересекшихся отрезков.
Обработка "нехороших случаев"
Сканирующая точка
Решим, для начала, вопрос с вертикальными отрезками. Важно, что заодно пропадет и проблема с обработкой событий, имеющих одинаковую координату по оси .
Слегка поменяем нашу концепцию. Сканирующая прямая теперь становится не совсем прямой. Теперь у нас появляется, скорее, сканирующая точка. Суть изменения в следующем: в случае, если несколько событий попадают на одну вертикальную прямую, мы их обрабатываем в порядке возрастания координаты по оси . Внимательный читатель сейчас наверное воскликнет: "А как же тогда наш статус? Ведь отрезки не могут пересекать точку!". Однако и это не является проблемой. Если отрезок, который лежит в статусе, не вертикален, то он сортируется по своей координате , в которой он пересекается с вертикальной прямой, проведенной через нашу точку (да, это бывшая сканирующая прямая). А вот если отрезок вертикален, то его параметром является как раз ордината "сканирующей точки". Если внимательно подумать, то все будет корректно.Здесь должна быть анимашка, в которой показывается, что все будет корректно.
СНМ вместо отрезков
Внимание! Этот раздел должен интересовать только задротов любознательных, так как он описывает разбор случая, который нам, по обещанию Ковалева, не встретится.
