Изменения

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

Участник:Muravyov

615 байт добавлено, 17:11, 5 мая 2012
Разбиение многоугольника на монотонные части
Теперь рассмотрим случай с пересечением добавленной ранее диагональю. Поскольку внутри <tex>H</tex> никаких вершин вершин находиться не может, и оба конца любой добавленной ранее диагонали должны лежать выше <tex>v_i</tex>, диагональ <tex>v_{i}v_m</tex> не может пересекать никакую из ранее добавленных диагоналей.
 
====== Прочие случаи ======
Для отдельных случаев, таких как полигон с дыркой, алгоритм тоже корректен. Вопрос лишь в том, как правильно в таком случае определить тип каждой вершины. Для этого нужно корректно задать внутреннюю область многоугольника, что по прежнему нам позволяет сделать список рёбер <tex>D</tex> и дерево <tex>T</tex>, описанные выше.
}}
184
правки

Навигация