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

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

Постановка задачи

На плоскости лежит [math]n[/math] отрезков, каждый из них задан координатами своих концов. Требуется по этим данным определить множество точек, в которых эти отрезки пересекаются. Однако, не всегда координаты точки можно абсолютно точно представить с помощью вещественных типов данных. Поэтому характеризовать каждую точку будем множеством отрезков, которые пересекаются в этой точке.

Для входных данных, представленных на рисунке, ответ будет следующий:Файл:Pic1.1

Для упрощения понимания введем два ограничения на входные данные:

• не существует вертикальных отрезков
• не существует пары отрезков, имеющих более одной общей точки

Как обрабатывать эти случаи будет объяснено позднее.

Алгоритм

Основная идея

Алгоритм будет основан на идее сканирующей прямой. Опишем три типа событий, которые мы и будем обрабатывать:

• начался новый отрезок
• два отрезка пересеклись
• отрезок закончился

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

Статус

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