Алгоритм Рамера – Дугласа – Пекера

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

• 1 Идея
• 2 Алгоритм
  • 2.1 Непараметрический алгоритм Рамера – Дугласа – Пойкера
  • 2.2 Псевдокод
• 3 Приложение
• 4 Сложность
• 5 См. Также
• 6 Дополнительная литература
• 7 Ссылки
• 8 Внешние ссылки

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

Упрощение кусочно-линейной кривой с помощью алгоритма Дугласа – Пойкера.

Начальная кривая - это упорядоченный набор точек или линий и размерность расстояния ε>0.

Алгоритм рекурсивно делит строку. Первоначально ему даются все баллы между первой и последней точкой. Он автоматически отмечает первую и последнюю точку, которую нужно сохранить. Затем он находит точку, которая наиболее удалена от отрезка линии, причем первая и последняя точки являются конечными точками; эта точка, очевидно, самая дальняя на кривой от аппроксимирующего отрезка прямой между конечными точками. Если точка находится ближе, чем ε к отрезку линии, то любые точки, которые в настоящее время не отмечены для сохранения, могут быть отброшены без того, чтобы упрощенная кривая была хуже, чем ε.

Если точка, наиболее удаленная от отрезка линии, больше ε от аппроксимации, то эту точку необходимо сохранить. Алгоритм рекурсивно вызывает себя с первой точкой и самой дальней точкой, а затем с самой дальней точкой и последней точкой, которая включает самую дальнюю точку, отмеченную как сохраняемую.

Когда рекурсия завершена, может быть сгенерирована новая выходная кривая, состоящая из всех и только тех точек, которые были отмечены как сохраненные.

Эффект изменения эпсилон в параметрической реализации RDP

Непараметрический Рамер – Дуглас – Пойкер

Выбор ε обычно определяется пользователем. Как и большинство методов аппроксимации линий / полигональной аппроксимации / обнаружения доминирующих точек, его можно сделать непараметрическим, используя границу ошибки из-за оцифровки / квантования в качестве условия завершения.

Псевдокод

(Предполагается ввод - массив с единицей)

function DouglasPeucker (PointList, epsilon) // Найти точку с максимальным расстоянием dmax = 0 index = 0 end = length (PointList) для от i = 2 до (конец - 1) {d = perpendicularDistance (PointList [i], Line (PointList [1], PointList [end])) if (d>dmax) {index = i dmax = d}} ResultList = пусто; // Если максимальное расстояние больше, чем эпсилон, рекурсивно упростить if (dmax>epsilon) {// Рекурсивный вызов recResults1 = DouglasPeucker (PointList [1... index], epsilon) recResults2 = DouglasPeucker (PointList [ index... end], epsilon) // Создаем список результатов ResultList = {recResults1 [1... length (recResults1) - 1], recResults2 [1... length (recResults2)]}} else {ResultList = {PointList [1], PointList [end]}} // Вернуть результат return ResultList end

Ссылка: https://karthaus.nl/ rdp /

Алгоритм используется для обработки векторной графики и картографического обобщения. Он не всегда сохраняет свойство несамопересечения кривых, что привело к разработке альтернативных алгоритмов.

Алгоритм широко используется в робототехнике для выполнения упрощения и уменьшения шума данных о диапазоне, полученных вращением сканер диапазона ; в этом поле он известен как алгоритм разделения и слияния и относится к Дуда и Харт.

Время выполнения этого алгоритма при запуске на полилиния, состоящая из $n\; -\; 1\; \{\backslash \; displaystyle\; n-1\}$сегментов и $n\; \{\backslash \; displaystyle\; n\}$вершин, задается повторением $T\; (\; п)\; знак\; равно\; Т\; (я\; +\; 1)\; +\; Т\; (N\; -\; я)\; +\; О\; (п)\; \{\backslash \; Displaystyle\; Т\; (п)\; =\; Т\; (я\; +\; 1)\; +\; Т\; (NI)\; +\; О\; (п)\}$где $i\; \in \; \{1,\dots ,\; n\; -\; 2\}\; \{\backslash \; displaystyle\; i\; \backslash \; in\; \backslash \; \{1,\; \backslash \; ldots,\; n-2\; \backslash \}\}$- значение индекса в псевдокоде. В худшем случае $i\; =\; 1\; \{\backslash \; displaystyle\; i\; =\; 1\}$или $i\; =\; n\; -\; 2\; \{\backslash \; displaystyle\; i\; =\; n-2\}$в каждом рекурсивный вызов, и этот алгоритм имеет время выполнения $\Theta \; (n\; 2)\; \{\backslash \; displaystyle\; \backslash \; Theta\; (n\; ^\; \{2\})\}$. В лучшем случае $i\; =\; \lfloor \; n\; /\; 2\; \rfloor \; \{\backslash \; displaystyle\; i\; =\; \backslash \; lfloor\; n\; /\; 2\; \backslash \; rfloor\}$или $i\; =\; \lceil \; n\; /\; 2\; \rceil \; \{\backslash \; displaystyle\; i\; =\; \backslash \; lceil\; n\; /\; 2\; \backslash \; rceil\}$при каждом рекурсивном вызове, и в этом случае время выполнения имеет хорошо известное решение (с помощью основной теоремы для повторений «разделяй и властвуй» ) $O\; (n\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (n\; \backslash \; log\; n)\}$.

Используя (полностью или частично) структуры данных с динамической выпуклой оболочкой, упрощение, выполняемое алгоритмом, может быть выполнено за $O\; (n\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (n\; \backslash \; log\; n)\}$времени.

• Подгонка кривой

Альтернативные алгоритмы для упрощения линий включают:

• Урс Рамер, «Итерационная процедура для многоугольной аппроксимации плоских кривых», Компьютерная графика и Обработка изображений, 1 (3), 244–256 (1972) doi : 10.1016 / S0146-664X (72) 80017-0
• Дэвид Дуглас и Томас Пекер, «Алгоритмы сокращения количества точек, необходимых для представления оцифрованной линии или ее карикатуры », Канадский картограф 10 (2), 112–122 (1973) doi : 10.3138 / FM57-6770-U75U-7727
• Джон Хершбергер и Джек Сноиинк, «Ускорение алгоритма упрощения линии Дугласа – Пекера», Proc 5th Symp on Data Handling, 134–143 (1992). Технический отчет UBC TR-92-07 доступен по адресу http://www.cs.ubc.ca/cgi-bin/tr/1992/TR-92-07
• R.O. Дуда и П. Харт, «Классификация паттернов и анализ сцены», (1973), Вили, Нью-Йорк (https://web.archive.org/web/20110715184521/http://rii.ricoh.com/~stork/DHS.html )
• Висвалингам, М.; Вятт, Дж. Д. (1992). Обобщение линий путем многократного исключения наименьшего участка (Технический отчет). Документ для обсуждения. Исследовательская группа по картографическим информационным системам (CISRG), Университет of Hull. 10.

• Поддержка Boost.Geometry Алгоритм упрощения Дугласа – Пекера
• Реализация алгоритмов Рамера – Дугласа – Пекера и многих других алгоритмов упрощения с лицензией с открытым исходным кодом на C ++
• XSLT-реализация алгоритма для использования с данными KML.
• Вы можете увидеть алгоритм, примененный к журналу GPS во время поездки на велосипеде, внизу этой страницы
• Интерактивная визуализация алгоритма
• Реализация в F #
• Реализация гема Ruby
• JTS, Java Topology Suite, содержит реализацию Java многих алгоритмов, включая алгоритм Дугласа-Пекера ithm