Line Generalisation Aglorithms - Simplification Overview

Algoritmos de Simplificación de Líneas

Los algoritmos de simplificación de líneas se han ido desarrollando a lo largo de los años con el fin de eliminar información redundante o innecesaria de coordenadas de entidades lineales, mientras que se retienen las características perceptivas de la línea. Por lo general trabajan aplicando algún criterio geométrico a los pares de coordenadas de la línea (como la distancia entre puntos o el desplazamiento desde una línea central). La Figura 1 muestra una línea antes y después de haber sido simplificada, las flechas indican los puntos que se han eliminado durante el proceso.

Figura 1. Simplificación de Líneas (Fuente: McMaster & Shea 1992)

Existen varias razones que justifican la necesidad de simplificar líneas digitalizadas. Se resumen algunas a continuación:
1.	Reducción del tiempo de impresión: la simplificación reduce el número de pares de coordenadas (x,y), incrementando así la velocidad de impresión (a mayor velocidad se mejoran las cualidades estéticas de la línea).
2.	Reducción del espacio de almacenamiento: : la simplificación puede reducir un amplio conjunto de datos a un 70%, reduciendo tanto el espacio de almacenamiento requerido para los datos como el coste de almacenarlos.
3.	Conversión vector a raster más rápida: un conjunto de coordenadas simplificadas posibilitará una conversión del formato vectorial al raster más rápida.
4.	Procesado vectorial más rápido: el tiempo necesario para procesar los vectores, incluyendo la traslación, rotación, reescalado, análisis cartométricos y la generación de algunos símbolos se reduce bastante en el caso de los datos simplificados.

Rutinas de Procesado Local

Como base en la introducción a los algoritmos de simplificación de líneas, la Figura 2 representa dos rutinas locales de procesado. En la parte izquierda (A) se muestra el “algoritmo de la distancia perpendicular” que trabaja con una serie de operaciones secuenciales sobre triadas de pares de coordenadas. En primer lugar se traza una línea perpendicular al segmento que une el primer y tercer punto (p1 y p3) de la triada, desde el punto intermedio (p2). Si la distancia es mayor que la tolerancia definida por el usuario, el punto intermedio se mantiene, pero si es menor que el valor de tolerancia, ese punto se elimina. Los tres puntos siguientes (p2, p3 y p4) pasan a formar la siguiente triada y se repite el proceso anterior. Este proceso se repite hasta que se alcanza el final de la línea..

Figura 2. Simplificador de Procesado Local (Fuente: McMaster & Shea 1992)

El “algoritmo de tolerancia angular” se representa en la parte derecha de la figura (B) y trabaja de un modo similar al descrito anteriormente, sólo se diferencia en que la tolerancia es angular y se mide entre los vectores que conectan los puntos p1 y p3, y p1 y p2.

Los dos algoritmos presentados en la Figura 2 y descritos anteriormente constituyen la base de la mayoría de los algoritmos de simplificación. El algoritmo en el que se centra el apartado de simplificación de líneas se conoce como el Algoritmo de Simplificación de Lang - una versión extendida del algoritmo de la distancia perpendicular de la Figura 2A. El Algoritmo de Simplificación de Lang tiene aceptación, entre otras cosas, porque mantiene las características geométricas originales de la línea. En la parte inferior hay enlaces (a la derecha) a dos lecciones interactivas que te ayudarán a visualizar cómo se aplica el algoritmo de Lang al simplificar una línea. Si deseas leer/revisar la teoría en este momento, accede a los enlaces de la izquierda.

Enlaces de Teoría:

Lecciones Interactivas del Algoritmo de Simplificación de Lang:

Generalización Digital
Suavizado de Líneas

Visualización de Ejercicio
Ejemplo Interactivo Simple

Pincha aquí para descargarte toda la teoría aparecida en este módulo