Изменения

Перейти к: навигация, поиск

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

128 байт убрано, 23:46, 3 декабря 2011
Нет описания правки
==Постановка задачи==
[[Файл:pic1.jpg|right|391|thumb|Пример результата работы алгоритма]]
На плоскости лежит <tex>n</tex> отрезков, каждый из них задан координатами своих концов. Требуется по этим данным определить множество точек, в которых эти отрезки пересекаются. Однако, не всегда координаты точки можно абсолютно точно представить с помощью вещественных типов данных. Поэтому характеризовать каждую точку будем множеством отрезков, которые пересекаются в этой точке.
 
Для входных данных, представленных на рисунке, ответ будет следующий:[[Файл:pic1.jpg|right|391|thumb|Пример результата работы алгоритма]]
Для упрощения понимания введем два ограничения на входные данные:
40
правок

Навигация