Algoritmo de Ramer–Douglas–Peucker

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.

La curva inicial es una lista ordenada de puntos o segmentos y un umbral de error ε > 0.

El algoritmo construye una aproximación de la curva inicial mediante un proceso recursivo. Se toma como solución inicial el segmento que une los dos puntos extremos de la curva. Entonces, se busca el punto más alejado de dicho segmento (peor punto).

• Si el peor punto está más cerca del segmento que el umbral de distancia ε, entonces se termina el proceso. Es seguro que el resto de puntos de la curva están a menor distancia que el umbral ε, y por lo tanto todos los puntos de la curva (salvo los extremos) pueden ser descartados.

• Si el peor punto está más alejado que ε, entonces ese punto debe permanecer en la simplificación. El algoritmo hace dos llamadas recursivas a sí mismo para calcular la aproximación de dos curvas de menor longitud. Una con los puntos entre el primer y el peor punto y otra con los puntos entre el peor punto y el punto final de la curva.

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

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

La elección de ε es normalmente una distancia elegida por el usuario. Como la mayoría de métodos de ajuste de línea, aproximación poligonal o detección del punto dominante, es posible realizar una versión no paramétrica del algoritmo, calculando un valor para ε basándose en el uso del error vinculado debido a la digitalización o la cuantificación.^[3] El código MATLAB de la versión no paramétrica del algoritmo^[4] está disponible en línea.^[5]

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

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

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

Entre otros algoritmos para la simplificación de líneas se encuentran:

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