Изменения

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

Триангуляция полигонов (ушная + монотонная)

2 байта добавлено, 18:25, 27 мая 2012
Структуры данных
В подходе, описанном выше, требуется находить пересечения заметающей прямой и левых ребёр многоугольника. Создадим двоичное дерево поиска <tex>T</tex>, в листьях которого будем хранить рёбра, пересекающие <tex>l</tex>, такие, что внутренняя область многоугольника будет лежать справа от них самих. С каждым таким ребром будем хранить его <tex>helper</tex>. Порядок следования листьев в дереве соответствует порядку следования рёбер в многоугольнике: слева направо. Дерево изменяется в зависимости от текущего состояния заметающей прямой. Создадим приоритетную очередь <tex>Q</tex> из вершин, в которой приоритетом будет <tex>y</tex>-координата вершины. Если две вершины имеют одинаковые <tex>y</tex>-координаты, больший приоритет у левой. Вершины будут добавляться на "остановках" заметающей прямой.
Многоугольник <tex>P</tex> и добавленные в процессе диагонали удобно хранить в виде спика списка <tex>D</tex> рёбер с двойными связями (''DCEL — doubly-connected edge list''), так как потом это обеспечит эффективный доступ к каждой из частей, которые нужно будет триангулировать.
===== Псевдокод =====
Анонимный участник

Навигация