304
правки
Изменения
→Алгоритм сохраняющий топологию
==Алгоритм сохраняющий топологию==
Алгоритм сохраняющий топологию, как было упомянуто ранее, содержится в статье де Берга A New Approach to Subdivision Simplification, где расскрываются также детали реализации, здесь же мы опишем идею описывается идея алгоритма. Также стоит обратить внимание, что исходная полигональная цепь должна быть без самопересечений.
Алгоритм делится на три четыре основных этапа:
*Создание графа <tex>G_1</tex>, в котором помимо исходных ребер, добавлены все возможные сокращенные ребра. Иначе говоря ребра, для который верно, что <tex>i < j</tex> и для любого <tex>t</tex>, такого что <tex>i < t < j</tex>, верно <tex>distance(V_t, \overline{V_iV_j}) \le \varepsilon</tex>.
*Создание графа <tex>G_2</tex>, в котором добавлены все возможные ребра, с учетом того, что каждое новое добаленное ребро не пересечет любое из предыдущих. На этом этапе построение выполняется без учета <tex>\varepsilon</tex>.
*Создание графа <tex> G = G_1 \cap G_2</tex>, в котором будет содержаться кратчайшая полигональная цепь без самопересечений по построению <tex>G_1</tex> и <tex>G_2</tex>.
*Поиск кратчайшего пути в <tex>G</tex>, как в невзвешенном графе, этот путь и будет являться ответом на задачу.
==Ссылки==
