Изменения

Упрощение полигональной цепи {{---}} процесс, позволяющий уменьшить число точек кривой, аппроксимированной серией точекполилинии.

Дана некоторая аппроксимированная криваяполилиния, заданная последовательностью точек<tex> a_1, a_2, ..., a_n</tex>, и некоторое <tex>\varepsilon</tex>. Требуется ответитьнайти цепь <tex> a_1, a_i, a_j, какие точки мы можем оставить..., a_n </tex>, так чтобы расхождение между являющейся подпоследовательностью исходной . Для этой цепи верно, что для всех <tex>k</tex>, таких что <tex> i < k < j:</tex> <tex>\rho(a_k, Segment(a_i, a_j)) \le \varepsilon</tex> для любых соседних <tex>i</tex> и получившейся кривыми не превышало <tex>j</tex>. Существует также альтернативная задача, в которой вместо <tex>\varepsilon</tex> задано число <tex>k</tex> вершин в итоговой цепи. В этом случае требуется составить цепь <tex> a_1, a_i, a_j, ..., a_n </tex> заданной длины таким образом, что максимально необходимое <tex>\varepsilon</tex> для условия <tex> \rho(a_k, Segment(a_i, a_j)) \le \varepsilon</tex>было минимально. Также упрощение можно выполнять с помощью введения новой полилинии, не сохраняющей точки исходной, при этом количество точек в получившейся кривой должно стремиться к минимумуно такая вариация задачи рассмотрена не будет.

В случае, когда у нас есть несколько устройств с разным dpi, например , монитор и принтер, то, решив альтернативную задачувзяв за <tex>\varepsilon</tex> половину расстояния, которое помещается на одной из границ пикселя, можно адаптировать мы можем растеризовать одну и ту же цепь для разных устройств.

Алгоритму задается исходная ломаная полилиния и максимальное расстояние, которое может быть между исходной и упрощённой ломаными полилиниями (то есть , максимальное расстояние от точек исходной ломаной к ближайшему участку полученной ломанойполилинии). Упрощенная ломаная полилиния состоит из подмножества точек, которые определяются из исходной ломаная.

Начальная ломаная полилиния представляет собой упорядоченный набор точек.

Алгоритм рекурсивно делит ломануюполилинию. Входом алгоритма служат координаты всех точек между первой и последней включая их, а так же <tex>\varepsilon</tex>. Первая и последняя точка сохраняются неизменными. После чего алгоритм находит точку, наиболее удалённую от отрезка, состоящего из первой и последней (оптимальный способ поиска расстояния от точки до отрезка рассмотрен ниже). Если точка находится на расстоянии, меньше , чем <tex>\varepsilon</tex>, то все точки, которые ещё не были отмечены к сохранению, могут быть выброшены из набора , и получившаяся прямая сглаживает кривую с точностью не ниже <tex>\varepsilon</tex>.

Если же расстояние больше <tex>\varepsilon</tex>, то алгоритм рекурсивно вызывает себя на наборе от начальной до данной и от данной до конечной точек (что означает, что данная точка будет отмечена к сохранению).

По окончанию всех рекурсивных вызовов выходная ломаная итоговая полилиния строится только из тех точек, что были отмечены к сохранению.

ЛинияПолилиния, полученная в результате работы алгоритма, отражается черной пунктирной линией.    

Ожидаемая сложность алгоритма может быть оценена выражением <tex>\Theta(n\log n)</tex> в лучшем случае, когда номер наиболее удаленной точки всегда оказывается лексикографически центральным. Однако , в худшем случае сложность алгоритма составляет <tex>O(n^2)</tex>. Это достигается, например, в случае, когда если номер наиболее удаленной точки всегда соседний к номеру граничащей граничной точки.

К сожалению, алгоритм Дугласа-Пекера в ходе своей работы не сохраняет топологию. Это означает, что означает в ответе мы можем получить линию с самопересечениями.

В статье де Берга (de Berg) ''[http://www.bowdoin.edu/~ltoma/teaching/cs350/spring06/Lecture-Handouts/deberg95new.pdf "A New Approach to Subdivision Simplification "]''(1995) приведен алгоритм, позволяющий решать чуть более общую задачу , чем текущая, : упрощение полигональной цепи с учетом обязательных особых точек, не входящих в нее, и с учетом топологии. Можно использовать алгоритм и для текущего случая , задав множество особых точек пустыйпустым. Время работы алгоритма при этом составит <tex>O(n^2\log n)</tex>. Краткое описание алгоритма дано ниже.

Алгоритм может находить не минимальный по количеству точек ответ. Рассмотрим пример, где в котором исходная линия с некоторым приближением будет представлять полуокружность. Мы можем подобрать такое <tex>\varepsilon</tex>, что алгоритм добавит три точки помимо стартовой и конечной (точки через каждую четверть исходной линии), в то же время мы можем взять две точки через

Альтернативную задачу Решение альтернативной задачи очень схоже с заданным числом <tex>k</tex> оптимально решать такисходном алгоритмом. На каждой итерации алгоритм находит подучасток исходной цепи, что в итоговой цепи останутся лишь на котором расстояние до наиболее значимые удаленной точки. Алгоритм начинается максимально, делит ее так же как и в исходном алгоритме и запоминает полученные в результате деления подучастки для обычной задачи. Теперь каждый раз выберается та часть, у которой наиболее удаленная вершина находится на большем расстоянии относительно таких же вершин других частейследующих итераций. Алгоритм завершитсястартует, когда будет итоговая для выбора доступна только исходная цепь будет состоять из требуемого числа точек.

Если перпендикуляр падает на отрезок, то ответ это ответом будет расстояние от исходной точки до точки пересечения отрезка с перпендикуляром, если нет, то иначе {{---}} расстояние от исходной точки до одного из концов отрезка.

Самое очевидное {{---}} это найти точку пересечения перпендикуляра и прямойи, и в зависимости от ее положения , вычислить ответ. На самом делеИли же, этот анализ может быть произведен путем построения треугольника, вершинами которого являются концы отрезка и точка, и сопоставления соотношения длин его сторон.

[[Файл:DistancePtoSDistancePtoS1.png‎|400px|right]]Даны точка <tex>(x_0, y_0)O</tex> и отрезок, заданный точками <tex>(x_1, y_1)A</tex> и <tex>(x_2, y_2)B</tex>.

*<tex>R_1</tex> {{---}} отрезок <tex>(x_0, y_0)</tex><tex>(x_1, y_1)[O; A]</tex>*<tex>R_2</tex> {{---}} отрезок <tex>(x_0, y_0)</tex><tex>(x_2, y_2)[O; B]</tex>*<tex>R_{12}</tex> {{---}} отрезок <tex>(x_1, y_1)</tex><tex>(x_2, y_2)[A; B]</tex>

*Оба предыдущих условия ложны, то <tex>\operatorname{abs} (\frac{| \overrightarrow{R_{12}} \times \overrightarrow{R_1}|/}{|\overrightarrow{R_{12}}|})</tex>, где <tex> \overrightarrow{R_{12}} = (x_2 -x_1, y_2 B - y_1)A</tex> и <tex> \overrightarrow{R_1} = (x_1 - x_0, y_1 A - y_0)O</tex>. Это следует из формул для площади параллелограмма через векторное произведение и через произведения основания на высоту

Как описано выше, в худшем случае алгоритм работает за <tex>O(n^2)</tex>. Можно внести дополнения, которые позволят получить <tex>O(n\log n)</tex> в худшем случае. Ускорение основывается на уменьшении времени поиска наиболее удаленной вершины. Это можно осуществить благодаря идее о том, что наиболее удаленная вершина лежит на выпуклой оболочке полигональной цепи. Описание ускорения взято из статьи Хершберга(Hershberger) ''[http://www.bowdoin.edu/~ltoma/teaching/cs350/spring06/Lecture-Handouts/hershberger92speeding.pdf "Speeding Up the Douglas-Peucker Line-Simplification Algorithm"]'' (1992).

Для построения выпуклой оболочки используется [http://www.ams.sunysb.edu/~jsbm/courses/545/melkman.pdf алгоритм Мелкмана], который работает для двумерной полигональной цепи без самопересечений за <tex>O(n)</tex>, строя все промежуточные выпуклые оболочки, которые пригодятся в дальнейшем.

Построив выпуклую оболочку, После построения выпуклой оболочки используется бинарный поиск для нахождения наиболее удаленной вершины за <tex>O(\log n)</tex>. Затем, если потребуется, действия повторятся рекурсивно, как и в оригинальном алгоритме, но заново строить оболочки не имеет смысла, так как промежуточные уже были построены. Использовав их, можно разбить текущую оболочку на две за <tex>O(\log n)</tex>.

[http://psimpl.sourceforge.net/reumann-witkam.html Алгоритм Реуманна-Виткама ] (Reumann-Witkam) определяет прямую через первые две точки цепи, последняя из последовательных точек начиная со второй, удаленных небольше чем на <tex>\varepsilon</tex>, соединяются прямой, а все промежуточные точки исключаются.

[http://psimpl.sourceforge.net/opheim.html Алгоритм Опхейма ] (Opheim) несколько схож с алгоритмом Реуманна-Виткама. В этом алгоритме мы рассматриваем все вершины в <tex>\varepsilon</tex> радиусе от первой, и строим луч из текущей и последней, попавшей в радиус. Если таких точек нет, то берется следующая за исходной.

[http://psimpl.sourceforge.net/lang.html Алгоритм Ланга ] (Lang) определяет фиксированный размер поисковой области для упрощения. Две точки, что образуют поисковую область, составляют отрезок. Этот отрезок используется для расчета перпендикулярного расстояния до каждой промежуточной точки. Если рассчитанное расстояние больше заданного <tex>\varepsilon</tex>, область поиска будет уменьшен путем исключения ее последней точки.

==Алгоритм , сохраняющий топологию==Алгоритм сохраняющий топологию, как было упомянуто ранее, содержится в статье де Берга A New Approach to Subdivision Simplification, где расскрываются также детали реализации, здесь же мы опишем идею описывается идея алгоритма. Также стоит обратить внимание, что исходная полигональная цепь должна быть без самопересечений.

Алгоритм делится на три четыре основных этапа:*Создание графа <tex>G_1</tex>, в котором помимо исходных ребер, добавлены все возможные сокращенные ребра. Иначе говоря ребра, для который верно, что <tex>i < j</tex> и для любого <tex>t</tex>, такого что <tex>i < t < j</tex>, верно <tex>distance\rho(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>, как в невзвешенном графе, этот путь и будет являться ответом на задачу.

*[http://www.bowdoin.edu/~ltoma/teaching/cs350/spring06/Lecture-Handouts/hershberger92speeding.pdf "Speeding Up the Douglas-Peucker Line-Simplification Algorithm"]*[http://www.ams.sunysb.edu/~jsbm/courses/545/melkman.pdf Алгоритм Мелкмана]

*[http://www.bowdoin.edu/~ltoma/teaching/cs350/spring06/Lecture-Handouts/deberg95new.pdf "A New Approach to Subdivision Simplification"]