El algoritmo Ramer-Douglas-Peucker , también conocido como el algoritmo Douglas-Peucker y el 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 .
Ocurrencia
El propósito del algoritmo es, dada una curva compuesta de segmentos de línea (que también se llama Polilínea en algunos contextos), encontrar una curva similar con menos puntos. El algoritmo define "diferente" en función de la distancia máxima entre la curva original y la curva simplificada (es decir, la distancia de Hausdorff entre las curvas). La curva simplificada consta de un subconjunto de los puntos que definieron la curva original.
Algoritmo
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 de forma recursiva . Inicialmente se le dan todos los puntos entre el primer y el último punto. Marca automáticamente el primer y último punto a conservar. A continuación, busca el punto más alejado del segmento de línea con el primer y último punto como puntos finales; este punto es obviamente el más alejado en la curva del segmento de línea aproximado 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 mantenerse puede descartarse 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 mantenerse. El algoritmo se llama a sí mismo de forma recursiva con el primer punto y el punto más lejano y luego con el punto más lejano y el último punto, que incluye el punto más lejano marcado como guardado.
Cuando se completa la recursividad, se puede generar una nueva curva de salida que consta de todos y solo aquellos puntos que se han marcado como conservados.
Ramer-Douglas-Peucker no paramétrico
La elección de ε suele ser definida por el usuario. Como la mayoría de los métodos de ajuste de línea / aproximación poligonal / detección de punto dominante, puede hacerse no paramétrico utilizando el límite de error debido a la digitalización / cuantificación como condición de terminación. [1]
Pseudocódigo
(Supone que la entrada es una matriz basada en uno)
función DouglasPeucker (PointList [], epsilon) // Encuentra el punto con la distancia máxima dmax = 0 índice = 0 end = longitud (PointList) para i = 2 a (final - 1) { d = distancia perpendicular (PointList [i], Line (PointList [1], PointList [end])) si (d> dmax) { índice = i dmax = d } } ResultList [] = vacío; // Si la distancia máxima es mayor que épsilon, simplifica de forma recursiva if (dmax> épsilon) { // Llamada recursiva recResults1 [] = DouglasPeucker (PointList [1 ... índice], épsilon) recResults2 [] = DouglasPeucker (PointList [índice ... final], épsilon) // Construye la lista de resultados ResultList [] = {recResults1 [1 ... length (recResults1) - 1], recResults2 [1 ... length (recResults2)]} } más { ResultList [] = {PointList [1], PointList [end]} } // Devuelve el resultado return ResultList [] end
Enlace: https://karthaus.nl/rdp/
Solicitud
El algoritmo se utiliza para el procesamiento de gráficos vectoriales y generalización cartográfica . No siempre conserva la propiedad de no intersección propia para las curvas, lo que ha llevado al desarrollo de algoritmos variantes. [2]
El algoritmo se usa ampliamente en robótica [3] 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 conoce como el algoritmo de división y fusión y se atribuye a Duda y Hart . [4]
Complejidad
El tiempo de ejecución de este algoritmo cuando se ejecuta en una polilínea que consta de segmentos y los vértices están dados por la recurrencia dónde es el valor del índice en el pseudocódigo. En el peor de los casos, o en cada invocación recursiva y este algoritmo tiene un tiempo de ejecución de . En el mejor de los casos o en cada invocación recursiva, en cuyo caso el tiempo de ejecución tiene la solución conocida (a través del teorema maestro para las recurrencias de divide y vencerás ) de.
Usando estructuras de datos de casco convexo (totalmente o semi) dinámicas , la simplificación realizada por el algoritmo se puede lograr enhora. [5]
Algoritmos similares
Los algoritmos alternativos para la simplificación de líneas incluyen:
- Visvalingam – Whyatt
- Reumann – Witkam
- Simplificación de Opheim
- Simplificación de idioma
- Zhao-Saalfeld
Ver también
Otras lecturas
- Urs Ramer, "Un procedimiento iterativo para la aproximación poligonal de curvas planas", Procesamiento de imágenes y gráficos por computadora, 1 (3), 244–256 (1972) doi : 10.1016 / S0146-664X (72) 80017-0
- David Douglas y Thomas Peucker, "Algoritmos para la reducción del número de puntos necesarios para representar una línea digitalizada o su caricatura", The Canadian Cartographer 10 (2), 112-122 (1973) doi : 10.3138 / FM57-6770-U75U -7727
- John Hershberger y Jack Snoeyink, "Aceleración del algoritmo de simplificación de línea Douglas-Peucker", Proc 5th Symp on Data Handling, 134-143 (1992). Informe técnico de UBC TR-92-07 disponible en http://www.cs.ubc.ca/cgi-bin/tr/1992/TR-92-07
- RO Duda y PE Hart, "Clasificación de patrones y análisis de escenas", (1973), Wiley, Nueva York ( https://web.archive.org/web/20110715184521/http://rii.ricoh.com/~stork/ DHS.html )
- Visvalingam, M; Whyatt, JD (1992). Generalización de línea por eliminación repetida del área más pequeña (informe técnico). Informe de discusión. Grupo de Investigación de Sistemas de Información Cartográfica (CISRG), Universidad de Hull. 10.
Referencias
- ^ Prasad, Dilip K .; Leung, Maylor KH; Quek, Chai; Cho, Siu-Yeung (2012). "Un marco novedoso para hacer que los métodos de detección de puntos dominantes no sean paramétricos". Computación de imagen y visión . 30 (11): 843–859. doi : 10.1016 / j.imavis.2012.06.010 .
- ^ Wu, Shin-Ting; Márquez, Mercedes (2003). "Un algoritmo de Douglas-Peucker de no auto-intersección". 16º Simposio Brasileño de Computación Gráfica y Procesamiento de Imágenes (SIBGRAPI 2003) . Sao Carlos, Brasil: IEEE. págs. 60–66. CiteSeerX 10.1.1.73.5773 . doi : 10.1109 / SIBGRA.2003.1240992 . ISBN 978-0-7695-2032-2. Parámetro desconocido
|book-title=
ignorado ( ayuda ) - ^ 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) . Robots autónomos . 23 (2). págs. 97-111. doi : 10.1007 / s10514-007-9034-y . hdl : 20.500.11850 / 9089 .
- ^ Duda, Richard O .; Hart, Peter E. (1973). Clasificación de patrones y análisis de escenas . Nueva York: Wiley. ISBN 0-471-22361-1.
- ^ Hershberger, John; Snoeyink, Jack (1992). Acelerando el algoritmo de simplificación de línea de Douglas-Peucker (PDF) (Informe técnico).
enlaces externos
- Boost.Geometry admite el algoritmo de simplificación de Douglas-Peucker
- Implementación 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.
- Puede ver el algoritmo aplicado a un registro de 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 ruby gem
- JTS, Java Topology Suite , contiene la implementación de Java de muchos algoritmos, incluido el algoritmo Douglas-Peucker