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

Ідея

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

Алгоритм

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

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

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

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

function DouglasPeucker(PointList[], epsilon) // Знаходимо точку з максимальною відстанню від прямої між першою й останньою точками набору dmax = 0 index = 0 for i = 2 to (length(PointList) - 1) d = PerpendicularDistance(PointList[i], Line(PointList, 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, 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[]

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

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

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

Складність

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

Примітки

Література Urs Ramer, "An iterative procedure for the polygonal approximation of plane curves", Computer Graphics and Image Processing, 1(3), 244–256 (1972) 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) 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 https://web.archive.org/web/20160414023022/http://www.cs.ubc.ca/cgi-bin/tr/1992/TR-92-07 R.O. Duda and P.E. Hart, "Pattern classification and scene analysis", (1973), Wiley, New York (https://web.archive.org/web/20110715184521/http://rii.ricoh.com/~stork/DHS.html) 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 (https://web.archive.org/web/20140210052537/http://www2.dcs.hull.ac.uk/CISRG/publications/DPs/DP10/DP10.html)