304
правки
Изменения
Нет описания правки
==Задача==
Дана некоторая аппроксимированная кривая, заданная последовательностью точек, и некоторое <tex>\varepsilon</tex>. Требуется ответить, какие точки мы можем оставить, так чтобы расхождение между исходной и получившейся кривыми не превышало <tex>\varepsilon</tex>, при этом количество точек в получившейся кривой должно стремиться к минимуму.
Существует также альтернативная задача, при которой вместо <tex>\varepsilon</tex> задано число <tex>k</tex> вершин в итоговой цепи.
==Мотивация==
Такая задача встречается при обработки векторной графики и построении карт. Расмотрим пример для построения карт. Дан путь из Москвы Например, есть цепь, несколько точек которой попадают в Санкт-Петербург, заданный точками через каждый километр путиодин и тот же пиксель. В масштабах всей России такая точность явно ни к чемуОчевидно, стоит оставить лишь что тогда можно упростить все эти точки, отражающие ключевые участки путив одну. В этом случае и пригодится упрощение, одним из вариантов реализации которого является алгоритм Дугласа-Пекера (Douglas-Peucker). В случае, когда у нас есть несколько устройств с разным dpi, например монитор и принтер, то, решив альтернативную задачу, можно адаптировать одну и ту же цепь для разных устройств.
==Алгоритм Дугласа-Пекера==
<br clear="all"/>
===Решение альтернативной задачи===
==Обзор ускорения работы алгоритма Дугласа-Пекера==
Как описано выше, в худшем случае алгоритм работает за <tex>O(n^2)</tex>. Можно внести дополнения, которые позволят получить <tex>O(n\log n)</tex> в худшем случае. Ускорение основывается на уменьшении времени поиска наиболее удаленной вершины. Это можно осуществить благодаря идее о том, что наиболее удаленная вершина лежит на выпуклой оболочке полигональной цепи.
