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

Алгоритм Рамера-Дугласа-Пекера — алгоритм, що дозволяє зменшити число точок кривої, апроксимованої більшою серією точок. Алгоритм було незалежно відкрито Урсом Рамером в 1972 та Давидом Дугласом і Томасом Пекером в 1973 та декількома іншими дослідниками протягом наступного десятиліття. Також алгоритм відомий під назвами: алгоритм Дугласа-Пекера, алгоритм ітеративної найближчої точки та алгоритм розбиття і злиття.

Ідея

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

Алгоритм

Згладжування кусково-лінійної кривої алгоритмом Дугласа-Пекера.

Згладжування кусково-лінійної кривої алгоритмом Дугласа-Пекера залежно вiд параметра ε.

Початкова крива являє собою упорядкований набір точок або ліній, і задану відстань ε > 0. Початкова крива показана на малюнку 0, спрощена — на малюнку 4.

Алгоритм рекурсивно ділить лінію. Входом алгоритму служать координати всіх точок між першою і останньою. Перша і остання точка зберігаються незмінними. Після чого алгоритм знаходить точку, найбільш віддалену від відрізка, що з'єднує першу і останню. Якщо точка знаходиться на відстані, меншій ε, то всі точки, які ще не були відзначені до збереження, можуть бути викинуті з набору і отримана пряма згладжує криву з точністю не нижче ε

Якщо ж відстань більше ε, то алгоритм рекурсивно викликає себе на наборі від початкової до даної і від даної до кінцевої точках (що означає, що дана точка буде відзначена до збереження). По закінченню всіх рекурсивних викликів вихідна ламана будується тільки з тих точок, що були відзначені до збереження.

Псевдокод (рекурсивна реалізація)

function DouglasPeucker(PointList[], epsilon) // Знаходимо точку з максимальною відстанню від прямої між першою й останньою точками набору dmax = 0 index = 0 for i = 2 to (length(PointList) - 1) d = PerpendicularDistance(PointList[i], Line(PointList[1], PointList[end])) if d > dmax index = i dmax = d end end // Якщо максимальна дистанція більша, ніж epsilon, то рекурсивно викликаємо функцію на ділянках if dmax >= epsilon //Recursive call recResults1[] = DouglasPeucker(PointList[1...index], epsilon) recResults2[] = DouglasPeucker(PointList[index...end], epsilon) // Будуємо підсумковий набір точок ResultList[] = {recResults1[1...end-1] recResults2[1...end]} else ResultList[] = {PointList[1], PointList[end]} end // Повертаємо результат return ResultList[] end 

Псевдокод (ітеративна реалізація)

function DouglasPeucker(PointList[], epsilon) { // У стек заносимо перший і останній індекси stack.push({0, length(PointList) - 1}) // У масиві за заданим індексом зберігаємо точку (true) або ні (false) keep_point[0...length(PointList) - 1] = true while(!stack.empty()) { startIndex = stack.top().first endIndex = stack.top().second stack.pop() dMax = 0 index = startIndex for(i = startIndex + 1 to endIndex - 1) { if(keep_point[i]) { d = PerpendicularDistance(PointList[i], Line(PointList[startIndex], PointList[endIndex])) if(d > dMax) { index = i dMax = d } } } if(dMax >= epsilon) { stack.push({startIndex, index}) stack.push({index, endIndex}) } else { for(j = startIndex + 1 to endIndex - 1) { keep_point[j] = false } } } for(i = 0 to (length(PointList) - 1)) { if(keep_point[i]) { ResultList.Add(PointList[i]) } } return ResultList[] } 

Застосування

Алгоритм застосовується для обробки векторної графіки та при картографічній генералізації.

Крім того, застосовується у робототехніці для обробки результатів роботи кругового лазерного далекоміру і тому також називається алгоритмом розбиття і злиття.

Складність

Очікувана складність алгоритму може бути оцінена виразом ${\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$, яка спрощується (як наслідок основної теореми про рекурентні співвідношення) в ${\displaystyle T(n)\in \Theta (n\log n)}$. Проте в гіршому випадку складність алгоритму ${\displaystyle O\left(n^{2}\right)}$.

Примітки

1. Heckbert, Paul S.; Garland, Michael (1997). Survey of polygonal simplification algorithms (PDF): 4. Архів оригіналу (PDF) за 22 квітня 2016. Процитовано 23 червня 2016. 
2. Nguyen and Martinelli and Siegwart (2005). A Comparison of Line Extraction Algorithms using 2D Laser Rangefinder for Indoor Mobile Robotics (PDF). Архів оригіналу (PDF) за 17 вересня 2010. Процитовано 15 червня 2016.  [Архівовано 2010-09-17 у Wayback Machine.]

Література

• Urs Ramer, "An iterative procedure for the polygonal approximation of plane curves", Computer Graphics and Image Processing, 1(3), 244–256 (1972) DOI:10.1016/S0146-664X(72)80017-0
• David Douglas & Thomas Peucker, "Algorithms for the reduction of the number of points required to represent a digitized line or its caricature", The Canadian Cartographer 10(2), 112–122 (1973) DOI:10.3138/FM57-6770-U75U-7727
• John Hershberger & Jack Snoeyink, "Speeding Up the Douglas–Peucker Line-Simplification Algorithm", Proc 5th Symp on Data Handling, 134–143 (1992). UBC Tech Report TR-92-07 available at
• R.O. Duda and P.E. Hart, "Pattern classification and scene analysis", (1973), Wiley, New York ()
• Visvalingam, M., and Whyatt, J.D. "Line Generalisation by Repeated Elimination of the Smallest Area". (1992) CISRG Discussion Paper Series No 10, University of Hull, 16 pp ()