|
Palabras
clave: Malla triangular, triangulación de Delaunay, polígonos
de Voronoi, interpolante, malla rectangular, modelo de secciones, modelo
de =strings=.
Resumen
La topografía, como otras ciencias y técnicas, ha experimentado
en los últimos años una evolución hacia la utilización
de los sistemas informáticos y la electrónica. Solamente
es necesario recordar la gran proliferación de receptores de GPS
y progresiva incorporación de esta tecnología en los trabajos
topográficos de hoy en día. Por otra parte, la versatilidad
y productividad que supone la utilización de las estaciones totales
y los instrumentos topográficos basados en la electrónica,
así como su conexión con los sistemas gráficos, hacen
que, cada vez más, los profesionales de la topografía dispongan
de sistemas dedicados exclusivamente a la generación de modelos
digitales del terreno.
Es por ello por lo que conviene conocer, al menos de forma somera, las
características de estos programas y su fundamento teórico,
para poder juzgar en qué situaciones será conveniente utilizar
uno u otro de los posibles sistemas.
El presente artículo analiza las características de los
modeladores digitales del terreno habitualmente utilizados, desde el punto
de vista de su fundamento teórico, indicando las ventajas y los
inconvenientes que presentan cada uno de ellos.
Introducción
Un modelador digital del terreno es un simulador matemático de
la representación física del terreno, en definitiva es lo
que en otras ramas de la ciencia y la técnica se conoce con el
nombre de >modelo matemático=. Básicamente, consiste
en utilizar una metodología y un algoritmo matemático que
permita realizar las dos funciones principales:
1º Calcular la cota en cualquier punto del terreno.
2º Generar las curvas de nivel.
El resto de funcionalidades, que a menudo aportan estos sistemas, están
desarrolladas basándose en las actividades indicadas anteriormente.
Los datos de partida para que el modelador digital del terreno (MDT) pueda
realizar sus funciones son los puntos del terreno que se hayan levantado
por cualquiera de los métodos topográficos habituales (taquimetría,
fotogramentría, etc.). La calidad de estos datos será fundamental
para conseguir un modelo matemático del terreno aceptable, sirva
como indicación que la distribución de los puntos levantados
deberá ser, en general uniforme y con mayor densidad en aquellas
zonas del terreno donde se puedan producir mayores indeterminaciones.
Los modeladores digitales del terreno se pueden clasificar atendiendo
a la metodología en la que se basan: de malla regular, red irregular
de triángulos, de secciones o de cadenas (>strings=). Atendiendo
a los algoritmos matemáticos de interpolación y extrapolación
se pueden clasificar en: gavitacionales, estadísticos, polinómicos,
Spline, etc.
Considerando la cota de cada punto como un atributo o variable asociada
a la posición en planta de cada uno de ellos, la utilización
de modeladores digitales del terreno para otros fines es algo muy común.
Su versatilidad es tan grande que pueden ser aplicados a la interpolación
de datos meteorológicos, de aforos, de contaminación y como
ya se ha indicado anteriormente, para interpolar cualquier variable de
la que se disponga una serie de mediciones espaciales irregularmente distribuidas.
Clasificación
De acuerdo con la metodología y el algoritmo de interpolación
en la que están basados, se clasifican en:
- Modelos digitales del terreno sobre malla regular o rejilla.
- Algoritmo gravitacional (ponderación inversamente proporcional
al cuadrado de la distancia).
- Algoritmos geoestadísticos (Krigeado): Ordinario, simple o universal,
- Curvatura mínima (Splines).
- Mediante secciones radiales.
- Modelos digitales del terreno sobre red irregular de triángulos.
- Interpolación mediante Splines, B-Splines y NURBS.
- Interpolación mediante polinomios de grado >n=.
- Modelos digitales del terreno basados en curvas de nivel o >strings=.
En la tabla nº
1 se incluye un resumen de las metodologías y algoritmos habitualmente
utilizados.
Definición
de la malla base
Si la malla base es rectangular y regular, para definirla, solo es necesario
indicar la longitud del paso en ambas direcciones. El tamaño del
paso es función de la cantidad de puntos conocidos y de la precisión
deseada. En el caso de malla triangular, el problema es más complejo.
Se trata de generar un conjunto de triángulos cuyos vértices
sean los puntos del terreno que previamente han sido levantados, es lo
que se conoce como triangulación de una nube de puntos en el espacio
distribuidos arbitrariamente.
La solución al problema planteado se puede abordar con diversos
algoritmos, de los que el más conocido es el de Dirichlet-Delaunay,
figura n1 1, consistente en subdividir un dominio dado en un conjunto
de polígonos convexos. Dado un conjunto de puntos P1, Y, Pn, se
toman dos puntos Pi y Pj pertenecientes al mismo, la mediatriz Mij del
segmento PiPj divide el plano en dos semiplanos Vi y Vj, tales que los
puntos del semiplano Vi son más cercanos a Pi que a Pj, mientras
que los puntos del semiplano Vj son más cercanos a Pj que a Pi.
Considerando más de dos puntos, el concepto expuesto anteriormente
se puede generalizar, de tal forma que la porción del plano Vk
será la constituida por todos los puntos del plano más cercanos
a Pk que a cualquier otro punto del conjunto inicial. A esta partición
del plano en n regiones se le conoce como teselación de Dirichlet
y los polígonos que delimitan cada una de las regiones se denominan
polígonos de Voronoi. Este concepto que acaba de ser expuesto para
el plano puede ser aplicado al espacio, sin más que sustituir la
recta mediatriz por el plano medriatriz y el polígono por la superficie
poliédrica.
Uniendo las parejas
de puntos Pi, Pj que comparten un lado de uno de los polígonos
de Voronoi, se obtiene una malla triangular. Las propiedades más
importantes de esta red triangular son:
- La circunferencia circunscrita a un triángulo no contiene ningún
otro punto del conjunto inicial, figura nº 2.
- Dados dos triángulos adyacentes, los cuatro vértices que
los componen forman un cuadrilátero, la diagonal más corta
será la que forme el lado común, es decir que los ángulos
de los triángulos serán máximos, figura nº 2.
Algoritmos interpolantes
De los modelos expuestos anteriormente, a continuación se desarrollan,
esquemáticamente, algunos de los algoritmos que utilizan.
Gravitacional
Consiste en ponderar con mayor peso a los puntos más cercanos al
punto a interpolar, existiendo diferentes variantes según el exponente
de la función interpoladora.
siendo,
n el número de puntos que influyen en la interpolación.
p el exponente de la función. Un buen valor, contrastado por la
experiencia, es p=2.
di la distancia del punto Pi al punto a interpolar.
zi la cota de cada punto que interviene en la interpolación.
Splines, B-splines
y NURBS
Este algoritmo ajusta una curva suave a un conjunto de puntos conocidos,
>curva adaptativa=, obligando a que pase por cada uno de los puntos.
Si la función de interpolación es la >B-spline= racional
no uniforme (NURBS), en inglés >non-uniform rational B-spline=,
su formulación es la siguiente:
donde,
u es un parámetro.
Ni,k es la función base de grado k.
Pi son los puntos de control.
wi son los pesos.
La curva, así
definida, tiene n+1 puntos de control con sus correspondientes pesos,
también n+1, y el grado de la misma es k, necesitándose
n+k+2 nodos. El vector de parámetros es:
U= {u0,Y,u0,u1,Y,u1,un,Y,un}
u0,Y,u0 (k+1) valores
u1,Y,u1 (k+1) valores
...
...
un,Y,un (k+1) valores
es decir, hay n+1
grupos de parámetros que a su vez están formados por k+1
valores, luego su cantidad total es n+k+2.
La función
base Ni,k viene dada por las expresiones:
siendo,
k el grado de la curva.
t el vector de parámetros, cuya estructura es análoga a
la indicada anteriormente para el parámetro u.
ti los nodos.
Polinomios de grado "n"
Se trata de encontrar una función f tal que:
la función
f es de la forma: f=Polinomio(x,y). La interpolación más
sencilla es la correspondiente a un polinomio de primer grado cuya expresión
será:
Si se aumenta el grado
del polinomio, será factible conseguir que, además de ser
continua la función, sean continuas sus derivadas. En el caso particular
de un polinomio de segundo grado, la expresión del interpolante
será:
Geoestadísticos
(Kriging)
El primer paso en el >kriging= ordinario consiste en elaborar el variograma
a partir de la nube inicial de puntos. El variograma consta de dos partes:
una parte experimental y una parte del modelo matemático. Sea z
el valor de la cota a interpolar, el variograma experimental se genera
calculando la varianza (s2) de cada punto del conjunto con respecto a
los demás puntos [9].
Una vez calculadas
la varianzas, se procede a representarlas en relación con las distancias
entre los puntos, figura nº 3.
El variograma teórico
o del modelo, se genera mediante ajuste estadístico y es el que
se utilizará en los cálculos de interpolación y extrapolación
de cotas. El variograma indica que los puntos próximos tienen valores
de las varianzas parecidas, a partir de una cierta separación,
las varianzas dejan de ser parecidas, sin embargo su media sí presenta
una tendencia constante. El variograma teórico se utiliza para
calcular los pesos de ponderación que se usará el proceso.
La ecuación básica es:
donde,
n es el número de puntos de partida.
zi es la cota de cada punto.
wi es el peso asignado a cada uno de ellos.
La expresión [10] es básicamente igual a la [1], utilizada
en los modelos gravitacionales, excepto que en vez de asignar los pesos
en función inversa de la distancia elevada a una cierta potencia,
el >kriging= utiliza el variograma.
Si la suma de los pesos es la unidad, el >krigeado= se denomina ordinario,
si no se impone esta condición el proceso de >krigeado= se denomina
simple. El Universal se refiere a la cualidad de estudiar e imponer la
tendencia de los datos, esto es, el estudio local de la varianza, o lo
que es lo mismo, considerar que el variograma no es estático y
que puede ser adaptado a las variaciones locales que se produzcan.
Características
Cada uno de los modelos expuestos en este artículo tiene ventajas
e inconvenientes a la hora de ser aplicados en un trabajo topográfico
real. En general, los puntos reales del terreno que definen la base de
partida para la generación de los modelos digitales, deberían
formar parte del propio modelo, de tal forma que la cota asignada a un
punto del modelo coincidente con uno real, fuese la misma. Esta característica
solo se consigue en los modelos basados en la red irregular de triángulos.
Sin embargo, a la hora de producir las curvas de nivel, los modelos basados
en la malla rectangular regular, producen unos resultados muy aceptables,
tanto desde el punto de vista de su apariencia como desde el punto de
vista de la velocidad de cálculo.
La calidad de los resultados obtenidos con cualquiera de los modelos depende
fundamentalmente de la calidad de los datos de partida, es decir del conjunto
de puntos tomados realmente. Una mala distribución de los mismos,
o una indeterminación por falta de datos, hace que el resultado
del modelo digital se aparte rápidamente de la morfología
que realmente tiene la zona modelizada
.
Cuando un modelador genera una curva de nivel de forma artificial, posiblemente,
por las razones expuestas anteriormente, se dice que produce artefactos
(>artifacts=). Es raro el trabajo en el que no se produzcan estos fenómenos,
incluso aplicando cualquier algoritmo, sobre todo, en los bordes del dominio
a modelizar. Esta es la razón por la que habitualmente, los modelizadores
disponen de herramientas de edición de datos que ayudan a generar
un modelo digital más real.
Muchos de los algoritmos disponen de parámetros de ajuste que permiten
variar las condiciones de trabajo de la función interpolante, por
ejemplo, en el caso de un algoritmo gravitacional, es posible variar la
influencia de la distancia asignando diversos valores a la potencia de
la misma. Aunque habitualmente se suele ajustar al cuadrado, se puede
cambiar por otras potencias si las circunstancias del problema lo requieren.
En este mismo ejemplo, el número de puntos vecinos que intervienen
en la ponderación del punto a interpolar, también puede
ser variado a través del ajuste del radio de influencia. Puntos
más allá del radio de influencia no intervendrán
en el proceso de interpolación. En las tablas n1 2 y n1 3, se muestran
algunas de las características más importantes de los diferentes
modeladores y algoritmos.
Ejemplos
A continuación
se muestran tres ejemplos de modelización digital del mismo terreno
utilizando diferentes algoritmos matemáticos.
Bibliografía
Barnhill R.E., Gregory.J.A. APolynomial Interpolation to Boundary Data
on Triangles@. Mathematics of Computation, n1 29. 1975.
Clough R.W., Tocher J.L. AFinite element stiffness matrices for analysis
of plate blending@. Proc. Conf. On Matrix Methods in Structural Mechanics,
WPAFB, Ohio, 1965.
Deutsch C.V., Journel A.G. AGSLIB: Geostatistical Software Library and
User=s Guide@. Oxford University Press, New York 1992.
Farin G. ACurves and surfaces for Computer Aided Geometric Design: A practical
guide@. Academic Press, 1990.
Journel A. AConstrained Interpolation and Qualitative Information@. Mathematical
Geology, vol. 18, n1 3, pp 269-286. 1986.
Kanaganathan S., Goldstein N.B.AComparison of four point adding algorithms
for Delaunay type three dimensional mesh generators@. IEEE Transactions
on magnetics, vol 27, n1 3, may 1991.
Lee R.C.T. Fu J.J. AVoronoi Diagrams of Moving Points in the Plane@. International
Journal of Computational Geometry and Applications, 1991.
Martínez Marín R. AGeneración automática de
una malla triangular@. Mapping, noviembre 2000.
Martínez Marín R. AGeneración automática de
curvas de nivel (isolíneas) suavizadas@. Topografía y Cartografía,
abril 2001
Poiker T.K., Fowler J.J., Mark D.M. AThe Triangulated Irregular Network@.
Proceedings of the Digital Terrain Models Symposium St. Louis, Miss.,
pp. 516-540, 1978.
Preparata F.P., Shamos M.I. AComputational Geometry, An Introduction@.
1985.
Shewchuk J.R. ATriangle: Engineering a 2D Quality Mesh Generator and Delaunay
Triangulator@. First Workshop on Applied Computational Geometry (Philadelphia,
Pennsylvania), pag. 124-133. May 1996.
Sloan S.W., Houlsby G.T. AAn implementation of Watson=s Algorithm for
Computing 2-D Delaunay Triangulations@. Advanced Engineering Software,
Vol. 6, N1 4, 1984.
Zienkiewicz O.C. AThe Finite Element Method in Engineering Science@. McGraw-Hill,
New York, 1977.
|
Anónimo