Algoritmo Ramer-Douglas-Peucker

L'algoritmo Ramer–Douglas–Peucker (RDP) è un algoritmo per la riduzione del numero di punti in una linea spezzata. La forma iniziale dell'algoritmo fu suggerita nel 1972 da Urs Ramer e nel 1973 da David Douglas e Thomas Peucker e diverse altre nei successivi decenni. Questo algoritmo è anche conosciuto sotto il nome di algoritmo Douglas–Peucker, iterative end-point fit e split-and-merge.

Idea

Assegnata un'approssimazione lineare a tratti di una curva, lo scopo dell'algoritmo è trovare un'approssimazione di dimensione ridotta, ovvero con meno segmenti, che non sia dissimile dall'approssimazione originale. L'algoritmo definisce la "dissimilarità" come massima distanza tra la curva originale e la curva semplificata. La curva semplificata consiste di un sottoinsieme dei punti della curva originale.

Algoritmo

Semplificazione di una linea spezzata con l'algoritmo Douglas–Peucker. 0. Linea originale; 1. la linea a è una prima approssimazione dell'originale, ma la distanza b tra a e il punto c supera la massima distanza. 2. L'approssimazione successiva include il punto c. 2. e 3. Si continua con gli altri punti fino alla linea semplificata (4.)

Uno pseudocodice per questo algoritmo è riportato di seguito; si assume che l'input sia un array che parte dall'indice 1.

function DouglasPeucker(PointList[], epsilon)
    // troviamo il punto con la massima distanza
    dmax = 0
    index = 0
    end = length(PointList)
   //se ha meno di 3 punti non vi è nulla da semplificare e torniamo l'array (di 1 o 2 punti)
    if (end < 3 ) return PointList[]
    for i = 2 to ( end - 1) {
        d = shortestDistanceToSegment(PointList[i], Line(PointList[1], PointList[end])) 
        if ( d > dmax ) {
            index = i
            dmax = d
        }
    }
    // se la massima distanza è maggiore di epsilon, semplifichiamo ricorsivamente
    if ( dmax > epsilon ) {
        // Chiamate ricorsiva
        recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
        recResults2[] = DouglasPeucker(PointList[index...end], epsilon)
 
        // Concateniamo le liste risultanti
        ResultList[] = {recResults1[1...end-1] recResults2[1...end]}
    } else {
       //prendiamo i due punti estremi
        ResultList[] = {PointList[1], PointList[end]}
    }
    // Ritorna il risultato
    return ResultList[]
end