Algoritmo de Ramer–Douglas–Peucker

El algoritmo de Ramer–Douglas–Peucker (RDP) es un algoritmo para reducir el número de puntos utilizados en la aproximación de una curva. La forma inicial del algoritmo fue independientemente propuesta en 1972 por Urs Ramer, en 1973 por David Douglas and Thomas Peucker^[1] y algunos más en la siguiente década.^[2] Este algoritmo también es conocido con el nombre de algoritmo de Douglas-Peucker.

Idea

El objetivo del algoritmo es, dada una curva compuesta por segmentos, encontrar una curva similar aproximada con menos puntos. El algoritmo define una diferencia basada en la máxima distancia entre la curva original y la curva simplificada. La curva simplificada consiste en una reducción de los puntos que definían la curva original.

Algoritmo

La curva inicial es una lista ordenada de puntos o segmentos y la dimensión distancia ε > 0.

El algoritmo divide el segmento recursivamente. Inicialmente se dan todos los puntos entre los extremos de la curva. Automáticamente los extremos son marcados como solución final. Entonces, busca el punto más alejado del segmento definido por el punto inicial y final de la curva (obviamente este punto será el más alejado de la curva aproximada por los dos puntos iniciales). Si el punto está más cerca del segmento que la distancia ε entonces ningún punto será guardado ya que la nueva curva simplificada sería peor que ε.

Si el punto está más alejado que ε entonces ese punto debe permanecer en la simplificación. El algoritmo se llama recursivamente a sí mismo, primero con el primer y el peor punto y después con el último y el peor punto.

Cuando se completa la recursión la nueva curva puede ser generada a partir de solo los puntos que han permanecido tras haber aplicado el algoritmo.

RDP no paramétrico

La elección de ε es normalmente elegida como 1-2...n pixels. Como la mayoría de métodos de ajuste de línea, aproximación poligonal o detección del punto dominante pueden ser no paramétricos basándose en el uso del error vinculado debido a la digitalización o la cuantificación como condición final.

Pseudocódigo

function DouglasPeucker(PointList[], epsilon)
    // Busca el punto con la distancia 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 distancia es mayor que epsilon, simplificar recursivamente
    if ( dmax > epsilon ) {
        // Llamada recursiva
        recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
        recResults2[] = DouglasPeucker(PointList[index...end], epsilon)
 
        // Construcción de la lista resultado
        ResultList[] = {recResults1[1...end-1] recResults2[1...end]}
    } else {
        ResultList[] = {PointList[1], PointList[end]}
    }
    // Devolver el resultado
    return ResultList[]
end

Aplicaciones

El algoritmo es utilizado para el procesamiento de imágenes vectoriales y generalización cartográfica.

El algoritmo es ampliamente utilizado en robótica^[3] para realizar simplificaciones y eliminar ruido al medir distancias con telémetros giratorios.

Complejidad

La complejidad esperada por este algoritmo puede describirse con la recurrencia linear $T(n){=}2T({n \over 2})+O(n)$ , la cual tiene solución conocida a través del Teorema maestro de $T(n)\in \Theta (nlog(n))$ . De todos modos, la complejidad en el peor caso es $\Theta (n^{2})$ .

Otros algoritmos de simplificación de líneas

Alternative algorithms for line simplification include:

Algoritmo de Visvalingam–Whyatt
Algoritmo de Reumann–Witkam
Algoritmo de simplificación Opheim
Algoritmo de simplificación Lang

Referencias

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 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 (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 (http://www2.dcs.hull.ac.uk/CISRG/publications/DPs/DP10/DP10.html)

Notas

↑ Ver referencia para más detalles
↑ Heckbert, Paul S.; Garland, Michael (1997). Survey of polygonal simplification algorithms. p. 4.
↑ Nguyen, Viet; Gächter, Stefan; Martinelli, Agostino; Tomatis, Nicola; Siegwart, Roland (2007). «A comparison of line extraction algorithms using 2D range data for indoor mobile robotics». Autonomous Robots 23 (2): 97. doi:10.1007/s10514-007-9034-y.

Enlaces externos

[1] Ver referencia para más detalles

[2] Heckbert, Paul S.; Garland, Michael (1997). Survey of polygonal simplification algorithms. p. 4.

[3] Nguyen, Viet; Gächter, Stefan; Martinelli, Agostino; Tomatis, Nicola; Siegwart, Roland (2007). «A comparison of line extraction algorithms using 2D range data for indoor mobile robotics». Autonomous Robots 23 (2): 97. doi:10.1007/s10514-007-9034-y.

[1]

[2]

[3]