Algoritmo de Generalización de curvas Douglas-Peucker

El algoritmo de generalización de curvas es un proceso utilizado en matemáticas, computación gráfica, cartografía y procesamiento de datos para simplificar una curva compleja manteniendo su forma general o características esenciales.

La generalización de curvas consiste en transformar una curva detallada (compuesta por muchos puntos o segmentos) en una versión más simple, con menos puntos, que aún represente de manera adecuada la forma original.

• Reducir la complejidad geométrica sin perder la información relevante.
  
• Optimizar almacenamiento y procesamiento, especialmente en sistemas con recursos limitados.
  
• Facilitar la visualización o el análisis de los datos.

• Cartografía: al hacer zoom en un mapa, se generalizan los ríos, caminos o límites para que se vean más simples y limpios
  
• Computación gráfica: para representar trayectorias o contornos de objetos de forma más eficiente.
  
• Análisis de datos espaciales: para suavizar o resumir trayectorias en sistemas GPS o datos temporales.

• Algoritmo de Douglas-Peucker: reduce el número de puntos en una curva manteniendo la forma general.
  
• Interpolación y ajuste de curvas: como splines o curvas de Bézier.

En computación gráfica y programación, la generalización de curvas se utiliza para reducir la cantidad de puntos que definen una línea o curva, lo cual mejora el rendimiento en renderizado, almacenamiento y transmisión de datos. Por ejemplo, al simplificar una trayectoria dibujada por el usuario o los bordes de una figura compleja.

Uno de los algoritmos más conocidos para esto es Douglas-Peucker, que reduce el número de puntos conservando la forma principal de la curva.

Estos algoritmos buscan simplificar la curva reduciendo su complejidad geométrica, conservando su forma general. Aquí sí se habla de “generalización” propiamente dicha.

• Douglas-Peucker
  
• Visvalingam-Whyatt

• Reamostrado equidistante (cuando se combina con eliminación de puntos)

El algoritmo Douglas-Peucker , también conocido como algoritmo Ramer-Douglas-Peucker o algoritmo iterativo de ajuste de punto final, es un algoritmo para suavizar polilíneas (líneas compuestas por segmentos lineales) reduciendo el número de puntos. La curva simplificada debe conservar la forma aproximada de la curva original, pero consistir únicamente en un subconjunto de los puntos que la definieron.

El grado de engrosamiento se controla mediante un único parámetro ε, que define la distancia máxima entre los puntos originales y la curva simplificada.

El algoritmo fue desarrollado independientemente por Urs Ramer en 1972 y por David Douglas y Thomas Peucker en 1973.

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.

Dada una curva  con estos puntos intermedios

d= (0, 0), (1, 0.1), (2, -0.1),(3, 5), (4, 0), (5, 0)

Se debe definir el inicio y el final  de la curva

Start: [0, 0]

End: [5, 0]

Se hace uso de Fórmula de distancia perpendicular con los puntos intermedios (1, 0.1), (2, -0.1),(3, 5), (4, 0)

fórmula dada el algoritmo

p=  [1, 0.1]

d =|((End – Start),  (Start – p))| /|(End -Start)||

Reemplazando las variables 

p=(1, 0.1)

d= |((5, 0) – (0,  0), (0, 0)-(1, 0.1))|/ |(5, 0)- (0, 0)|

d=0.1

Se hace con el segundo punto 

p=  (2, -0.1)

d= |((5, 0) – (0,  0), (0, 0)-(2, – 0.1))|/ |(5, 0)- (0, 0)|

d= 0.1

Se hace con el tercero

p=  (3, 5)

d= |((5, 0) – (0,  0), (0, 0)-(3, 5))|/ |(5, 0)- (0, 0)|

d= 5.0

Se hace con el cuarto 

p=  (3, 5)

d= |((5, 0) – (0,  0), (0, 0)-(4, 0))|/ |(5, 0)- (0, 0)|

d= 0, 0

Luego se calcula las distancias que sean mayor que epsilon = 1.0

Solo el punto (3, 5)  dio una distancia mayor a epsilon

Luego se hace uso de las dos recursividades donde los puntos deben volver a realizar la búsqueda de  distancia perpendicular.

rec1 = el primer punto  hasta la distancia más lejana encontrada

 rec2= la distancia más lejana encontrada mas el ultimo punto 

Con valores

rec 1= (0, 0), (1, 0.1), (2, -0.1),(3, 5)

rec 2= (3, 5), (4, 0), (5, 0)

Se hace uso de la formula nuevamente  para encontrar la distancia mas alejada en cada recursividad

Rec1:

Start =  (0, 0)

End = (3, 5)

P=  (1, 0.1), (2, -0.1)

Donde sus distancias al realizar la fórmula son menores que epsilon, entonces solo retorna el inicio y el final de los puntos dados 

rec2:

Start = (3, 5)

End = (5, 0)

P= (4, 0)

Donde su distancia al realizar la formula es menor a epsilon, entonces retorna el inico y el final de los puntos definidos 

para dar como resultado 

Rec1= (0, 0) , (3, 5)

Rec2 =(3, 5),  (5.0)

Usando la fórmula: ((rec1[:-1], rec2))

Deja los puntos :  (0, 0), (3, 5),  (5.0)

De los 6 puntos datos, el algoritmo de Douglas-Peucker redujo los puntos manteniendo su forma general con tres puntos 

https://colab.research.google.com/drive/1GN6oh9UcJDAF4ay6jSssdaIizahX7rSu?usp=sharing

La generalización de curvas permite simplificar formas complejas conservando su esencia, lo cual es fundamental en diversas disciplinas como la cartografía, la computación gráfica y el análisis de datos espaciales, donde la precisión visual o funcional no siempre requiere una representación detallada.

El uso de algoritmos como Douglas-Peucker permite optimizar el procesamiento y almacenamiento de datos, al reducir el número de puntos en una curva sin comprometer significativamente su forma original, lo que resulta especialmente útil en entornos con recursos limitados.

Este proceso mejora la eficiencia en la visualización y transmisión de información gráfica, ya que las curvas simplificadas requieren menos recursos para ser renderizadas o enviadas, sin perder claridad en su representación.

La generalización de curvas tiene aplicaciones prácticas en sistemas de navegación, diseño gráfico y sistemas de información geográfica, ayudando a representar caminos, fronteras o trayectorias de forma más limpia y funcional a diferentes escalas.

El parámetro de error (ε) utilizado en algoritmos como Douglas-Peucker brinda control sobre el grado de simplificación, lo que permite ajustar el equilibrio entre precisión y eficiencia según las necesidades del sistema o del usuario.

Autores: David Steven Rojas Santana, Camilo Uribe, Daniela Caterine
Editor: Magister ingeniero Carlos Iván Pinzón Romero
Código: UCCG-9
Universidad: Universidad Central

Álvarez, G. (2011, junio 15). Curvas de nivel generadas con Global Mapper [Imagen]. Geofumadas. https://geofumadas.com/wp-content/uploads/2011/06/crearcurvasdenivelconglobalmapper3.jpg

Autor desconocido. (2007). Algoritmo de Douglas-Peucker [PDF]. Universidad de Sevilla. https://biblus.us.es/bibing/proyectos/use/abreproy/4370/fichero/Volumen+1%252FAnexo.pdf

García-Balboa, J. L., & Ariza-López, F. (1999, junio). Esquema del funcionamiento del algoritmo de Douglas-Peucker [Imagen]. ResearchGate. https://www.researchgate.net/figure/Esquema-del-funcionamiento-del-algoritmo-de-Douglas-Peucker_fig1_326132347

Herrera Morales, A. (2014, marzo 7). Algoritmo de Ramer-Douglas-Peucker de simplificación de rutas [Entrada de blog con imagen]. Avelino Herrera. https://avelinoherrera.com/blog/index.php?entry=entry140307-095351

Isochrone. (2024, May 31). Douglas–Peucker and Visvalingam–Whyatt simplification algorithms [Imagen]. Wikipedia. https://en.wikipedia.org/wiki/Ramer–Douglas–Peucker_algorithm#/media/File:Douglas–Peucker_and_Visvalingam–Whyatt_simplification_algorithms.svg

Mohneesh, S. (2021, septiembre 20). Applications of Ramer-Douglas-Peucker algorithm in machine learning that you might not have heard. Medium. https://mohneesh0.medium.com/applications-of-ramer-douglas-peucker-algorithm-in-machine-learning-that-you-might-not-have-heard-63b0c4f15a43

Moreno Nova, E. A. (2021, marzo 5). Generación de curvas (splines) [Imagen]. Niixer. https://niixer.com/index.php/2021/03/05/generacion-de-curvas-splines/