:: Un algoritmo para la creación de polígonos a partir de estructuras de líneas sin topología GIS ::

Fecha de Publicación: 07/09/2003

Este artículo fue también publicado por la revista Mapping, en su número 89 de Octubre de 2003.

  INTRODUCCIÓN.

A menudo el desarrollo de pequeñas aplicaciones relacionadas con información geográfica encuentra uno de sus principales problemas en la formación y tratamiento de polígonos. Los Sistemas de Información Geográfica (SIG) tienen solucionadas las tareas de poligonación desde hace décadas, algunos de ellos con estructuras topológicas altamente fiables. Sin embargo, a veces lo que se busca es incorporar algunas de las funciones básicas de manejo de polígonos a pequeñas aplicaciones (cálculo de áreas, perímetros, centroides, sombreados de color, etc.), que no necesitan de toda la potencia brindada por las estructuras de datos verdaderamente topológicas de un GIS.

Aquí se propone un algoritmo encaminado a dar respuesta a este tipo de situaciones. En concreto, se plantea el proceso lógico para la formación de polígonos a partir de una red de líneas sin topología. Imaginemos una red de segmentos de línea y un punto elegido por el usuario en alguna parte de su extensión; en ese caso, el cerebro humano puede percibir visualmente el polígono envolvente al punto de manera casi inmediata, pero la definición por medios geométricos no es tan sencilla, pues involucra un buen número de pasos intermedios. Para llevar a cabo los mismos utilizaremos como herramienta los principios de la geometría vectorial y un poco de imaginación.

Objetivo del algoritmo: a partir de un punto dado, reconstruir su polígono envolvente según una red de segmentos de línea.Dicho de otro modo, se trata de averiguar qué líneas encierran el polígono donde está el punto (líneas verdes) y todo ello en tiempo de ejecución (al-vuelo). Es importante resaltar que el escenario con el que trabajamos se basa en una estructura de líneas que no tiene topología de polígonos por lo que los algoritmos de punto en polígono no son aplicables.

Buscamos en consecuencia, calcular selectivamente el polígono envolvente al punto de base, con el objeto de poder realizar posteriormente algunas funciones básicas con éste, como el cálculo de su área, su perímetro, centroide, aplicar un sombreado de color, etc. Se puede comprender mejor la funcionalidad del algoritmo que vamos a exponer viendo el funcionamiento de su ejecutable terminado:

Descargar Ejecutable
(52 Kb. No necesita ningún tipo de instalación)

  APLICACIONES POTENCIALES.

Las aplicaciones podrían estar el desarrollo de programas que trabajen con la representación de datos geográficos basados en áreas y líneas rectas: gestión de parcelario, catastro urbano, y aplicaciones de dibujo de gráficos en general.

  LIMITACIONES.

Asumimos en este artículo una red de líneas (segmentos) sin vértices intermedios entre los puntos de origen o fin y sin intersecciones que no se correspondan con dichos nodos de origen o fin. Igualmente, tampoco se han contemplado polígonos-isla en la estructura de líneas.

Otra de las limitaciones importantes es la imposibilidad de almacenar atributos sobre los polígonos. Al estar creados estos polígonos en tiempo de ejecución y no tener almacenada su estructura en ninguna parte más que en la memoria volátil del ordenador, no es posible almacenar atributos asociados.

No obstante, todas estas limitaciones podrían ser salvadas satisfactoriamente mediante la incorporación de lógica adicional, la cual excede ya el ámbito de este artículo. Por simplicidad en la exposición no se han incorporado estas cuestiones.

  PASOS PROPUESTOS EN EL ALGORITMO.

El algoritmo propuesto consta de los siguientes pasos:

1.
Localizar la línea más próxima al punto de entre toda la red de líneas (línea base).
2.
Orientar dicha línea más cercana con respecto al punto y seleccionar el vértice adecuado de los dos posibles (el de la izquierda relativa).
3.
Seleccionar el resto de líneas que tienen dicho vértice en común.
4.
Sobre estas líneas seleccionadas, calcular los ángulos máximos en el sentido contrario de las agujas del reloj.
5.
Seleccionar la línea con un ángulo mayor con respecto a la línea tomada como base.
6.
Reconfigurar como nueva línea base la línea seleccionada en el paso anterior y repetir desde el paso 3: Selección de líneas sobre el nodo final, cálculo de ángulos y comprobación del nodo final.
7.
Si el nodo final es igual que el nodo inicial en el que empezó el polígono, terminar el proceso. Si no hay más líneas que elegir y el nodo final no es igual al inicial, entonces el polígono está abierto y también se termina el proceso.
8.
En el caso de que el polígono no esté abierto, seleccionar todas las líneas que forman el polígono y operar con ellas para lo que sea necesario; por ejemplo: cálculo de áreas, perímetros, centroides, sombreado de color, etc

Desarrollaremos a continuación la ejecución detallada de cómo realizar cada paso y al final del artículo veremos cómo todos esos pasos encajan en un pequeño programa realizado en Visual Basic que desarrolla el algoritmo aquí propuesto. Tanto el código fuente de esta aplicación demostrativa (en versiones Visual Basic y Java), como su fichero ejecutable están disponibles para la descarga al final de este artículo.

  PASO 1. LOCALIZAR LA LÍNEA MÁS PRÓXIMA AL PUNTO.

El algoritmo comenzaría por calcular las distancias de todas y cada una de las líneas con respecto al punto. La razón de este calculo radica en el hecho de que la línea más cercana será la primera parte del polígono que encierra al punto. Este principio podría dar lugar a problemas en el caso de operar con polígonos-isla (un polígono-isla es un polígono contenido completamente dentro de otro polígono más grande); sin embargo, ya hemos dicho que por claridad de exposición no vamos a tener en cuenta el supuesto de los polígonos-isla en este algoritmo.

La geometría nos dice que la distancia más corta entre un punto y una recta es la perpendicular a dicha recta que pasa por ese punto. En otras palabras, si pensamos en vectores en vez de líneas, sería el vector que pasando por el punto de medición de la distancia mantiene un producto escalar = 0 (precisamente por ser perpendicular). Una fórmula inmediata para el cálculo de la distancia entre un punto (x,y) y una recta entre los puntos x0, y0 - x1, y1 es la siguiente:


Veamos un ejemplo. Sea una línea L definida por estos dos puntos:

x0 = 511 y0 = 416
x1 = 694 y1 = 140

Y un punto P definido por las coordenadas:

x = 589 y = 203

Para calcular la distancia mínima de este punto a la línea procederíamos de la forma:

d= ABS((416-140)*589+(694-511)*203+(511*140-694*416))/SQR((694-511)^2+(140-416)^2)=52.6970

Este resultado 52.6970 estaría expresado en las unidades de las coordenadas (por ejemplo en metros si trabajamos con coordenadas UTM) y se corresponde con la distancia más corta del punto a la línea, que viene a ser la perpendicular que pasa por el punto tomado como referencia. Fijémonos en que hemos obtenido el valor absoluto (ABS), pues en este caso nos da lo mismo que la distancia sea positiva o negativa.

Hay que considerar la distancia sobre el segmento y no sobre la recta, que se prolonga hasta el infinitoAhora bien, esta formulación nos da la distancia más corta a una línea, pero no a un segmento de línea. Es decir, trata el segmento como prolongado hacia el infinito por ambos extremos, como si los vértices de inicio y fin no supusieran delimitación alguna. Necesariamente tenemos que tener en cuenta los extremos de los segmentos para decirle al programa que el cálculo de la distancia según la fórmula que hemos visto sólo se debe aplicar en el ámbito del segmento. Si no lo hiciéramos así, la selección del segmento más cercano al punto podría ser errónea, tal y como se ve en la figura adjunta.

En el caso de que el ángulo formado entre la línea y el punto de medición sea superior a 90° (es decir, que dicho ángulo sea obtuso), la distancia a aplicar no será la derivada por la ecuación antes vista, sino la distancia entre el punto y su vértice más cercano. Por el contrario, si los dos ángulos formados entre la línea y el punto son inferiores o iguales a 90° (es decir, si ambos ángulos son agudos o agudo y recto), la distancia a aplicar en ese caso sí que sería la derivada de la ecuación.

¿Cómo calcular el ángulo entre la línea y el punto de medición en cada extremo del segmento? Utilizando la geometría vectorial sabemos que el producto escalar entre dos vectores puede facilitarnos el ángulo que forman ambos. El producto escalar entre dos vectores, uno |V| definido por las coordenadas (x,y) y otro |W| definido por las coordenadas (p, q) se puede expresar de dos formas:

  • Mediante coordenadas cartesianas: (x·p)+(y·q)
  • O bien mediante coordenadas polares: |V| · |W| · cos (donde es el ángulo formado por los dos vectores).

Como ambas expresiones equivalen a la misma magnitud (el producto escalar), las igualamos y obtenemos:

Cos = ( (x·p)+(y·q) ) / |V| · |W|

Posteriormente, el cálculo del inverso del coseno de nos arrojará el ángulo formado por los dos vectores. Este principio nos servirá también en otros pasos del algoritmo para conocer indirectamente otros ángulos.

Pero veámoslo con un ejemplo basado en la siguiente configuración geométrica:

Lo primero que hacemos es calcular la longitud de los dos segmentos mediante coordenadas. Estas longitudes nos servirán de valores del módulo de los dos vectores que posteriormente construiremos:

|Vector 1| = SQR((146-164)^2+(85-119)^2)=38.47
|Vector 2| = SQR((227-164)^2+(141-119)^2)=66.73

Para construir vectores a partir de los dos segmentos tomaremos el vértice en común (164, 119) como origen del sistema de coordenadas, restándole sus valores x e y al resto de las coordenadas con las que operaremos.

Cos = (((227-164)*(146-164))+((141-119)*(85-119)))/(38.47*66.73)=-0.73312209

Ahora el inverso del coseno nos devuelve el ángulo: ACS -0.73312209=137.15°

Como el ángulo es mayor de 90°, ya sabemos que se trata de un ángulo obtuso, y en este caso la distancia a considerar no sería la calculada por la ecuación de la distancia entre la recta infinita y el punto, sino la distancia euclideana entre el punto de medición y su vértice más cercano (dicho cálculo sería el mismo que el realizado antes bajo la denominación de módulo del vector 1).

En resumen, podemos saber cuál es el segmento más cercano al punto solicitado por el usuario aplicando la ecuación de la distancia del punto a la recta (infinita), y posteriormente delimitar el ámbito de aplicación de dicha medición en función de los ángulos formados por los vértices para saber si hay que aplicar la ecuación o bien la distancia euclideana a los extremos de los segmentos. Con ello podemos computar rápidamente la distancia a todos y cada uno de los segmentos de la capa de líneas y seleccionar aquel segmento que tenga una distancia menor, que como hemos dicho antes será la primera pieza del polígono envolvente que buscamos.

  PASO 2. ORIENTAR DICHA LÍNEA CON RESPECTO AL PUNTO Y SELECCIONAR EL NODO DE LA PARTE IZQUIERDA.

Es extremadamente importante proceder en el sentido contrario de las agujas del reloj en el proceso de reconstrucción del polígono envolvente. Es decir, ir definiendo las líneas que forman el polígono envolvente en el sentido contrario al horario. Ello es importante por dos razones:

  • Por mantener un orden en el proceso de generación del polígono.
  • Porque otros algoritmos a aplicar a posteriori como la medición de superficies exigen también una ordenación de las líneas en el sentido contrario de las agujas del reloj.

Por ello, una vez seleccionada la línea más cercana al punto deberemos saber por cuál de los dos nodos debemos comenzar a trabajar en la búsqueda de líneas con ese origen. Este proceso de orientación básicamente consiste en tener en cuenta la disposición geométrica del punto y de la línea seleccionada con respecto a éste.

Para ello tiramos una línea imaginaria con origen en el punto y destino el punto medio de la línea. Dicho punto medio es fácil de obtener a partir de las propias coordenadas:

xmed. = x0 / 2 + x1 / 2
ymed. = y0 / 2 + y1 / 2

Ahora se trataría de saber qué nodo queda a la derecha de esa nueva línea que divide el plano bidimensional donde se encuentra el vector en dos partes. El vértice que caiga en la parte izquierda será siempre el que tendremos que coger como base para las siguientes fases del algoritmo. Ello nos garantiza que seguiremos el sentido contrario de las agujas del reloj, puesto que esté donde esté el segmento, la orientación relativa entre el origen (punto) y el destino (punto medio de la línea) será siempre la misma.

Veamos con detalle cómo saber cuál de los dos vértices está a la derecha de la línea media según uno de los múltiples algoritmos existentes (GOSPER, 1998). Partimos de la ecuación explícita de la recta:

y = m · x + n

Donde m es la pendiente de la recta y n es la ordenada en el origen.
Si se conoce la pendiente de la línea y un punto en la línea entonces tenemos que:

y - y1 = m · (x - x1)

Operamos con esta ecuación y obtenemos:

y - y1 = m · x - m · x1
y - m · x = y1 - m · x1

La pendiente m la sacamos de (y2-y1) / (x2-x1); sustituyendo m por esta expresión tenemos:

y - ( (y2 - y1) / (x2 - x1) ) · x = y1 - ( (y2-y1) / (x2-x1) ) · x1

Multiplicamos la ecuación de arriba por (x2-x1) con el objeto de disminuir el peso del cálculo en el ordenador al evitar divisiones. Como consecuencia tenemos la siguiente ecuación, en la cual a partir de dos puntos que definen una línea (x1, y1) junto con (x2, y2), y un punto ubicado en cualquier lugar (x, y) podemos saber si éste queda a la derecha de la línea, a la izquierda o si pertenece a la línea:

(x2-x1) · y - (y2-y1) · x = (x2-x1) · y1 - (y2-y1) · x1

Dicha igualdad sólo se cumplirá en el caso de que el punto analizado pertenezca a la recta. En caso de que el punto no pertenezca a la recta, la igualdad no se cumplirá y observando los términos resultantes podremos responder a nuestra pregunta: ¿a qué lado de la recta queda el punto analizado?. Así, una vez obtenidos los dos términos restamos el primer término del segundo término. Si el resultado es positivo, el punto está a la derecha de la línea imaginaria divisoria del plano, mientras que si es negativo, significa que el punto cae en la parte izquierda (¡y ese es el punto, pues, que nos interesa!); si el resultado es cero, entonces el punto analizado pertenece a la línea imaginaria divisoria o a su prolongación hacia el infinito.

Veámoslo con un ejemplo. Tenemos una línea definida por los siguientes vértices:

x1=400 y1=100
x2=455 y2=160

Y queremos saber si el punto definido por las coordenadas x=420, y=150 está a la derecha o a la izquierda de la línea.

Aplicamos la igualdad expuesta anteriormente, de la forma:

(455-400)*150-(160-100)*420 = (455-400)*100-(160-100)*400

La igualdad no se cumple, luego ya sabemos que el punto no pertenece a la recta divisoria imaginaria. Observamos los términos resultantes restando el resultado del primer término al segundo y obtenemos:

(-18500) - (-16950) = -1550

El resultado es negativo, luego el punto analizado está a la izquierda de la línea y por tanto es el vértice que nos interesaría. Como en este caso estamos operando con líneas formadas por dos vértices, analizando un punto conocemos el resultado del otro por exclusión (si uno cae en la parte derecha, sabemos que el otro pertenece al lado izquierdo y viceversa.)

  PASO 3. SELECCIONAR LOS SEGMENTOS DE LÍNEA QUE CONTENGAN EL VÉRTICE ELEGIDO EN EL PASO ANTERIOR.

Una vez que sabemos el vértice correcto, el siguiente paso es sencillo: seleccionar todas las líneas que cuentan con esas coordenadas en sus vértices origen o final. En el código fuente adjuntado al final de este artículo se puede ver un ejemplo de cómo realizar este paso; en dicho ejemplo hemos recurrido a una matriz para almacenar las coordenadas de la red de segmentos de líneas, y mediante un bucle recorremos dicha matriz en busca de segmentos que tengan en alguno de sus dos pares de coordenadas el vértice con el que estamos trabajando.

  PASO 4. CALCULAR LOS ÁNGULOS MÁXIMOS EN EL SENTIDO CONTRARIO DE LAS AGUJAS DEL RELOJ.

Si existen varias líneas que parten del vértice seleccionado, tenemos que ver la manera de seleccionar la línea que nos interesa de entre varias. Saber qué línea es la siguiente que envuelve al punto no es difícil: aquella que tiene un ángulo mayor (medido en el sentido contrario de las agujas del reloj). Básicamente la idea es que una vez conocemos uno de los lados del polígono cada línea que realice el mayor giro en el sentido contrario de las agujas del reloj nos irá delimitando lo que queda dentro y fuera del polígono.

Por ejemplo, en la figura adjunta tenemos el punto de origen, sobre el que hemos calculado el segmento más cercano (rojo), luego hemos seleccionado de entre sus dos vértices el que queda a la izquierda de la línea media (gris punteada) y nos encontramos ahora con dos nuevos segmentos seleccionados y candidatos a formar parte del polígono: el segmento azul y el verde. Aquel segmento que junto con el más cercano al punto (rojo) forme un ángulo mayor (medido en el sentido de las agujas del reloj) será la que forme parte del polígono.

Vemos en la figura que el segmento azul forma un ángulo de 122.83° con la línea roja, mientras que el segmento verde forma un ángulo mucho mayor (259.19°). Sería este último segmento el que constituiría la siguiente parte del polígono, ya que es el que presenta un giro mayor en el sentido contrario de las agujas del reloj.

Ya hemos visto anteriormente en este artículo (Paso 1) cómo a partir del producto escalar entre dos vectores podemos determinar el ángulo que estos vectores forman entre sí. Sin embargo, este ángulo no necesariamente representa la magnitud que buscamos.

Entre cada par de segmentos, salvo que estén totalmente alineados, existen dos ángulos en función de por qué lado se mida, tal y como se muestra en la figura de al lado. El hecho es que tenemos que saber qué angulo es el que tenemos que tomar y además hacer "comparables" los ángulos formados por varios segmentos con respecto a la línea base para poder elegir en consecuencia (conocer si la magnitud del ángulo medido está a un lado u otro de la línea base para saber si debe ser restada de 360°).

Vayamos por partes. Para asegurar que el origen de la medición del ángulo es la línea base, tomaremos como origen de coordenadas el vértice en común; de esa manera, restamos los valores x e y del vértice en común al resto de coordenadas con las que operamos, formando vectores como ya hemos visto anteriormente. Nos quedaría ahora saber si el ángulo que hemos determinado es mayor o menor de 180°, lo cual averiguaremos mediante el proceso ya descrito de determinar a qué lado de la una recta queda un punto. Si el punto queda al lado derecho de la línea base, utilizaremos el ángulo tal y como está. Si por el contrario, la recta azul de la figura quedara por debajo de la línea base (su izquierda relativa), tendríamos que restar el ángulo obtenido de 360° para tener el ángulo de giro en el sentido contrario de las agujas del reloj. Es decir, si el punto está a la derecha de la línea base (debidamente orientada), se usa el ángulo sin modificaciones; si por el contrario cae en la parte izquierda, el ángulo vendría dado por 360 -

  PASO 5. SELECCIONAR LA LÍNEA CON ÁNGULO MÁXIMO MAYOR.

Con la medición de ángulos realizada sobre las líneas de interés en el paso anterior, seleccionamos aquella que tenga un valor más alto, la cual será la que gire "más a la izquierda" y por lo tanto la siguiente en la conformación del polígono. En el código fuente adjunto se puede ver que esta operación es realizada con simple un condicional que va evaluando dentro de un bucle qué ángulo es más grande y se va quedando con la mayor magnitud encontrada.

  PASO 6. RECONFIGURAR LA NUEVA LÍNEA BASE Y VUELTA AL PASO 3.

Una vez que tenemos la siguiente línea sobre la que trabajar, cambiamos la situación de la línea base a la geometría del nuevo segmento seleccionado. En este caso ya no tenemos que trabajar para saber cuál será el siguiente vértice de interés, puesto que será el del lado opuesto al último seleccionado (si seleccionáramos sobre el mismo vértice que en el paso anterior, entraríamos en un bucle sin fin).

Reconfiguramos la situación con respecto a la nueva línea base, pues, y volvemos a repetir desde el paso 3. De esta forma, seleccionaremos el siguiente segmento que define el polígono.

  PASO 7. COMPROBAR SI EL POLÍGONO ESTÁ CERRADO.

En el momento en que las coordenadas finales de uno de los segmentos seleccionados para el polígono coincidan con las coordenadas de inicio de la primera línea base que tomamos (el segmento más cercano al punto del usuario), salimos del bucle pues tenemos ya toda la geometría del polígono.

Si por el contrario llega un momento en el que no hay más líneas que elegir y las coordenadas finales del último segmento no coinciden con las coordenadas de inicio, entonces significa que el polígono está abierto.

  PASO 8. RECONSTRUCCIÓN Y OPERACIÓN CON LA GEOMETRÍA DEL POLÍGONO.

Si disponemos de un polígono ya cerrado, podemos realizar operaciones con el mismo, tales como la determinación de su área, perímetro, el cálculo de su centroide, su sombreado de color u otros procedimientos básicos con polígonos. En el ejemplo de código fuente que se adjunta con este artículo recogemos la geometría del polígono en una nueva matriz y procedemos a calcular el área y el perímetro de una forma muy sencilla.

  MEJORAS DEL ALGORITMO.

Las funcionalidades del algoritmo propuesto podrían ser incrementadas mediante la integración de lógica adicional que contemplara los siguientes aspectos:

  • Introducción de una tolerancia de incertidumbre en el case de los vértices (nodos) o Error Circular Probable (Circular Error Probable, CEP).
  • Detección de polígonos isla.
  • Detección de intersecciones.
  • Operación con polilíneas y no sólo con segmentos de línea.
  • Introducción de una estrategia de indexación espacial para pre-seleccionar los segmentos sobre los que calcular la distancia mínima al punto base del usuario, especialmente cuando se opere con grandes cantidades de líneas.



¿Esta información te ha sido útil?
Ayúdanos a mantener la página con una donación:



© GabrielOrtiz.com