304
правки
Изменения
Нет описания правки
На рисунке граница поисковой области помечена красной линией, допустимая область для упрощения - красной пунктирной линией, точки попавшие в итоговую цепь отображены черным.
<br clear="all"/>
==Алгоритм сохраняющий топологию==
Алгоритм сохраняющий топологию, как было упомянуто ранее, содержится в статье де Берга 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>.
==Ссылки==
