Hispanopedia Wiki
Articulo de referencia

Algoritmo de Ramer-Douglas-Peucker

El algoritmo Ramer-Douglas-Peucker , también conocido como algoritmo Douglas-Peucker o algoritmo iterativo de ajuste de puntos finales , es un algoritmo que reduce una curva com...

Hispanopedia WikiContenido en espanolLectura gratuita

El algoritmo Ramer-Douglas-Peucker , también conocido como algoritmo Douglas-Peucker o algoritmo iterativo de ajuste de puntos finales , es un algoritmo que reduce una curva compuesta por 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 ]

Algoritmo

Simplificación de una curva lineal por tramos con el algoritmo de Douglas-Peucker.

La curva inicial es un conjunto ordenado de puntos o líneas y la dimensión de distancia ε > 0 .

El algoritmo divide la línea recursivamente . Inicialmente, recibe todos los puntos entre el primero y el último. Marca automáticamente el primero y el último punto que se conservarán. Luego, encuentra el punto más alejado del segmento de línea cuyos extremos son el primero y el último punto; este punto siempre es el más alejado en la curva del segmento de línea de aproximación entre los extremos. Si el punto está más cerca que ε del segmento de línea, entonces cualquier punto que no esté marcado para conservarse puede descartarse sin que la curva simplificada sea peor que ε .

Si el punto más alejado del segmento de línea se encuentra a una distancia mayor que ε de la aproximación, dicho 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, que incluye el punto más alejado marcado como conservado.

Una vez completada la recursión, se puede generar una nueva curva de salida que consta únicamente de los puntos que se han marcado como conservados.

El efecto de variar épsilon en una implementación paramétrica de RDP

Ramer-Douglas-Peucker no paramétrico

La elección de ε suele ser definida por el usuario. Al igual que la mayoría de los métodos de ajuste de líneas, aproximación poligonal o detección de puntos dominantes, puede hacerse no paramétrico utilizando el límite de error debido a la digitalización y la cuantización como condición de terminación. [ 2 ]

Pseudocódigo

Suponiendo que la entrada es un array basado en uno:

# fuente: https://karthaus.nl/rdp/ función DouglasPeucker ( PointList [], epsilon ) # Encuentra el punto con la distancia máxima dmax = 0 índice = 0 fin = longitud ( PointList ) para i = 2 a ( fin - 1 ) { d = perpendicularDistance ( PointList [ i ], Line ( PointList [ 1 ], PointList [ fin ])) si ( d > dmax ) { índice = i dmax = d } }ResultList [] = vacío ;# Si la distancia máxima es mayor que epsilon, simplifica recursivamente if ( dmax > epsilon ) { # Llamada recursiva recResults1 [] = DouglasPeucker ( PointList [ 1. .. index ], epsilon ) recResults2 [] = DouglasPeucker ( PointList [ index ... end ], epsilon )# Construir la lista de resultados ResultList [] = { recResults1 [ 1. .. length ( recResults1 ) - 1 ], recResults2 [ 1. .. length ( recResults2 )]} } else { ResultList [] = { PointList [ 1 ], PointList [ end ]} } # Devolver el resultado return ResultList []

Solicitud

El algoritmo se utiliza para el procesamiento de gráficos vectoriales y la generalización cartográfica . Se reconoce como el que proporciona las mejores representaciones perceptuales de las líneas originales. Sin embargo, puede producirse una autointersección si la aproximación aceptada no es suficientemente precisa, lo que ha llevado al desarrollo de algoritmos variantes. [ 3 ]

El algoritmo se utiliza ampliamente en robótica [ 4 ] para realizar la simplificación y la eliminación de ruido de los datos de rango adquiridos por un escáner de rango giratorio ; en este campo se conoce como el algoritmo de división y fusión y se atribuye a Duda y Hart . [ 5 ]

Complejidad

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 viene 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 de los casos, i = ⁠ n / 2 ⁠ o i = ⁠ n ± 1 / 2 ⁠ en cada invocación recursiva produce un tiempo de ejecución de Ω( n log n ) .

Utilizando estructuras de datos de envolvente convexa (total o semi-) dinámicas , la simplificación realizada por el algoritmo se puede lograr en un tiempo O ( n log n ) . [ 6 ]

El tiempo de ejecución para la generalización del modelo digital de elevación utilizando la variante tridimensional del algoritmo es O ( n³ ) , pero se han desarrollado técnicas para reducir el tiempo de ejecución para datos más grandes en la práctica. [ 7 ]

Algoritmos similares

Comparación con el algoritmo de Visvalingam-Whyatt

Entre los algoritmos alternativos para la simplificación de líneas se incluyen:

  • Visvalingam–Whyatt
  • Reumann-Witkam
  • simplificación de Opheim
  • simplificación del idioma
  • Zhao-Saalfeld
  • Imai-Iri

Véase también

Lecturas adicionales

  • Ramer, Urs (1972). "Un procedimiento iterativo para la aproximación poligonal de curvas planas". Computer Graphics and Image Processing . 1 (3): 244– 256. doi : 10.1016/S0146-664X(72)80017-0 .
  • Douglas, David; Peucker, Thomas (1973). "Algoritmos para la reducción del número de puntos necesarios para representar una línea digitalizada o su caricatura". Cartographica: The International Journal for Geographic Information and Geovisualization . 10 (2): 112– 122. Bibcode : 1973CIJGI..10..112D . doi : 10.3138/FM57-6770-U75U-7727 .
  • Hershberger, John; Snoeyink, Jack (1992). Aceleración del algoritmo de simplificación de líneas de Douglas-Peucker . Actas del 5.º Simposio sobre Manejo de Datos. págs. 134-143 . El informe técnico TR-92-07 de la UBC está disponible en: Acelerando el algoritmo de simplificación de líneas de Douglas-Peucker | Ciencias de la Computación en la UBC.
  • Duda, RO; Hart, PE (1973). Pattern Classification and Scene Analysis . Nueva York: Wiley. Bibcode : 1973pcsa.book.....D . Archivado del original el 15 de julio de 2011.
  • Visvalingam, M.; Whyatt, JD (1992). Generalización de líneas mediante eliminación repetida del área más pequeña (Informe técnico). Documento de debate. Grupo de Investigación de Sistemas de Información Cartográfica (CISRG), Universidad de Hull. 10.

Referencias

  1. ↑ Shi, Wenzhong; Cheung, ChuiKwan (2006). "Evaluación del rendimiento de algoritmos de simplificación de líneas para la generalización vectorial". The Cartographic Journal . 43 (1): 27– 44. Bibcode : 2006CartJ..43...27S . doi : 10.1179/000870406x93490 .
  2. ↑ Prasad, Dilip K.; Leung, Maylor KH; Quek, Chai; Cho, Siu-Yeung (2012). "Un nuevo marco para hacer que los métodos de detección de puntos dominantes sean no paramétricos" . Image and Vision Computing . 30 (11): 843– 859. doi : 10.1016/j.imavis.2012.06.010 .
  3. ↑ Wu, Shin-Ting; Marquez, Mercedes (2003). "Un algoritmo Douglas-Peucker sin autointersección". XVI Simposio Brasileño de Gráficos por Computadora y Procesamiento de Imágenes (SIBGRAPI 2003) . São Carlos, Brasil: IEEE. pp. 60–66 . CiteSeerX 10.1.1.73.5773 . doi : 10.1109/SIBGRA.2003.1240992 . ISBN   978-0-7695-2032-2. S2CID 10163908 . 
  4. ↑ Nguyen, Viet; Gächter, Stefan; Martinelli, Agostino; Tomatis, Nicola; Siegwart, Roland (2007). "Una comparación de algoritmos de extracción de líneas utilizando datos de rango 2D para robótica móvil en interiores" (PDF) . Autonomous Robots . 23 (2): 97– 111. Bibcode : 2007AuRob..23...97N . doi : 10.1007/s10514-007-9034-y . hdl : 20.500.11850/9089 . S2CID 35663952 . 
  5. ↑ Duda, Richard O.; Hart , Peter E. (1973). Clasificación de patrones y análisis de escenas . Nueva York: Wiley. ISBN 0-471-22361-1.
  6. ↑ Hershberger, John; Snoeyink, Jack (1992). Aceleración del algoritmo de simplificación de líneas de Douglas-Peucker (PDF) (Informe técnico).
  7. ↑ Fei, Lifan; He, Jin (2009). "Un algoritmo tridimensional de Douglas-Peucker y su aplicación a la generalización automatizada de DEM". Revista Internacional de Ciencias de la Información Geográfica . 23 (6): 703– 718. Bibcode : 2009IJGIS..23..703F . doi : 10.1080/13658810701703001 .
  • Boost.Geometry admite el algoritmo de simplificación de Douglas-Peucker.
  • Implementación del algoritmo de Ramer-Douglas-Peucker y muchos otros algoritmos de simplificación con licencia de código abierto en C++.
  • Implementación XSLT del algoritmo para su uso con datos KML.
  • Puedes ver el algoritmo aplicado a un registro GPS de un paseo en bicicleta en la parte inferior de esta página.
  • Visualización interactiva del algoritmo
  • Implementación en F#
  • Implementación de gemas Ruby
  • JTS, Java Topology Suite , contiene implementaciones en Java de muchos algoritmos, incluido el algoritmo de Douglas-Peucker.
  • Código Rosetta (Implementaciones en muchos lenguajes)
  • Simplificación de polilíneas 2D en CGAL , la biblioteca de algoritmos de geometría computacional. Simplifica simultáneamente muchas curvas con la garantía de no introducir intersecciones.