Изменения

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

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

Нет изменений в размере, 06:46, 21 января 2012
Сканирующая точка
[[Файл:anim2.gif|right|560|thumb|Сканирующая точка]]
Слегка поменяем нашу концепцию. Сканирующая прямая теперь становится не совсем прямой. Теперь у нас появляется, скорее, сканирующая точка. Суть изменения в следующем: в случае, если несколько событий попадают на одну вертикальную прямую, мы их обрабатываем в порядке возрастания координаты по оси <tex>XY</tex>. Внимательный читатель сейчас, наверное, воскликнет: "А как же тогда наш статус? Ведь отрезки не могут пересекать точку!". Однако и это не является проблемой. Если отрезок, который лежит в статусе, не вертикален, то он сортируется по своей координате <tex>Y</tex>, в которой он пересекается с вертикальной прямой, проведенной через нашу точку (да, это бывшая сканирующая прямая). А вот если отрезок вертикален, то его параметром является как раз ордината "сканирующей точки". <s>Если внимательно подумать, то все будет корректно.</s>
===Несколько отрезков в одной точке===
Анонимный участник

Навигация