Изменения

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

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

84 байта добавлено, 06:47, 9 декабря 2011
Нет описания правки
===В итоге===
[[Файл:anim1.gif|right|391|thumb|Пример работы алгоритма]]
Изначально у нас есть только события вида "начался отрезок" и "закончился отрезок". События вида "пересекаются два отрезка" будут добавляться нами в множество еще не обработанных событий. Соответственно, алгоритм выглядит так: выбираем то событие из множества необработанных, у которого наименьшая координата <tex>X</tex>, обрабатываем, делаем так, пока множество необработанных событий непустое. Плюс, на протяжении всего алгоритма должен поддерживаться следующий инвариант: в множество необработанных событий уже добавлены все пересечения отрезков, которые в текущем статусе текущие.
Анонимный участник

Навигация