El algoritmo de Ramer–Douglas–Peucker , también conocido como algoritmo de Douglas–Peucker y algoritmo iterativo de ajuste de punto final , es un algoritmo que diezma una curva compuesta de segmentos de línea a una curva similar con menos puntos. Fue uno de los primeros algoritmos exitosos desarrollados para la generalización cartográfica . Produce la generalización más precisa, pero también requiere más tiempo. [1]
La curva inicial es un conjunto ordenado de puntos o líneas y la dimensión de la distancia ε > 0 .
El algoritmo divide la línea recursivamente . Inicialmente, se le dan todos los puntos entre el primer y el último punto. Marca automáticamente el primer y el último punto que se deben conservar. A continuación, encuentra el punto que está más alejado del segmento de línea con el primer y el último punto como puntos finales; este punto siempre está más alejado en la curva del segmento de línea que se aproxima entre los puntos finales. Si el punto está más cerca que ε del segmento de línea, entonces cualquier punto que no esté marcado actualmente para conservar se puede descartar sin que la curva simplificada sea peor que ε .
Si el punto más alejado del segmento de línea es mayor que ε de la aproximación, entonces ese punto debe conservarse. El algoritmo se llama recursivamente a sí mismo con el primer punto y el punto más alejado y luego con el punto más alejado y el último punto, lo que incluye el punto más alejado marcado como conservado.
Cuando se completa la recursión, se puede generar una nueva curva de salida que consta solo de todos los puntos que se han marcado como conservados.
La elección de ε suele estar definida por el usuario. Como la mayoría de los métodos de ajuste de líneas, aproximación poligonal o detección de puntos dominantes, se puede hacer no paramétrica utilizando el límite de error debido a la digitalización y cuantificación como condición de terminación. [2]
Suponiendo que la entrada es una matriz basada en uno:
# fuente: https://karthaus.nl/rdp/ function DouglasPeucker ( PointList [], epsilon ) # Encuentra el punto con la distancia máxima dmax = 0 index = 0 end = length ( PointList ) for i = 2 to ( end - 1 ) { d = perpendicularDistance ( PointList [ i ], Line ( PointList [ 1 ], PointList [ end ])) if ( d > dmax ) { index = i dmax = d } } ResultList [] = vacío ; # Si la distancia máxima es mayor que epsilon, simplificar recursivamente if ( dmax > epsilon ) { # Llamada recursiva recResults1 [] = DouglasPeucker ( PointList [ 1. .. index ], epsilon ) recResults2 [] = DouglasPeucker ( PointList [ index ... end ], epsilon ) # Construye la lista de resultados ResultList [] = { recResults1 [ 1. .. length ( recResults1 ) - 1 ], recResults2 [ 1. .. length ( recResults2 )]} } else { ResultList [] = { PointList [ 1 ], PointList [ end ]} } # Devuelve el resultado return ResultList []El algoritmo se utiliza para el procesamiento de gráficos vectoriales y generalización cartográfica . Se reconoce como el que ofrece las mejores representaciones perceptuales de las líneas originales. Pero podría producirse una autointersección si la aproximación aceptada no es lo suficientemente fina, lo que llevó al desarrollo de algoritmos variantes. [3]
El algoritmo se utiliza ampliamente en robótica [4] para realizar la simplificación y eliminación de ruido de los datos de rango adquiridos por un escáner de rango giratorio ; en este campo se lo conoce como algoritmo de división y fusión y se atribuye a Duda y Hart . [5]
El tiempo de ejecución de este algoritmo cuando se ejecuta en una polilínea que consta de n – 1 segmentos y n vértices está dado por la recurrencia T ( n ) = T ( i + 1) + T ( n − i ) + O ( n ) donde i = 1, 2,..., n − 2 es el valor de indexen el pseudocódigo. En el peor de los casos, i = 1 o i = n − 2 en cada invocación recursiva produce un tiempo de ejecución de O ( n 2 ) . En el mejor caso, i = norte/2 o yo = n ± 1/2 en cada invocación recursiva se obtiene un tiempo de ejecución de O ( n log n ) .
Utilizando estructuras de datos de envoltura convexa (totalmente o semi) dinámicas , la simplificación realizada por el algoritmo se puede lograr en tiempo O ( n log n ) . [6]
Dadas condiciones específicas relacionadas con la métrica de delimitación, es posible disminuir la complejidad computacional a un rango entre O ( n ) y O ( 2n ) mediante la aplicación de un método iterativo. [7]
El tiempo de ejecución para la generalización del modelo de elevación digital utilizando la variante tridimensional del algoritmo es O ( n 3 ) , pero se han desarrollado técnicas para reducir el tiempo de ejecución para datos más grandes en la práctica. [8]
Los algoritmos alternativos para la simplificación de líneas incluyen: