228
правок
Изменения
→Реализация
==Реализация==
Здесь будут рассмотрены некоторые основные моменты реализации
Это только идейные реализации в коде все выглядет пример в 50 раз хуже.(по количеству строк)
===Класс "трапецоид"===
struct Trapezoid
Trapezoid next
Trapezoid up
Trapezoid down
Trapezoid end
Segment top
Segment bottom
Point left
Point right
===Построение трапецоидной карты===
TrapezoidMap(S - segments)
Строим оболочку(просто находим крайние точки множества отрезков по четырем направлениям)
Строим рандомную перестановку отрезков
for i 1 to n
do ищем множество трапецоидов пересекаемых отрезком s_i. //это специальная функция//
Удаляем это множество из карты и добавляем новые узлы появившиеся из-за s_i в поисковой структуре
Аналогично для просто карты
===Поиск трапецоидов, которых пересекает отрезок===
FOLLOWSEGMENT(s_i - segment)
Запоминаем левый и правый конец s_i
Делаем запрос на левый конец в карте.
j <tex>\leftarrow</tex> 0;
while q <tex>\in</tex> правый от rightp(трапецоид_j)
do if rightp(трапецоид_j) над si
then ставим трапецоид_(j+1) нижним правым соседом трапецоид_j.
else ставим трапецоид_(j+1) верхним правым соседом трапецоид_j.
j <tex>\leftarrow</tex> j+1
==Ссылки==
[http://graphics.stanford.edu/courses/cs268-09-winter/ Lecture notes from stanford, Seidel]
