Изменения
Новая страница: «Алгоритм Бентли-Оттмана(англ. Bentley-Ottmann) - алгоритм, позволяющий по множеству отрезков на пл...»
Алгоритм Бентли-Оттмана(англ. Bentley-Ottmann) - алгоритм, позволяющий по множеству отрезков на плоскости получить множество точек, в которых эти отрезки пересекаются, при этом для каждой точки алгоритм выдает множество отрезков, пересекающихся в ней.
==Постановка задачи==
На плоскости лежит <tex>n</tex> отрезков, каждый из них задан координатами своих концов. Требуется по этим данным определить множество точек, в которых эти отрезки пересекаются. Однако, не всегда координаты точки можно абсолютно точно представить с помощью вещественных типов данных. Поэтому характеризовать каждую точку будем множеством отрезков, которые пересекаются в этой точке.
Для входных данных, представленных на рисунке, ответ будет следующий:[[Файл:pic1.1]]
Для упрощения понимания введем два ограничения на входные данные:
* не существует вертикальных отрезков
* не существует пары отрезков, имеющих более одной общей точки
Как обрабатывать эти случаи будет объяснено позднее.
====
==Постановка задачи==
На плоскости лежит <tex>n</tex> отрезков, каждый из них задан координатами своих концов. Требуется по этим данным определить множество точек, в которых эти отрезки пересекаются. Однако, не всегда координаты точки можно абсолютно точно представить с помощью вещественных типов данных. Поэтому характеризовать каждую точку будем множеством отрезков, которые пересекаются в этой точке.
Для входных данных, представленных на рисунке, ответ будет следующий:[[Файл:pic1.1]]
Для упрощения понимания введем два ограничения на входные данные:
* не существует вертикальных отрезков
* не существует пары отрезков, имеющих более одной общей точки
Как обрабатывать эти случаи будет объяснено позднее.
====
