Triangulación espacial de Delaunay
El problema de construir una red de triángulos que no se superponen es uno de los básicos en geometría computacional y se usa ampliamente en gráficos por computadora y sistemas de información geográfica para modelar superficies y resolver problemas espaciales.
El problema de construir una red de triángulos no superpuestos se planteó por primera vez en 1934 en el trabajo del matemático soviético B. N. Delone, quien formuló las condiciones correspondientes.
En matemáticas, la tarea de construir una triangulación a partir de puntos dados es la tarea de conectarlos en pares mediante segmentos que no se cruzan de modo que se forme una red de triángulos. Sus elementos principales son (Fig. 5.3): nodos (vértices de triángulos), aristas (lados) y caras (los propios triángulos). La triangulación construida puede ser convexa (si es un polígono mínimo que cubre el área de modelado), no convexa (si la triangulación no es convexa) y óptima (si la suma de las longitudes de todas las aristas es mínima).
Una red de tales triángulos se denomina triangulación de Delaunay si satisface ciertas condiciones:
Ninguno de los puntos originales cae dentro del círculo circunscrito alrededor de algún triángulo (figura 5.3);
La triangulación es convexa y satisface la condición de Delaunay formulada anteriormente;
La suma de los ángulos mínimos de todos los triángulos es el máximo de todas las triangulaciones posibles;
La suma de los radios de los círculos descritos alrededor de los triángulos es mínima entre todas las triangulaciones posibles.
El primero de los criterios anteriores para construir una triangulación de Delaunay, llamado circular, es uno de los principales y se verifica para cualquier par de triángulos con caras comunes. La interpretación matemática del criterio se desprende de la Fig. 5.3:
(5.2)
Hay muchas formas de construir la triangulación de Delaunay, que es una de las más populares en Últimamente Métodos para construir una malla de triangulación. Se utiliza en muchos sistemas GIS para construir modelos de relieve.
Cuando se aplica al espacio bidimensional, se formula de la siguiente manera: un sistema de triángulos interconectados que no se superponen tiene el perímetro más pequeño si ninguno de los vértices cae dentro de alguno de los círculos descritos alrededor de los triángulos formados (Fig. 5.4).
Arroz. 5.4. Triangulación de Delaunay
Esto significa que los triángulos resultantes con tal triangulación son lo más cercanos posible a los equiláteros, y cada uno de los lados de los triángulos resultantes del vértice opuesto es visible en el ángulo máximo desde todos los puntos posibles del semiplano correspondiente. Ésta es exactamente la triangulación óptima a lo largo de cuyos bordes se suele realizar la interpolación lineal para construir isolíneas.
Muchos algoritmos para construir la triangulación de Delaunay utilizan el siguiente teorema.
Teorema 1. La triangulación de Delaunay se puede obtener a partir de cualquier otra triangulación utilizando el mismo sistema de puntos reorganizando secuencialmente pares de triángulos adyacentes ABC y BCD que no satisfacen la condición de Delaunay en pares de triángulos ABD y ACD (figura 5.5).
Arroz. 5.5.. Reconstrucción de triángulos que no satisfacen la condición de Delaunay
Esta operación de reconstrucción a menudo se denomina volteo. Este teorema permite construir la triangulación de Delaunay de forma secuencial, primero construyendo alguna triangulación y luego mejorándola sucesivamente en el sentido de la condición de Delaunay. Al verificar la condición de Delaunay para pares de triángulos adyacentes, puede usar la definición directamente, pero a veces se usan otros métodos basados en las condiciones enumeradas anteriormente.
En estas condiciones aparece la característica total de toda la triangulación (suma de ángulos mínimos o suma de radios), optimizando cuál se puede obtener una triangulación de Delaunay.
Como se mencionó anteriormente, uno de operaciones críticas Lo que se realiza al construir una triangulación es verificar la condición de Delaunay para pares de triángulos dados. Según la definición de triangulación de Delaunay y las condiciones correspondientes, en la práctica se suelen utilizar varios métodos de verificación:
– comprobar la ecuación circunscrita;
– comprobar con un círculo circunscrito previamente calculado;
– comprobar la suma de los ángulos opuestos;
– control modificado de la suma de ángulos opuestos.
Muchos sistemas realizan la prueba con un círculo circunstante precalculado. La idea principal del algoritmo de verificación mediante círculos precalculados es precalcular para cada triángulo construido el centro y el radio del círculo descrito a su alrededor, después de lo cual la verificación de la condición de Delaunay se reducirá a calcular la distancia al centro. de este círculo y comparando el resultado con el radio. El centro y el radio r del círculo descrito alrededor se pueden encontrar como , , , r 2 = (b 2 + c 2 - 4аd)/4а 2, donde los valores a B C D determinado por fórmulas (5.3)
(5.3)
Otra entrada para la ecuación de este círculo es:
(5.5.)
(5.6)
Entonces la condición de Delaunay para se cumplirá sólo cuando para cualquier otro punto de triangulación sea:
(x 0 – x C) 2 + (y 0 – y C) 2 ≥ r 2 . (5.7)
Actualmente, existen muchos algoritmos para construir la triangulación de Delaunay. Muchos de los algoritmos conocidos utilizan la definición de triangulación de Delaunay como característica de triangulación secundaria. Por lo tanto, se observan las siguientes debilidades en dichos algoritmos:
– los algoritmos utilizan funciones trigonométricas calculadas constantemente, lo que ralentiza drásticamente el proceso;
– al estudiar la relación entre puntos y el segmento base, surgen ángulos muy pequeños, y al usar funciones trigonométricas Existe un peligro constante de desaparición del orden y división por 0 debido a la precisión limitada de las representaciones de datos en una computadora; esta situación requiere un procesamiento adicional constante.
Los productos de software más conocidos construyen la triangulación de Delaunay utilizando el teorema de la bola vacía como principio principal para construir triángulos. El algoritmo se ve así:
– todo el conjunto de puntos se divide en triángulos, es decir se crean combinaciones de tres puntos;
– para cada combinación se encuentran el círculo circunscrito y las coordenadas de su centro;
– si no queda un solo punto dentro del círculo de la combinación actual, entonces esta combinación es un triángulo, parte de la triangulación de Delaunay.
Las ventajas de este algoritmo incluyen:
– falta de uso de funciones trigonométricas, lo que no ralentiza el proceso de construcción;
– construcción directa de la triangulación de Delaunay, sin construcciones previas;
– simplicidad de todos los cálculos y transformaciones;
– Como resultado, la cuadrícula de triangulación está representada por muchos triángulos, en lugar de líneas individuales.
La triangulación construida de esta manera es la base geométrica para construir isolíneas.
Los algoritmos para construir la triangulación de Delaunay se pueden dividir en varios grupos, que se diferencian en la estructura de los datos de entrada utilizados, el volumen de operaciones computacionales, las premisas iniciales, etc. Consideremos algunos de ellos.
Los algoritmos de fusión implican dividir un conjunto de puntos fuente en subconjuntos, construir una triangulación en cada uno de ellos y luego combinarlos en una sola red. La esencia de uno de estos algoritmos se reduce a lo siguiente.
Un conjunto de puntos iniciales se divide mediante líneas verticales en dos o más partes, después de lo cual cada uno de ellos se divide mediante líneas horizontales y verticales en partes aproximadamente iguales. Como resultado, toda el área de los puntos iniciales se divide en primitivas de tres o cuatro puntos (Fig. 2.4), a lo largo de los cuales se construyen uno o dos triángulos.
La fusión de estos triángulos en una sola red se realiza mediante la construcción de dos líneas de base. (P 0 P 1 y P 2 P 3, arroz. 5.7.a), dibujando círculos de radio variable centrados en la bisectriz perpendicular a la línea base (Fig. 5.7, b), buscando un nodo que caiga sobre el círculo (punto A, arroz. 5.7. c) y construcción de un nuevo triángulo (P 0 P 1 A). En este caso, puede que sea necesario eliminar un triángulo existente (por ejemplo, P 0 AB).
Los algoritmos iterativos se basan en la idea de agregar puntos secuencialmente a una triangulación parcialmente construida con su mejora y reconstrucción simultáneas de acuerdo con los criterios de Delaunay. EN vista general Implican varios pasos y se reducen a construir un triángulo en los primeros tres. puntos de partida y explorar varias opciones para colocar el siguiente punto. En particular, se consideran opciones para que caiga fuera del límite del área de modelado, en un nodo o borde existente, dentro de un triángulo construido, etc. Cada una de estas opciones implica realizar una determinada operación: dividir un borde en dos, las caras en tres, etc.; después de lo cual se verifica que los triángulos resultantes cumplan con la condición de Delaunay y las reconstrucciones necesarias.
Los algoritmos de dos pasos implican primero la construcción de alguna triangulación, ignorando las condiciones de Delaunay, y luego su reconstrucción de acuerdo con estas condiciones. Un ejemplo de la aplicación del algoritmo se muestra en la Fig. 5.8.
Para acercar el modelo en relieve creado al real, se introducen elementos adicionales en él para garantizar que se tengan en cuenta y se muestren sus elementos estructurales lineales y areales. Dichos elementos adicionales son líneas estructurales ampliamente utilizadas en topografía que definen el “esqueleto en relieve”: cuencas hidrográficas, vaguadas, crestas, acantilados, cornisas, lagos, barrancos, líneas costeras, límites de estructuras artificiales, etc., cuya totalidad crea una especie de marco para la triangulación de Delaunay. Estas líneas estructurales se introducen en la triangulación como aristas de triángulos, con lo que se consigue modelar elementos reales en relieve en el contexto de los desniveles generales de la superficie terrestre. Dichos bordes se denominan estructurales (fijos, no reconfigurables), no se cruzan con los bordes de otros triángulos y no cambian posteriormente.
El problema de construir un modelo de superficie teniendo en cuenta las líneas de ruptura se denomina triangulación de Delaunay restringida si se satisfacen las condiciones de Delaunay para cualquier par de triángulos adyacentes que no estén separados por líneas de ruptura. Los investigadores creen que la forma más eficaz es construir dicha triangulación utilizando algoritmos iterativos.
En la figura 1 se muestra un fragmento de la triangulación de Delaunay con elementos adicionales incluidos en ella. 5.9, donde a la derecha se muestran nodos, aristas, aristas y líneas estructurales, y a la izquierda las líneas estructurales del terreno (líneas de costa, bordes de barrancos, etc.) y puntos con marcas conocidas.
Los algoritmos para construir la triangulación de Delaunay se implementan con una representación real o entera de las coordenadas de los nodos, lo que puede aumentar significativamente la velocidad y precisión del procesamiento, pero genera problemas de búsqueda y exclusión de nodos coincidentes.
El modelo TIN se edita fácilmente moviendo nodos, insertando nuevos, eliminando los existentes, cambiando la posición de uno o varios bordes, introduciendo nuevas líneas estructurales, etc. Dichos cambios siempre afectan a un pequeño grupo de triángulos adyacentes, no requieren reconstruir el toda la red y se realizan online, apuntando el cursor al elemento correspondiente.
Acerca de la precisión:
Al colocar piquetes en elementos característicos del relieve (por ejemplo, cuencas hidrográficas y vaguadas), ignoramos los elementos más pequeños en los huecos. Al trazar curvas de nivel1 a lo largo de dichos bordes de triángulos, se produce un error que depende del grado de desnivel del terreno y del ángulo de inclinación del terreno. Por ejemplo, el error promedio al medir el relieve no debe exceder 1/3 de la sección transversal del relieve en ángulos de inclinación de la superficie de 2 a 10 grados. Se puede calcular que con una sección de relieve de 0,5 m, el valor máximo del desnivel perdido (es decir, la desviación de la superficie del suelo de la línea recta que pasa por los piquetes adyacentes) no debe exceder (0,5/3)*cos10° = 0,16 m.
Para determinar con precisión el volumen de suelo transportado, también es importante el área ocupada por la parte del relieve no contabilizada. Digamos que en un cuadrado de 20x20 m entre dos pares de piquetes hay una convexidad cilíndrica con una altura máxima de 0,15 m, es fácil calcular que no tenerlo en cuenta a la hora de representar esta superficie con sólo dos triángulos conducirá a una error de aproximadamente 40 m3. No tanto, pero para una parcela de 1 hectárea, ubicada en una colina o en la parte superior (generalmente convexa) de la pendiente, se obtienen 40 * 25 = 1000 m3 de exceso de suelo. Si toma piquetes con el doble de frecuencia (es decir, cada 10 m), el error se cuadriplicará y ascenderá a 250 m3 por hectárea. Este factor se puede tener en cuenta de antemano, ya que las formas positivas de relieve plano suelen tener una forma convexa, mientras que las formas negativas tienen una forma cóncava. Si el área a inspeccionar tiene datos aproximados sobre el relieve, entonces el radio de curvatura de la superficie y la densidad requerida de piquetes se pueden calcular fácilmente a partir de los valores de las curvas de nivel o de las elevaciones individuales.
Definiciones y propiedades básicas.
Una triangulación es un gráfico plano cuyas regiones interiores son todas triángulos.
Propiedades:
· La triangulación de Delaunay corresponde uno a uno al diagrama de Voronoi para el mismo conjunto de puntos.
· Como consecuencia: si no hay cuatro puntos en el mismo círculo, la triangulación de Delaunay es única.
· La triangulación de Delaunay maximiza el ángulo mínimo entre todos los ángulos de todos los triángulos construidos, evitando así triángulos "delgados".
· La triangulación de Delaunay maximiza la suma de los radios de las esferas inscritas.
· La triangulación de Delaunay minimiza el funcional discreto de Dirichlet.
· La triangulación de Delaunay minimiza el radio máximo de la esfera ambiental mínima.
· La triangulación de Delaunay en el plano tiene la suma mínima de los radios de los círculos descritos alrededor de los triángulos entre todas las triangulaciones posibles.
Figura 1. Triangulación.
Una triangulación convexa es una triangulación en la que el polígono mínimo que encierra todos los triángulos es convexo. Una triangulación que no es convexa se llama no convexa.
El problema de construir una triangulación a partir de un conjunto dado de puntos bidimensionales se llama problema de conexión. puntos dados segmentos que no se cruzan para que se forme una triangulación.
Se dice que una triangulación satisface la condición de Delaunay si ninguno de los puntos de triangulación dados cae dentro del círculo circunscrito alrededor de cualquier triángulo construido.
Una triangulación se denomina triangulación de Delaunay si es convexa y satisface la condición de Delaunay.
Figura 2. Triangulación de Delaunay.
Método de la bola vacía de Delaunay. Construcción en el caso general.
Utilicemos una bola vacía, que moveremos cambiando su tamaño para que pueda tocar los puntos del sistema (A), pero quede siempre vacía.
Entonces, ubiquemos en el sistema de puntos (A) bola vacia Delaunay. Esto siempre es posible si eliges una bola lo suficientemente pequeña. Empecemos a aumentar su radio, dejando el centro de la bola en su lugar. En algún punto, la superficie de la pelota se encontrará con algún punto i del sistema (A). Esto definitivamente sucederá, porque no hay vacíos infinitamente grandes en nuestro sistema. Continuaremos aumentando el radio de la bola vacía para que el punto i permanezca en su superficie. Para ello tendrás que mover el centro de la bola desde el punto i. Tarde o temprano la pelota alcanzará con su superficie otro punto del sistema (A).
Fig. 3
Los simples Delaunay llenan el espacio sin espacios ni superposiciones.
La esfera descrita de cualquier simplex no contiene otros puntos del sistema dentro de sí misma.
Sea este el punto j. Sigamos aumentando el radio de nuestra bola, manteniendo ambos puntos en su superficie. A medida que la bola aumenta, llegará a un tercer punto del sistema, el punto k. En el caso bidimensional, nuestro “círculo vacío” quedará fijo en este momento, es decir Será imposible aumentar aún más su radio mientras se mantiene el círculo vacío. Al mismo tiempo, identificamos una configuración bidimensional elemental de tres puntos (i, j, k), que definen un determinado triángulo, cuya peculiaridad es que no hay otros puntos del sistema (A) dentro de su circunferencia circunscrita. En el espacio tridimensional, una pelota no está definida por tres puntos. Sigamos aumentando su radio, manteniendo los tres puntos que se encuentran en su superficie. Esto será posible hasta que la superficie de la bola se encuentre con el cuarto punto l del sistema. Después de esto, el movimiento y crecimiento de la bola vacía será imposible. Los cuatro puntos encontrados (i,j,k,l) definen los vértices del tetraedro, el cual se caracteriza porque dentro de su esfera circunscrita no se encuentran otros puntos del sistema (A). Este tetraedro se denomina simplex de Delaunay.
En matemáticas, un simplex es la figura más simple en un espacio de una dimensión determinada: un tetraedro, en un espacio tridimensional; triángulo - en dos dimensiones. Un conjunto arbitrario de tres (cuatro) puntos del sistema que no se encuentran en el mismo plano siempre define un determinado simplex. Sin embargo, será un simplex de Delaunay sólo si la esfera descrita está vacía. En otras palabras, los simples de Delaunay están determinados por una elección especial de tripletes (cuádruplos) de puntos en el sistema (A).
Hemos construido un simplex de Delaunay, pero colocando la bola vacía en diferentes lugares y repitiendo el mismo procedimiento, podemos definir otros. Se afirma que el conjunto de todos los simples de Delaunay del sistema (A) llena el espacio sin superposiciones ni espacios, es decir implementa la división del espacio, pero esta vez en tetraedros. Esta partición se llama Azulejos de Delaunay(Fig. 3).
Aplicación de la triangulación de Delaunay
Las triangulaciones de Delaunay se utilizan a menudo en el espacio euclidiano. Se garantiza que el árbol de expansión mínimo euclidiano se encuentra en la triangulación de Delaunay, por lo que algunos algoritmos utilizan la triangulación. Además, mediante la triangulación de Delaunay, se resuelve aproximadamente el problema del viajante euclidiano.
En la interpolación 2D, la triangulación de Delaunay divide el plano en los triángulos más gruesos posibles, evitando ángulos demasiado agudos y obtusos. Usando estos triángulos, puedes construir, por ejemplo, una interpolación bilineal.
Otro problema frecuente en geoinformática es la construcción de pendientes. Aquí es necesario determinar las direcciones dominantes de las pendientes por dirección cardinal y dividir la superficie en regiones en las que domina una determinada dirección. Dado que determinar la exposición no tiene sentido para áreas horizontales de la superficie, las áreas horizontales o con una ligera pendiente se asignan a una región separada, por ejemplo<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.
Fig.4.
El problema de calcular la exposición de las pendientes se suele utilizar para analizar la iluminación de la Tierra. En este sentido, a menudo es necesario tener en cuenta además la posición actual del Sol, es decir, la exposición se calcula como la dirección entre la normal al triángulo y la dirección al Sol.
Así, cada triángulo de triangulación se puede clasificar según el principio de pertenencia a una región particular. Después de esto, sólo necesitas llamar al algoritmo de selección de región.
La triangulación es la aproximación de la superficie de un objeto modelado mediante placas triangulares espaciadas de él a una distancia que no exceda un cierto valor especificado 6. Todas las placas triangulares deben estar unidas. Sus cimas se encuentran en la superficie. Es más fácil trabajar con un conjunto de placas triangulares que con una superficie general. A las placas triangulares las llamaremos triángulos. Para un triángulo, se calcula rápidamente la distancia a un punto determinado o al punto de intersección con una línea determinada en el espacio. La triangulación de las caras se realiza para la percepción visual del modelo geométrico, por lo que los lados de los triángulos se seleccionan de manera que el ojo no pueda notar las torceduras.
Al representar objetos geométricos mediante triángulos en planos paramétricos de superficies, se debe construir una triangulación espacial de las caras del cuerpo calculando una serie de puntos en el espacio y una serie de normales a las caras del cuerpo en estos puntos utilizando una serie de puntos bidimensionales Para visualizar rápidamente los cuerpos, sus caras se aproximan mediante placas triangulares construidas sobre puntos normales. Se requieren puntos normales para determinar el comportamiento de los rayos de luz que interactúan con las caras del cuerpo. Los dibujos tonales de los capítulos anteriores y de este capítulo se realizan mediante triangulación.
Como resultado de la triangulación de superficies, queremos tener una matriz de puntos bidimensionales en un plano paramétrico y una matriz de tripletes de números enteros, que son los números de puntos en la primera matriz mencionada. Así, cada triángulo estará representado por tres números de sus vértices en la matriz de parámetros. Para cada punto bidimensional del dominio paramétrico, se puede calcular un punto espacial en la superficie y la superficie normal en él. Los puntos espaciales y las normales se pueden almacenar en matrices similares a una matriz de puntos 2D.
Veamos algunos métodos de triangulación. Para superficies planas, existen métodos de triangulación rentables en los que se construyen triángulos en los puntos límite de la superficie y no es necesario buscar puntos dentro de la región paramétrica.
Triangulación de Delaunay.
Consideremos alguna zona del avión. Llamaremos convexa a un área si, al movernos a lo largo de su límite, tenemos que girar solo en una dirección (solo hacia la izquierda o solo hacia la derecha). El algoritmo de Delaunay se puede utilizar para triangular regiones planas convexas. No podremos aplicar este algoritmo directamente para triangular superficies de forma libre, pero usaremos su método para construir triángulos.
Arroz. 9.7.1. Región convexa con puntos dados dentro.
Sea una región bidimensional convexa delimitada por una línea discontinua cerrada y un conjunto de puntos dentro de esta región (Fig. 9.7.1).
Se requiere dividir el área especificada en triángulos, cuyos vértices son los puntos dados dentro del área y los vértices de la línea discontinua que la limita. Los triángulos no deben superponerse entre sí y sus lados sólo pueden cruzarse en los vértices.
Se pueden construir varios conjuntos diferentes de triángulos para llenar un área específica. En todos los casos, el número de triángulos es igual a , donde K es el número de vértices de la polilínea delimitadora, I es el número de puntos dados dentro del área.
Arroz. 9.7.2. Seleccionando el tercer punto del algoritmo de Delaunay
Una triangulación de una región será una triangulación de Delaunay si no hay vértices de otros triángulos dentro del círculo descrito alrededor de cada triángulo. La triangulación de Delaunay construye triángulos lo más equiangulares posible (no permite la construcción de triángulos excesivamente alargados).
Se le puede llamar equilibrado. Una triangulación de Delaunay será única si no hay cuatro vértices en el mismo círculo.
Consideremos la triangulación de Delaunay. Llamaremos vértices de la triangulación a los vértices de la polilínea que delimita la región y a los puntos dados dentro de la región. A los lados de los triángulos los llamaremos aristas. Entre las aristas, seleccionamos segmentos de la polilínea delimitadora, a las que llamaremos aristas limítrofes. Orientemos todos los bordes del límite de modo que la región convexa quede a la izquierda de cada borde. Sea necesario construir un triángulo cuyo lado sea el borde límite AB, que se muestra en la figura. 9.7.2.
A través de los vértices A, B y cualquier vértice que no esté en la misma recta que ellos, se puede dibujar un círculo. Como tercer vértice del triángulo, elegimos el vértice V, el círculo correspondiente no contiene otros vértices en el mismo lado con respecto al segmento AB en el que se encuentra el punto V. Para un borde límite, en el caso general, uno de esos vértices puede ser encontrado. Lo llamaremos el más cercano. El centro de una circunferencia que pasa por los puntos A, B y V se encuentra en la intersección de las perpendiculares a los puntos medios de los segmentos AB, BV y VA. La posición del centro del círculo estará caracterizada por el parámetro t del segmento MN, perpendicular al borde AB, de igual longitud y que pasa por el centro del borde AB.
Arroz. 9.7.3. Proceso de triangulación de Delaunay
Para todos los vértices que se encuentran a la izquierda del segmento AB, el vértice más cercano tiene el parámetro más pequeño t. La circunferencia correspondiente al vértice más cercano no contiene otros vértices a la izquierda del segmento AB. Sean descritos los vértices A, B y V mediante vectores de radio bidimensionales, respectivamente. Los vectores de radio de los puntos medios de los segmentos AB y BV serán iguales.
El valor del parámetro t de la línea, correspondiente a la posición en ella del centro del círculo que pasa por los puntos A, B y V, es igual a
Para el vértice más cercano a la izquierda del segmento AB, el parámetro t tiene un valor mínimo.
Orientemos todos los bordes límite de modo que el área a triangular quede a la izquierda de cada uno de ellos. Comenzamos a construir triángulos desde cualquier borde límite. Encontremos el vértice más cercano, cuyo círculo correspondiente no contiene otros vértices. Consideremos el vértice más cercano V para la arista límite AB, luego construimos un triángulo ABV y transferimos la arista AB a la categoría de inactivo. Llamaremos aristas y vértices inactivos que no participan en el algoritmo de triangulación. Si no hay ninguna arista BV entre las aristas límite, entonces construimos una nueva arista límite en el segmento VB. Si entre los bordes del límite hay un borde BV, entonces lo transferimos junto con el vértice B a la categoría de inactivo. Si no hay ninguna arista VA entre las aristas límite, entonces construiremos una nueva arista límite en el segmento AV. Si entre los bordes del límite hay un borde VA, entonces lo transferimos junto con el vértice A a la categoría de inactivo. El proceso de triangulación se muestra en la Fig. 9.7.3.
Arroz. 9.7.4. Triangulación de Delaunay
Terminamos la triangulación cuando todos los vértices y aristas quedan inactivos. El resultado de la triangulación de un área determinada se muestra en la Fig. 9.7.4.
Triangulación por método de corrección.
Consideremos la triangulación de una determinada superficie con un dominio rectangular para determinar los parámetros. Dividimos el dominio para definir los parámetros de la superficie en celdas rectangulares con líneas bidimensionales. Estas líneas forman una cuadrícula rectangular. Tomemos las distancias paramétricas entre líneas adyacentes de acuerdo con la fórmula (9.4.7) iguales
Tomemos las distancias paramétricas entre líneas adyacentes de acuerdo con la fórmula (9.4.8) iguales
Al construir diagonales en todas las celdas rectangulares, obtenemos una triangulación de la superficie (obtenemos un conjunto de triángulos que cumple con los requisitos). En la Fig. 9.7.5 muestra la triangulación de la superficie de revolución utilizando el método descrito.
Consideremos la triangulación de una superficie con un límite arbitrario. Construiremos el método de triangulación a partir de la corrección por contornos límite de la triangulación de superficie descrita anteriormente con un área rectangular para determinar los parámetros.
Arroz. 9.7.5. Triangulación de una superficie con dominio rectangular para definir parámetros.
Deje que el límite de la superficie en el dominio de definición de parámetros se describa mediante varios contornos bidimensionales que no se cruzan (2.12.7). Uno de los contornos es externo y contiene los contornos restantes. Para la dirección positiva de cada contorno tomaremos la dirección en la que, al avanzar, el área de definición de la superficie siempre está a la izquierda del contorno, mirando hacia la normal a la superficie. Construyamos polígonos en la dirección positiva de los contornos de los límites del área de definición de la superficie. Para construir polígonos de límites, debe caminar a lo largo de los contornos de los límites de la superficie con un paso variable y completar una matriz de puntos bidimensionales, cuyas coordenadas son los parámetros de la superficie. Construiremos un polígono a partir de puntos en un plano paramétrico, pero el paso al pasar de un punto a otro estará determinado por la geometría espacial, es decir, por la condición de que la desviación del arco curvo entre puntos adyacentes no sea más que un valor dado. valor. Calculamos los pasos paramétricos para construir un polígono para la curva de contorno del límite de la superficie usando la fórmula (9.4.4).
Cada polígono consta de un conjunto ordenado de puntos bidimensionales. Cada sección de un polígono puede considerarse como un segmento de línea recta bidimensional construido sobre dos puntos adyacentes. Usaremos áreas como aristas límite y los puntos de los polígonos en los que se basan las aristas se usarán como vértices de triangulación. Dado que el área para determinar los parámetros de la superficie se encuentra a la izquierda de los polígonos límite, al construir triángulos para cada borde de triangulación de límites, debe buscar el tercer vértice del triángulo a la izquierda del borde.
Determinemos qué nodos se encuentran dentro de los polígonos límite y cuáles se encuentran en el borde o fuera del área de definición de la superficie. Usando esta información, clasificamos las celdas de la cuadrícula rectangular en dos grupos. El primer grupo incluye celdas que se encuentran completamente dentro del área donde se determinan los parámetros de la superficie (las celdas no deben tocar los polígonos límite). El segundo grupo incluye las celdas restantes (que se encuentran fuera del área de definición de la superficie o intersecadas por polígonos límite).
Arroz. 9.7.6. Triangulación de superficies sin terminar
Dentro de cada celda del primer grupo, usando una diagonal, construiremos dos triángulos. Obtenemos así una triangulación inacabada. En la figura 2 se muestra un ejemplo de construcción de triángulos en celdas del primer grupo para una superficie de revolución limitada por contornos. 9.7.6.
Construiremos bordes límite en los lados no intersecados de las celdas del segundo grupo y los dirigiremos de modo que la celda correspondiente esté a la izquierda del borde. Alrededor de las celdas del primer grupo construiremos una línea discontinua cerrada (posiblemente varias líneas cerradas) de modo que al movernos a lo largo de ella, la parte del área que no está dividida en triángulos quede a la izquierda, cuando se mira hacia la superficie normal. . También usaremos las secciones rectas de esta línea discontinua como bordes límite. Consideraremos que todas las aristas son iguales. Para completar la triangulación, necesitamos construir triángulos entre los bordes del límite. Para cada arista buscaremos un vértice que se encuentre a su izquierda y que pueda usarse para construir un triángulo. Buscaremos un vértice solo entre aquellos vértices que se encuentran en la misma celda que el borde. Para seleccionar un vértice, utilizamos el método de Delaunay descrito anteriormente e ilustrado en la Fig. 9.7.2. Si se encuentra dicho vértice, entonces debe verificar si dos nuevos bordes del triángulo se cruzan con algún borde límite. Deje que se encuentre el vértice V más cercano para la arista límite AB y verifique que los segmentos BV y VA no intersectan otras aristas límite. Luego construiremos el triángulo ABV y transferiremos el borde AB a la categoría inactiva. Si no hay una arista BV entre las aristas del límite, entonces construiremos una nueva arista del límite en el segmento VB, pero si hay una arista BV entre las aristas del límite, entonces la transferiremos junto con el vértice B a la categoría de inactivo. Si no hay una arista VA entre las aristas del límite, entonces construiremos una nueva arista del límite en el segmento AV, pero si hay una arista VA entre las aristas del límite, entonces la transferiremos junto con el vértice A a la categoría de inactivo.
Si un segmento o VA intersecta otros bordes del límite, entonces pasamos a buscar el vértice más cercano para otro borde del límite. La triangulación se completará después de que todos los bordes y vértices se clasifiquen como inactivos.
Arroz. 9.7.7. Triangulación por método de corrección.
En la Fig. 9.7.7 muestra la triangulación de superficies mediante el método de corrección de triángulos en celdas intersecadas por contornos límite. En la Fig. 9.7.8, utilizando la triangulación resultante, se muestra la superficie misma.
Si los polígonos límite y la superficie tienen cierta simetría, entonces la triangulación mediante el método de corrección tendrá una simetría similar.
Triangulación por método de absorción.
Consideremos otro método de triangulación. En términos de velocidad, es inferior a la triangulación de Delaunay y sus modificaciones. Para comenzar el procedimiento de triangulación, es necesario representar el límite de la superficie en forma de polígonos cerrados. Durante el proceso de triangulación, necesitaremos determinar los pasos en función de los parámetros de la superficie. Con una dirección de movimiento conocida, estos pasos están determinados por las fórmulas (9.4.6). Los pasos aproximados para los parámetros de la superficie se pueden encontrar a continuación. Definamos una región en el plano de parámetros alrededor de un cierto punto de tal manera que cualquier segmento espacial de un punto a otro en esta región no esté más allá de un valor dado S de la superficie.
Para hacer esto, calculamos los incrementos permitidos de parámetros a lo largo de las líneas de coordenadas.
¿Dónde están los coeficientes de la primera y segunda forma cuadrática de la superficie en el punto ? Como límite de la región deseada, tomamos una elipse con centro en un punto y semiejes. Esta elipse tiene la ecuación
Si desea encontrar un punto en el plano al lado de un punto en la dirección dada por el ángulo con el eje y, entonces sus parámetros serán
Primero, consideremos un caso más simple cuando el área de los parámetros de la superficie está limitada a un contorno externo. Aproximamos el límite de la superficie mediante un polígono cerrado en el dominio paramétrico. Al construir una triangulación utilizaremos el polígono de trabajo, que en este caso tomaremos como polígono del contorno exterior. Agregaremos los puntos del polígono a la matriz resultante de puntos bidimensionales. Construiremos triángulos desde el borde del área de trabajo, estrechándolo hasta que solo queden tres puntos en el área de trabajo.
Encontremos un vértice en el polígono de trabajo en el que se convierte en la región. Un punto así siempre existe y el ángulo de rotación en él es menor. Denotaremos este punto por O, y sus parámetros por Cerca de este punto construiremos uno o dos triángulos, dependiendo del ángulo de rotación. Si el ángulo es menor, entonces construiremos un triángulo sobre estos tres puntos (Fig. 9.7.9). De lo contrario, construiremos dos triángulos sobre este punto, dos puntos vecinos y uno nuevo (Fig. 9.7.11). El nuevo punto se designa con P. Buscaremos el punto P en la diagonal del paralelogramo B OS P. Si el vértice del paralelogramo se encuentra dentro de la elipse (Fig. 9.7.10), entonces lo tomaremos como punto P. En caso contrario tomaremos como punto P la intersección de la elipse y la diagonal del paralelogramo. En este último caso, no es necesario buscar la intersección de la elipse y el segmento.
Las coordenadas del punto P se determinan a través de las coordenadas de los puntos O BC.
El ángulo del segmento OP con la horizontal está determinado por la igualdad.
(9.7.8)
Estos datos permiten determinar la posición del punto P con respecto a la elipse (9.7.5).
En el caso mostrado en la Fig. 9.7.9, construyamos un triángulo (recuerde los números de sus vértices) y eliminemos el punto O en el área de trabajo. En el caso que se muestra en la Fig. 9.7.11, construiremos dos triángulos y en el área de trabajo reemplazaremos el punto O con el punto P y colocaremos este último en la matriz de puntos resultante. En la Fig. La Figura 9.7.12 muestra el polígono obtenido después de construir dos triángulos y eliminar el punto O. En ambos casos, el punto O se eliminará del polígono de trabajo y el polígono de trabajo se estrechará. Tenga en cuenta que los triángulos se pueden construir sólo cuando el área de trabajo, después de estrecharse, no se cruza consigo misma.
Arroz. 9.7.9. Construcción de un triángulo
Arroz. 9.7.10. Polígono de resultados
Arroz. 9.7.11. Construcción de dos triángulos.
Arroz. 9.7.12. Polígono de resultados
Este tipo de situaciones se muestran en la Fig. 9.7.13. Pueden ocurrir cuando los lados de los triángulos construidos se cruzan con los lados del área de trabajo que no son adyacentes a ellos. Antes de construir un nuevo triángulo como en el caso mostrado en la Fig. 9.7.9, y en el caso mostrado en la Fig. 9.7.11, se debe realizar una verificación para garantizar que el polígono resultante no se interseca consigo mismo.
Además, al determinar la posición del punto P, es importante que esté a una distancia suficiente de otros puntos del área de trabajo y no se acerque a los segmentos que conectan los puntos del área. De lo contrario, pueden surgir dificultades en el futuro a la hora de construir triángulos. Por lo tanto, antes de estrechar el polígono de trabajo, debe verificar si el polígono resultante tiene autointersección. Si es imposible construir un triángulo (triángulos) cerca del punto O, entonces se debe buscar otro punto en el que el polígono se envuelva dentro del contorno más que en otros y realizar en él las acciones descritas.
A continuación, con el área de trabajo modificada realizaremos las mismas acciones que acabamos de describir. Busquemos un punto en el polígono de trabajo en el que gire dentro del área más que en otros puntos, verifiquemos la posibilidad de estrechar el polígono construyendo uno o dos triángulos y estrechemos el polígono.
Arroz. 9.7.13. No puedes construir triángulos en esta esquina.
Continuando con este proceso, ampliaremos el conjunto de puntos bidimensionales y el conjunto de triángulos, y al mismo tiempo estrecharemos el polígono de trabajo, reduciendo el área que cubre y el número de sus puntos. En alguna etapa de estas acciones recibiremos un polígono de trabajo que consta de tres puntos. Construyamos el último triángulo en estos puntos, eliminemos la zona de trabajo y terminemos la triangulación. En el método de triangulación descrito, el área limitada por el área de trabajo se elimina, por así decirlo, cortándole triángulos.
Consideremos el caso general cuando el área de los parámetros de la superficie está limitada por un contorno externo y varios contornos internos que se encuentran completamente dentro del contorno externo. Aproximamos el límite de la superficie mediante polígonos cerrados en el dominio paramétrico. Para cada contorno construiremos nuestro propio polígono. Al igual que ocurre con los contornos, para los polígonos construidos sobre ellos se debe cumplir la regla de su orientación mutua. La orientación de los polígonos interiores debe ser opuesta a la orientación del polígono exterior. Comencemos a construir la triangulación con el polígono de contorno exterior. Pongamos sus puntos en la matriz resultante de puntos bidimensionales y hagamos que el polígono funcione.
Construiremos triángulos de la misma forma que en el caso de una región simplemente conexa. Busquemos el punto O en el área de trabajo, verifiquemos la posibilidad de estrechar el área de trabajo allí y reduzcamos el área. Si hay contornos internos, resulta más difícil comprobar la posibilidad de estrechar el área de trabajo en un punto seleccionado. Además de las comprobaciones descritas para la intersección de los lados de los triángulos con los lados del área de trabajo, es necesario comprobar la intersección de los lados de los triángulos con los lados de todos los polígonos internos.
Comprobemos la posibilidad de construir dos triángulos en el punto O (figura 9.7.11) y encontremos que el nuevo punto P, una vez construido, caerá dentro de uno de los polígonos internos o estará en una proximidad inaceptable a sus segmentos. En este caso, no construiremos el punto P, sino que incluiremos este polígono interno en el polígono de trabajo construyendo los dos triángulos que se muestran en la Fig. 9.7.14.
Para incluir los puntos de uno de los polígonos internos en el polígono de trabajo, encontramos entre los puntos del polígono interno el punto más cercano al punto C (adyacente al punto O) del polígono de trabajo.
Construyamos triángulos en los puntos OCF y CEF y entre los puntos O y C del área de trabajo insertemos los puntos del polígono interno, comenzando desde el punto F y terminando en el punto E. Así, dividiremos el área de trabajo en el segmento OS, dividiremos el polígono interno en el segmento EF y unirlos con los segmentos OF y EU.
Arroz. 9.7.14. Construcción de dos triángulos.
Arroz. 9.7.15. Fusionar polígonos externos e internos
El resultado de la fusión se muestra en la Fig. 9.7.15. Por supuesto, antes de fusionar los polígonos exterior e interior, se deben realizar comprobaciones para garantizar la corrección de esta operación.
A continuación, continuaremos reduciendo el área de trabajo de la forma descrita hasta encontrarnos muy cerca de otra área interna y incluirla en el área de trabajo. Como resultado, todos los polígonos internos se incluirán en el polígono de trabajo, que deberá reducirse a los últimos tres puntos. Como resultado, toda la región conexa múltiple para determinar los parámetros de la superficie estará cubierta con triángulos.
Arroz. 9.7.16. No puedes construir triángulos en esta esquina.
Puede haber situaciones en las que sea imposible construir un solo triángulo en los polígonos dados. En la Fig. 9.7.16 muestra un área limitada por dos polígonos, cada uno de los cuales consta de cuatro segmentos. Para el polígono exterior, no podemos continuar con la triangulación porque el polígono interior está en el camino. En este caso encontraremos dos puntos vecinos B y C del polígono, para los cuales podemos construir un triángulo HRV. El punto P se proyecta en el centro del lado BC y se encuentra a una distancia tal que el nuevo triángulo no corta los polígonos.
Otros métodos de triangulación.
Hay otras formas de triangulación. Por ejemplo, después de construir los polígonos de los contornos externo e interno del área de definición de superficie, se puede elegir una estrategia diferente para construir triángulos. Otra opción es combinar los polígonos exterior e interior en un solo polígono antes de iniciar la triangulación. Puede "dibujar" puntos dentro del área de definición de parámetros utilizando un determinado algoritmo y realizar una triangulación de Delaunay utilizándolos y los puntos de los polígonos de contorno de límite. Hay algoritmos que primero construyen triángulos grandes y luego los dividen en tamaños manejables.
Triangulación corporal.
La triangulación de un cuerpo es un conjunto de triángulos que se obtienen triangulando las superficies de sus caras. La triangulación de superficies individuales se diferencia de la triangulación de caras de cuerpos en que en el último caso, los polígonos límite de caras adyacentes deben ser consistentes (Fig. 9.7.17).
Arroz. 9.7.17. Consistencia del polígono del límite de la cara del cuerpo
Las secciones de polígonos de caras adyacentes que pasan a lo largo de aristas comunes serán consistentes si sus puntos coinciden en el espacio.
Aplicación de la triangulación.
Los triángulos construidos como resultado de la triangulación se utilizan para obtener imágenes tonales. En la Fig. 9.7.18 y 9.7.19 muestran triangulaciones de la cara de un cuerpo laminar, cuya imagen tonal se muestra en la Fig. 6.5.1.
Arroz. 9.7.18. Triangulación de un rostro corporal mediante el método de corrección.
La división del dominio de determinación de parámetros de superficie en triángulos se puede utilizar en las integrales (8.6.2), (8.6.3), (8.6.12), (8.7.17)-(8.7.22) al calcular las características geométricas de los cuerpos. . Durante la integración numérica, el paso paramétrico para las curvas debe calcularse usando la fórmula (8.11.5), y para las superficies, los pasos paramétricos deben calcularse usando las fórmulas (8.11.1) y (8.11.2).
La triangulación para un conjunto finito de puntos S es el problema de triangular el casco convexo CH(S) que encierra todos los puntos del conjunto S. Los segmentos de recta en triangulación no pueden intersecarse, solo pueden encontrarse en puntos comunes que pertenecen al conjunto S. Dado que Los segmentos de recta cierran triángulos, los consideraremos costillas. En la Fig. La Figura 1 muestra dos versiones diferentes de triangulación para el mismo conjunto de puntos (ignoraremos temporalmente los círculos dibujados en estas figuras).
Arroz. 1
Para un conjunto dado de puntos S, podemos ver que todos los puntos del conjunto S se pueden subdividir en puntos límite (aquellos que se encuentran en el límite del casco convexo CH(S), y puntos interiores (aquellos que se encuentran dentro del casco convexo). casco CH(S). También se pueden clasificar las aristas obtenidas como resultado de la triangulación S como costillas de concha Y costillas internas. Los bordes del casco incluyen los bordes ubicados a lo largo del límite del casco convexo CH(S), y los bordes internos incluyen todos los demás bordes que forman una red de triángulos dentro del casco convexo. Tenga en cuenta que cada borde del caparazón conecta dos puntos límite adyacentes, mientras que los bordes internos pueden conectar dos puntos de cualquier tipo. En particular, si un borde interno conecta dos puntos límite, entonces se trata de una cuerda del casco convexo CH(S). Tenga en cuenta también que cada borde de la triangulación es el límite de dos regiones: cada borde interno está entre dos triángulos y cada borde del caparazón está entre un triángulo y un plano infinito.
Cualquier conjunto de puntos, excepto en algunos casos triviales, permite más de un método de triangulación. Pero hay una propiedad notable: cualquier método de triangulación para un conjunto dado determina el mismo número de triángulos, lo que se desprende del teorema:
Un teorema sobre la triangulación de un conjunto de puntos. Supongamos que el conjunto de puntos S contiene n>3 puntos y no todos son colineales. Además, i puntos de ellos son internos (es decir, se encuentran dentro del casco convexo CH(S). Entonces, cualquier método de triangulación del conjunto S dará como resultado exactamente n + i - 2 triángulos.
Para probar el teorema, primero consideramos la triangulación de n-i puntos límite. Dado que todos son vértices de un polígono convexo, dicha triangulación dará como resultado (n - i) - 2 triángulos. (Esto no es difícil de verificar y, además, se puede demostrar que cualquier triangulación arbitrario Un polígono de m lados (convexo o no convexo) contiene m (2 triángulos). Ahora veamos qué pasará con la triangulación al sumar los i puntos internos restantes, uno cada vez. Afirmamos que sumar cada uno de esos puntos aumenta el número de triángulos en dos. Al agregar un punto interno, pueden surgir dos situaciones, como se muestra en la Fig. 2. En primer lugar, el punto puede estar dentro de algún triángulo y luego dicho triángulo se reemplaza por tres nuevos triángulos. En segundo lugar, si un punto coincide con una de las aristas de triangulación, entonces cada uno de los dos triángulos adyacentes a esta arista se reemplaza por dos nuevos triángulos. De ello se deduce que después de sumar todos los i puntos, el número total de triángulos será (n - i - 2) + (2i), o simplemente n + i - 2.
Arroz. 2
En esta sección, presentaremos un algoritmo para generar un tipo especial de triangulación conocida como triangulación de Delaunay. Esta triangulación está bien equilibrada en el sentido de que los triángulos formados tienden a ser equiangulares. Por ejemplo, la triangulación que se muestra en la Fig. 1a puede atribuirse al tipo de triangulación de Delaunay, y en la Fig. La triangulación 1b contiene varios triángulos muy alargados y no puede atribuirse al tipo Delaunay. En la Fig. La Figura 3 muestra un ejemplo de triangulación de Delaunay para un conjunto de una gran cantidad de puntos.
Arroz. 3
Para formar una triangulación de Delaunay, necesitamos varias definiciones nuevas. Un conjunto de puntos se considera circular si existe un círculo en el que se encuentran todos los puntos del conjunto. Tal círculo estará circunscrito por un conjunto dado de puntos. El círculo circunscrito de un triángulo pasa por sus tres vértices (no colineales). Se dice que un círculo estará libre de puntos con respecto a un conjunto dado de puntos S si no hay puntos del conjunto S dentro del círculo, pero, sin embargo, los puntos del conjunto S pueden ubicarse en el círculo que está la mayoría sin puntos.
Una triangulación de un conjunto de puntos S será una triangulación de Delaunay si la circunferencia circunstante de cada triángulo está libre de puntos. En el diagrama de triangulación Fig. La Figura 1a muestra dos círculos que claramente no contienen otros puntos dentro de ellos (puedes dibujar círculos para otros triángulos para asegurarte de que también estén libres de puntos del conjunto). Esta regla no se observa en el diagrama de la Fig. 16 - un punto de otro triángulo cae dentro del círculo dibujado, por lo tanto, esta grangulación no pertenece al tipo Delaunay.
Se pueden hacer dos suposiciones sobre los puntos del conjunto S para simplificar el algoritmo de triangulación. Primero, para que exista triangulación, debemos suponer que el conjunto S contiene al menos tres puntos y que no son colineales. En segundo lugar, para que una triangulación de Delaunay sea única, es necesario que no haya cuatro puntos del conjunto S que se encuentren en el mismo círculo circunstante. Es fácil ver que sin tal suposición la triangulación de Delaunay no será única, porque 4 puntos en un círculo circunscrito nos permiten realizar dos triangulaciones de Delaunay diferentes.
Nuestro algoritmo funciona haciendo crecer continuamente la triangulación actual, un triángulo a la vez. Inicialmente, la triangulación actual consta de un solo borde del caparazón; al final del algoritmo, la triangulación actual se convierte en una triangulación de Delaunay. En cada iteración, el algoritmo busca un nuevo triángulo que se conecte a borde triangulación actual.
La definición del límite depende de siguiente diagrama Clasificación de las aristas de la triangulación de Delaunay con respecto a la triangulación actual. Cada borde puede ser durmiendo, vivo o muerto:
- costillas para dormir: un borde de una triangulación de Delaunay está inactivo si aún no ha sido detectado por el algoritmo;
- costillas vivas: la costilla está viva si se encuentra, pero sólo se conoce un área adyacente;
- costillas muertas: Un borde se considera muerto si se encuentra y se conocen ambas áreas adyacentes.
Inicialmente, el único borde que pertenece al lóbulo I convexo está vivo: un plano ilimitado está adyacente a él y todos los demás bordes están inactivos. A medida que funciona el algoritmo, los bordes pasan de dormidos a vivos y muertos. El límite en cada etapa consta de un conjunto de bordes vivos.
En cada iteración se selecciona cualquiera de las aristas de la frontera y se somete a un procesamiento que consiste en buscar una región desconocida a la que pertenece la arista e, si esta región resulta ser un triángulo f, definido por el puntos finales del borde e y algún tercer vértice v, entonces el borde e queda muerto, ya que ambas áreas adyacentes a él ahora se conocen. Cada uno de los otros dos lados del triángulo t se transfiere al siguiente estado: de dormido a vivo o de vivo a muerto. Aquí se llamará el vértice v conjugado con el borde e. De lo contrario, si la región desconocida resulta ser un plano infinito, entonces el borde e simplemente muere. En este caso, la arista e no tiene un vértice conjugado.
En la Fig. La Figura 4 muestra el funcionamiento del algoritmo, donde la acción ocurre de arriba hacia abajo y la gloria hacia la derecha. El borde en cada etapa está resaltado con una línea gruesa.
El algoritmo se implementa en el programa delaunayTriangulate. Al programa se le proporciona una matriz s de n puntos y devuelve una lista de triángulos que representan la triangulación de Delaunay. La implementación utiliza la clase de lista circular y clases de la sección Estructura de datos geométrica. La clase Diccionario puede ser cualquier diccionario que admita las operaciones requeridas. Por ejemplo, puede anular #define Dictionary RandomizedSearchTree.
Lista
Arroz. 4
Los triángulos que forman una triangulación se escriben en la lista de triángulos. La frontera está representada por un diccionario de fronteras vivas. Cada arista está orientada de modo que su región desconocida (por determinar) se encuentre a la derecha de la arista. La función de comparación edgeCmp se utiliza para buscar en el diccionario. Compara los puntos iniciales de dos aristas; si son iguales, entonces se comparan sus puntos finales:
Int edgeCmp (Borde *a, Borde *b) (si (a->org< b->org) devolver 1; si (a->org > b->org) devuelve 1; si (a->destino< b->destino) devolver -1; si (a->dest > b->dest) devuelve 1; devolver 0; )
¿Cómo cambia el borde de un paso al siguiente y cómo modifica la función updateFrontier el diccionario de borde del borde para reflejar estos cambios? Cuando un nuevo triángulo t se conecta al límite, los estados de los tres lados del triángulo cambian. El borde del triángulo t adyacente al límite cambia de vivo a muerto. La función updateFrontier puede ignorar esta ventaja porque ya debería eliminarse del diccionario cuando se llama a la función removeMin. Cada una de las dos aristas restantes del triángulo t cambia su estado de dormido a vivo, si no han sido registrados previamente en el diccionario, o de vivo a muerto, si la arista ya está en el diccionario. En la Fig. 5 muestra ambos casos. Según la figura, procesamos la arista viva af y, después de descubrir que el punto b es su conjugado, sumamos el triángulo afb a la triangulación actual. Luego buscamos el borde fb en el diccionario y, como aún no está allí y se descubre por primera vez, su estado cambia de dormido a vivo. Para editar el diccionario, rotaremos el borde fb de modo que la región desconocida adyacente a él quede a su derecha y escribiremos este borde en el diccionario. Luego encontraremos el borde ba en el diccionario; dado que está en él, ya está vivo (el área conocida adyacente a él es el triángulo abc). Dado que se acaba de descubrir la región desconocida para él, el triángulo afb, esta arista se elimina del diccionario.
La función updateFrontier edita el diccionario de fronteras, en el que cambia el estado del borde desde el punto a hasta el punto b:
Arroz. 5
Actualización nulaFrontier (Diccionario
La función hullEdge encuentra un borde del casco entre n puntos en la matriz s. Esta función en realidad utiliza el paso de inicialización y la primera iteración del método de envoltura de regalo:
Borde *bordecasco (Punto s, int n) ( int m = 0; for (int i = 1; i< n; i++) if (s[i] < s[m]) m = i; swap(s, s[m]); for (m = 1, i = 2; i < n; i++) { int с = s[i].classify (s, s[m]); if ((c == LEFT) || (C == BETWEEN)) m = i; } return new Edge(s, s[m]); }
La función triángulo simplemente genera y devuelve un polígono para los tres puntos que se le pasan como parámetros:
Polígono *triángulo (Punto &a, Punto &b, Punto &c) ( Polígono *t = nuevo Polígono; t->insertar (a); t->insertar (b); t->insertar (c); devolver t; )
Los modelos GRID son modelos de células regulares.
Dejemos que se introduzca el sistema de coordenadas. 
Y 
Y 
. Conjuntos de usuarios 
y pasos de muestreo 
.
,
- coordenadas físicas del punto.
calculamos 
Y 
,
- cuadrícula de bits.
- valores cuantificados. Real:
- parámetro del algoritmo – número de puntos, 
- peso. Cuanto más cerca esté el punto, mayor será el peso.
- grado de distancia (1 o 2).
Factor de normalización: 
Cómo 
más cerca de 1, más puntos con pesos más altos se tienen en cuenta.
Este es el método IDW: largo, para cada t es necesario encontrar vecinos. El conjunto de vecinos se puede encontrar de manera eficiente: el más cercano. Cada punto produce una “clavija” de cierta altura. Mucho depende de la irregularidad al fijar el punto, para ello toman 
o 
aquellos. dividido en sectores y puntos de construcción en las proximidades.
Ventaja– simplicidad
Defecto:
------Boleto 14. Modelo hojalata. Algoritmos de triangulación de Delaunay------
1) Triangulación (estaño).
Triangulación– construcción de una función en forma de un conjunto de funciones lineales por partes
Triangulación– interpolación dentro de una región convexa.
Triangulación– un gráfico plano, cuyos bordes internos son todos triángulos; una forma de representar el espacio en forma de triángulos adyacentes entre sí sin superposición. La triangulación se construye sobre un conjunto de puntos de varias maneras.
Se necesita un algoritmo para construir una triangulación óptima.
Un avión que pasa por 3 puntos.
1) Encuentra un triángulo que 
;
2)
- construir una ecuación del plano.
Para verificar si los puntos están dentro del triángulo o no, debes sustituir el valor en la ecuación de las líneas: los bordes del triángulo. Si las 3 ecuaciones > 0, entonces adentro.
Estructura de presentación:
Cada triangulación contiene el mismo número de triángulos.
, Dónde 
– número de puntos internos, 
- cantidad de puntos.
Triangulación codiciosa.
Conectamos todos los puntos con aristas, seleccionamos el mínimo y los sumamos a la triangulación. A continuación tomamos el siguiente mínimo que no se cruza con los anteriores, etc. El resultado es una triangulación codiciosa.
Triangulación de Delaunay.
El interior de un círculo circunscrito alrededor de cualquier triángulo no incluye las puntas de otros triángulos. Está construido de la única manera.
Un giro es una transferencia de aristas. Permite pasar de la triangulación convencional a la triangulación de Delaunay. Para comprobar si un punto pertenece a un círculo: sustituir si< R, то внутри.
Condición de Delaunay.
Ecuación de una circunferencia que pasa por tres puntos:
Si es menor que cero, entonces externo; en caso contrario, interno.
– Estado de Delaunay.
Algoritmo para construir la triangulación de Delaunay:
1) Agregar puntos bajo investigación– un algoritmo iterativo simple:
hay un conjunto 
añadir al triángulo, se lleva a cabo la construcción. 
división del triángulo 
reconstrucción. En la etapa cero, agregamos 3-4 puntos ficticios, que obviamente cubren nuestro sobre, todos los puntos dentro. Luego lanzamos el punto, miramos en qué triángulo golpea, lo dividimos en 3, para cada triángulo verificamos la condición de Delaunay y realizamos una transferencia invertida de aristas. El número medio de cambios de carril es de tres.
Complejidad teórica 
2) Métodos de aceleración. Basado en puntos estadísticamente dependientes. El triángulo semilla es el triángulo en el que cayó el punto anterior. Luego conectamos dos puntos: el anterior y el nuevo.
Pasamos del primer punto a otro.
