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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Ідея[ред. | ред. код]

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

Алгоритм[ред. | ред. код]

Згладжування кусково-лінійної кривої алгоритмом Дугласа-Пекера.
Згладжування кусково-лінійної кривої алгоритмом Дугласа-Пекера залежно в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[]
}

Застосування[ред. | ред. код]

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

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

Складність[ред. | ред. код]

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

Примітки[ред. | ред. код]

  1. Heckbert, Paul S.; Garland, Michael (1997). Survey of polygonal simplification algorithms. с. 4. 
  2. Nguyen and Martinelli and Siegwart (2005). A Comparison of Line Extraction Algorithms using 2D Laser Rangefinder for Indoor Mobile Robotics. 

Література[ред. | ред. код]