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

Алгоритм Рамера -Дугласа-Пойкера , также известный как алгоритм Дугласа-Пейкера и алгоритм итерационной подгонки конечной точки , представляет собой алгоритм, который преобразует кривую, состоящую из сегментов прямой, в аналогичную кривую с меньшим количеством точек. Это был один из первых успешных алгоритмов, разработанных для картографического обобщения . Он дает наиболее точное обобщение, но требует больше времени. ^{[ 1 ]}

Алгоритм

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

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

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

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

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

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

Псевдокод

Предполагая, что входные данные представляют собой массив, основанный на единице:

 # source: https://karthaus.nl/rdp/
function DouglasPeucker(PointList[], epsilon)
    # Find the point with the maximum distance
    dmax = 0
    index = 0
    end = length(PointList)
    for i = 2 to (end - 1) {
        d = perpendicularDistance(PointList[i], Line(PointList[1], PointList[end])) 
        if (d > dmax) {
            index = i
            dmax = d
        }
    }

    ResultList[] = empty;

    # If max distance is greater than epsilon, recursively simplify
    if (dmax > epsilon) {
        # Recursive call
        recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
        recResults2[] = DouglasPeucker(PointList[index...end], epsilon)

        # Build the result list
        ResultList[] = {recResults1[1...length(recResults1) - 1], recResults2[1...length(recResults2)]}
    } else {
        ResultList[] = {PointList[1], PointList[end]}
    }
    # Return the result
    return ResultList[]

Приложение

Алгоритм используется для обработки векторной графики и картографической генерализации . Он признан тем, который обеспечивает лучшее перцепционное представление оригинальных строк. Но самопересечение может произойти, если принятое приближение недостаточно точное, что привело к разработке вариантов алгоритмов. ^{[ 3 ]}

Алгоритм широко используется в робототехнике. ^{[ 4 ]} выполнять упрощение и шумоподавление данных о дальности, полученных вращающимся сканером дальности ; в этой области он известен как алгоритм разделения и слияния и приписывается Дуде и Харту . ^{[ 5 ]}

Сложность

Время работы этого алгоритма при запуске на ломаной линии, состоящей из $n - 1$ сегментов и $n$ вершин, определяется рекуррентностью $T (n) = T (i + 1) + T (n - i) + O (n),$ где $i = 1, 2,..., n - 2 —$ значение index в псевдокоде. В худшем случае $i = 1$ или $i = n - 2$ при каждом рекурсивном вызове дает время работы $O (n 2)$ . В лучшем случае $я = .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ n / 2 ⁠$ или $я = ⁠ n \pm 1/2 ⁠ ($ вызове дает время работы $O) n log n .$ при каждом рекурсивном

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

Учитывая конкретные условия, связанные с ограничивающей метрикой, можно уменьшить сложность вычислений до диапазона от $O (n)$ до $O (2n)$ за счет применения итерационного метода. ^{[ 7 ]}

Время выполнения генерализации цифровой модели рельефа с использованием трехмерного варианта алгоритма составляет $O (n 3)$ , но на практике были разработаны методы, позволяющие сократить время обработки больших данных. ^{[ 8 ]}

Подобные алгоритмы

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

Висвалингам – Уайатт
Ройманн-Виткам
Упрощение Опхайма
Упрощение языка
Чжао-Заальфельд

См. также

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

Дальнейшее чтение

Рамер, Урс (1972). «Итерационная процедура полигональной аппроксимации плоских кривых». Компьютерная графика и обработка изображений . 1 (3): 244–256. дои : 10.1016/S0146-664X(72)80017-0 .
Дуглас, Дэвид; Пойкер, Томас (1973). «Алгоритмы уменьшения количества точек, необходимых для изображения оцифрованной линии или ее карикатуры». Cartographica: Международный журнал географической информации и геовизуализации . 10 (2): 112–122. дои : 10.3138/FM57-6770-U75U-7727 .
Хершбергер, Джон; Снойинк, Джек (1992). Ускорение алгоритма линейного упрощения Дугласа-Пойкера . Материалы 5-го симпозиума по обработке данных. стр. 134–143. Технический отчет UBC TR-92-07 доступен на сайте « Ускорение алгоритма упрощения линии Дугласа-Пейкера» | Информатика в UBC
Дуда, Р.О.; Харт, ЧП (1973). Классификация образов и анализ сцен . Нью-Йорк: Уайли. Бибкод : 1973pcsa.book.....D . Архивировано из оригинала 15 июля 2011 г.
Висвалингам, М.; Уятт, доктор медицинских наук (1992). Генерализация линий путем многократного исключения наименьшего участка (Технический отчет). Дискуссионный документ. Группа исследования картографических информационных систем (CISRG), Университет Халла. 10.

Ссылки

^ Ши, Вэньчжун; Чунг, ЧуйКван (2006). «Оценка производительности алгоритмов линейного упрощения для векторной генерализации». Картографический журнал . 43 (1): 27–44. дои : 10.1179/000870406x93490 .
^ Прасад, Дилип К.; Люнг, Мэйлор К.Х.; Кек, Чай; Чо, Сиу-Юнг (2012). «Новая основа для того, чтобы сделать методы обнаружения доминирующих точек непараметрическими». Вычисление изображений и зрительных образов . 30 (11): 843–859. дои : 10.1016/j.imavis.2012.06.010 .
^ Ву, Шин-Тин; Маркес, Мерседес (2003). «Алгоритм Дугласа-Пейкера без самопересечения». 16-й Бразильский симпозиум по компьютерной графике и обработке изображений (SIBGRAPI, 2003) . Сан-Карлос, Бразилия: IEEE. стр. 60–66. CiteSeerX 10.1.1.73.5773 . дои : 10.1109/СИБГРА.2003.1240992 . ISBN 978-0-7695-2032-2 . S2CID 10163908 .
^ Нгуен, Вьетнам; Гехтер, Стефан; Мартинелли, Агостино; Томатис, Никола; Зигварт, Роланд (2007). «Сравнение алгоритмов выделения линий с использованием данных 2D-диапазона для внутренней мобильной робототехники» (PDF) . Автономные роботы . 23 (2): 97–111. дои : 10.1007/s10514-007-9034-y . hdl : 20.500.11850/9089 . S2CID 35663952 .
^ Дуда, Ричард О .; Харт, Питер Э. (1973). Классификация закономерностей и анализ сцены . Нью-Йорк: Уайли. ISBN 0-471-22361-1 .
^ Хершбергер, Джон; Снойинк, Джек (1992). Ускорение алгоритма линейного упрощения Дугласа-Пейкера (PDF) (технический отчет).
^ "ramer_douglas_peucker_funneling.py" . Суть .
^ Фей, Лифан; Он, Джин (2009). «Трехмерный алгоритм Дугласа – Пейкера и его применение для автоматического обобщения ЦМР». Международный журнал географической информатики . 23 (6): 703–718. дои : 10.1080/13658810701703001 .

Внешние ссылки

[1] Ши, Вэньчжун; Чунг, ЧуйКван (2006). «Оценка производительности алгоритмов линейного упрощения для векторной генерализации». Картографический журнал . 43 (1): 27–44. дои : 10.1179/000870406x93490 .

[2] Прасад, Дилип К.; Люнг, Мэйлор К.Х.; Кек, Чай; Чо, Сиу-Юнг (2012). «Новая основа для того, чтобы сделать методы обнаружения доминирующих точек непараметрическими». Вычисление изображений и зрительных образов . 30 (11): 843–859. дои : 10.1016/j.imavis.2012.06.010 .

[3] Ву, Шин-Тин; Маркес, Мерседес (2003). «Алгоритм Дугласа-Пейкера без самопересечения». 16-й Бразильский симпозиум по компьютерной графике и обработке изображений (SIBGRAPI, 2003) . Сан-Карлос, Бразилия: IEEE. стр. 60–66. CiteSeerX 10.1.1.73.5773 . дои : 10.1109/СИБГРА.2003.1240992 . ISBN 978-0-7695-2032-2 . S2CID 10163908 .

[4] Нгуен, Вьетнам; Гехтер, Стефан; Мартинелли, Агостино; Томатис, Никола; Зигварт, Роланд (2007). «Сравнение алгоритмов выделения линий с использованием данных 2D-диапазона для внутренней мобильной робототехники» (PDF) . Автономные роботы . 23 (2): 97–111. дои : 10.1007/s10514-007-9034-y . hdl : 20.500.11850/9089 . S2CID 35663952 .

[5] Дуда, Ричард О .; Харт, Питер Э. (1973). Классификация закономерностей и анализ сцены . Нью-Йорк: Уайли. ISBN 0-471-22361-1 .

[6] Хершбергер, Джон; Снойинк, Джек (1992). Ускорение алгоритма линейного упрощения Дугласа-Пейкера (PDF) (технический отчет).

[7] "ramer_douglas_peucker_funneling.py" . Суть .

[8] Фей, Лифан; Он, Джин (2009). «Трехмерный алгоритм Дугласа – Пейкера и его применение для автоматического обобщения ЦМР». Международный журнал географической информатики . 23 (6): 703–718. дои : 10.1080/13658810701703001 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]