Algoritmo de Ramer–Douglas–Peucker
# 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 y algunos más en la siguiente década. 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 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.

### RDP no paramétrico

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. El código MATLAB de la versión no paramétrica del algoritmo está disponible en línea.

## 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 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

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
