Algoritme de Ramer–Douglas–Peucker

L'algoritme de Ramer–Douglas–Peucker (RDP) és un algoritme per a reduir el número de punts utilisats en l'aproximació d'una curva. La forma inicial de l'algoritme va ser independentment proposta en 1972 per Urs Ramer, en 1973 per David Douglas and Thomas Peucker i alguns més en la següent década. Este algoritme també és conegut en el nom de algoritme de Douglas-Peucker.

Idea

L'objectiu de l'algoritme és, donada una curva composta per segments, trobar una curva similar aproximada en menys punts. L'algoritme definix una diferència basada en la màxima distància entre la curva original i la curva simplificada. La curva simplificada consistix en una reducció dels punts que definien la curva original.

Algoritme

Simplificant una curva definida a trossos en l'algoritme de Douglas-Peucker.

La curva inicial és una llista ordenada de punts o segments i un llindar d'error ε > 0.

L'algoritme construïx una aproximació de la curva inicial per mig d'un procés recursivo. Es pren com a solució inicial el segment que unix els dos punts extrems de la curva. Llavors, es busca el punt més alluntat de dit segment (pijor punt).

• Si el pijor punt està més prop del segment que el llindar de distància ε, llavors es termina el procés. És segur que el restant de punts de la curva estan a menor distancia que el llindar ε, i per lo tant tots els punts de la curva (llevat els extrems) poden ser descartats.

• Si el pijor punt està més alluntat que ε, llavors eixe punt deu permanéixer en la simplificació. L'algoritme fa dos cridades recursivas a sí mateixa per a calcular l'aproximació de dos curves de menor llongitut. Una en els punts entre el primer i el pijor punt i una atra en els punts entre el pijor punt i el punt final de la curva.

Quan es completa la recursión la nova curva pot ser generada a partir dels punts que han permaneixcut despuix d'haver aplicat l'algoritme.

Pseudocódigo

function DouglasPeucker(PointList[], epsilon)
    // Busca el punt en la distància màxima
    dmax = 0
    index = 0
    end = length(PointList)
    for i = 2 to ( end - 1) {
        d = shortestDistanceToSegment(PointList[i], Line(PointList[1], PointList[end])) 
        if ( d > dmax ) {
            index = i
            dmax = d
        }
    }
    // Si la distància és major que epsilon, simplificar recursivamente
    if ( dmax > epsilon ) {
        // Cridada recursiva
        recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
        recResults2[] = DouglasPeucker(PointList[index...end], epsilon)
 
        // Construcció de la llista resultat
        ResultList[] = {recResults1[1...end-1] recResults2[1...end]}
    } else {
        ResultList[] = {PointList[1], PointList[end]}
    }
    // Tornar el resultat
    return ResultList[]
end

RDP no paramètric

L'elecció de ε és normalment una distància elegida per l'usuari. Com la majoria de métodos d'ajust de llínea, aproximació poligonal o detecció del punt dominant, és possible realisar una versió no paramètrica de l'algoritme, calculant un valor per a ε basant-se en l'us de l'error vinculat per la digitalisació o la quantificació. El còdic MATLAB de la versió no paramètrica de l'algoritme està disponible en llínea.

Referències

• 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 https://web.archive.org/web/20160414023022/http://www.cs.ubc.ca/cgi-bin/tr/1992/TR-92-07

• R.O. Dubte 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 Séries 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)