Изменения

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

Участник:Muravyov

40 байт добавлено, 20:02, 2 мая 2012
Структура
===== Структура =====
В подходе, описанном выше, требуется находить пересечения заметающей прямой и левых ребёр многоугольника. Создадим BST двоичное дерево поиска <tex>T</tex>, в листьях которого будем хранить рёбра, пересекающие <tex>l</tex>? такие, что внутренняя область многоугольника будет лежать справа от них самих. С каждым таким ребром будем хранить его <tex>helper</tex>. Порядок следования листьев в дереве соответствует порядку следования рёбер в многоугольнике : слева направо соответствует порядку следования листьев в дереве. Дерево изменяется в зависимости от текущего состояния заметающей прямой. Создадим приоритетную очередь <tex>Q</tex> из вершин, в которой приоритетом будет <tex>y</tex>-координата вершины. Если две вершины имеют одинаковые <tex>y</tex>-координаты, больший приоритет у левой. Вершины будут добавляться на "остановках" заметающей прямой.
Многоугольник <tex>P</tex> удобно хранить в виде двусвязного спика <tex>D</tex> рёбер и добавленных в процессе диагоналей, так как потом это обеспечит эффективный доступ к каждой из частей, которые нужно будет триангулировать.
 
==== Триангуляция монотонного многоугольника ====
184
правки

Навигация