Hogar Cavidad oral Método de la bola vacía de Delaunay. Construcción en el caso general.

Cavidad oral

Método de la bola vacía de Delaunay. Construcción en el caso general.

20 de agosto de 2012 a las 22:41

Optimización del algoritmo para comprobar la condición de Delaunay mediante la ecuación circuncircular y su aplicación.

Te contaré un secreto sobre cómo comprobar rápidamente la condición de Delaunay para dos triángulos.
En realidad, la optimización en sí se describe un poco más abajo (ver "Optimización del algoritmo para verificar la condición de Delaunay a través de la ecuación circuncírculo"), pero te contaré todo en orden.

En mi caso, la triangulación se utiliza en el calco de imágenes para dividir el plano en sectores primitivos (triángulos). Como saben, también se divide en varias etapas: ajuste, identificación de límites, eludir los límites, barrer los contornos. esta en el mismo vista general. Realmente me gustaría parar, creo. etapa dificil: barriendo el avión.

En la entrada

Después de detectar y atravesar los límites, obtuve muchos bucles externos en la salida. Cada contorno conmovedor tiene Colores diferentes. Cada uno de estos circuitos también contiene un número conocido de circuitos internos.
Por lo tanto, desde el punto de vista del "barrido del plano", si consideramos los contornos externos por separado, tenemos un conjunto de puntos, cada uno de los cuales tiene un vecino a la derecha y a la izquierda. Aquellos. todos los puntos están cerrados en una cadena, no hay un solo punto "colgante" y cada cadena contiene al menos 3 puntos (Figura 1).

Foto 1

que hay que hacer

Necesitas cubrir la figura con triángulos.

Buscar

Después de leer el libro, no encontré un solo método (al menos uno) para construir una triangulación de Delaunay que fuera al menos algo adecuado para mi caso. No busqué otros libros. Y esto fue suficiente, puso en orden los pensamientos en mi cabeza. Como resultado, inventó su propia “bicicleta”.

Algoritmo

1) Supongamos, para empezar, que sólo hay una secuencia en la figura que estamos considerando. Luego todo se reduce a tomar triángulos secuencialmente. Tomamos cualquier punto e intentamos construir un triángulo con puntos vecinos. Si no fue posible construir un triángulo (la línea que conecta estos dos puntos se cruza con los ya construidos o la línea pasa en la zona de exclusión (Figura 2), pasamos al siguiente punto, digamos a la derecha. Cuando el siguiente triángulo Se encuentra, lo agregamos a la lista (Figura 3), y eliminamos el punto desde el cual fue construido (Figura 4).

Figura 2

figura 3

Figura 4

Una cosa más: al guardar el siguiente triángulo, es necesario registrar los vértices en el sentido de las agujas del reloj (en el sistema de coordenadas derecho). Esto será útil en el futuro para reducir los recursos informáticos.

2) Repetimos el paso 1 hasta haber barrido todo el avión.

3) Si hay varias secuencias, es decir uno, y en su interior hay uno o más contornos internos (Figura 1). Aquí es necesario considerar cada secuencia por separado. Tomemos otro contorno interno. A partir de uno externo y otro interno realizaremos dos circuitos simples. Para hacer esto, necesita encontrar dos "puertos" de un circuito a otro. Condición para los “puertos”: no deben cruzarse entre sí (ni siquiera sus extremos deben tocarse) y no deben cruzarse con líneas de contorno (Figura 5).

Figura 5

Figura 6
4) A continuación, deberás introducir una a una todas las secuencias internas en las secuencias ya formadas, separadas entre sí (punto 3). Debes fusionarlo con el que contiene el nuevo. Por definición, ninguna secuencia interna se toca ni se cruza con otras (tanto una externa como todas las internas posibles), por lo que todo irá sobre ruedas.
Una vez encontrados los puertos (Figura 6), es fácil construir nuevas secuencias y evitarlas utilizando los puntos 1 y 2 del algoritmo actual (Figura 7).

Figura 7

5) Después de la cuarta etapa tenemos una lista de triángulos (Figura 8). Es como si la tarea ya estuviera completada, pero sólo queda embellecer la imagen: comprobar que se cumple la condición de Delaunay (Figura 9).

Figura 8

Figura 9

6) De cara al futuro, les hablaré del sexto punto. Consiste en recorrer secuencialmente la lista de triángulos obtenidos mediante el paso N°5. Primero, marcamos todos los triángulos como "sucios". En cada ciclo comprobamos la condición de Delaunay para cada triángulo. Si no se cumple la condición, reconstruimos y marcamos los vecinos y el triángulo actual como "sucio". Si se cumple la condición, lo marcamos como limpio. En mi implementación del algoritmo, cada triángulo tiene un vínculo con sus vecinos. En este caso, el punto 6 es el que funciona más rápido.

Más sobre la quinta etapa.

Ahora, hasta donde yo sé, hay dos formas posibles determinar si los triángulos satisfacen la condición de Delaunay o no: 1) Verificar la suma de los ángulos opuestos. Debe ser menor que 180. 2) Calcula el centro del círculo circunscrito y calcula la distancia al cuarto punto. Todo el mundo sabe que la condición de Delaunay se cumple si el punto está fuera del círculo circunscrito.

Potencia de cálculo n.º 1: 10 multiplicar/dividir y 13 sumar/restar.
Poder de cálculo n.° 2: 29 operaciones de multiplicación/división y 24 operaciones de suma/resta.

Desde el punto de vista de la potencia informática, que se calcula, por ejemplo, en el libro, la opción número 1 es más rentable. Lo habría implementado, si no... (Figura 10). Como resultó después de la producción. este método En la “cinta transportadora”, el resultado fue la incertidumbre. Esta es una opción cuando el ángulo A en sí tiene más de 180 grados. Se considera en el libro como uno de los métodos privados individuales. Y con esto desaparece toda su elegancia, transparencia y prestaciones. Y más tarde resultó que el método nº 2 se puede optimizar de forma muy significativa.

Figura 10

Optimización del algoritmo para comprobar la condición de Delaunay mediante la ecuación circuncírculo.

Lo siguiente son las matemáticas puras.

Entonces tenemos:
Verificar la condición para el punto M(X, Y) mediante la ecuación de un círculo que pasa por los puntos A(x1, y1), B(x2, y2), C(x3, y3) se puede escribir como:

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ signo a ≥ 0

Los detalles se pueden encontrar en el excelente libro. (No, no soy el autor)
Entonces, el signo a es el signo de dirección transversal, desde el principio construí los triángulos en el sentido de las agujas del reloj, por lo que se puede omitir (es igual a uno).

A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);

D>=0

Figura 11

Sencillo ¿no?

Según el libro, nuevamente,

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (y1*x2 - x1*y2)<= 0

Tenemos: 15 operaciones de multiplicación/división y 14 operaciones de suma/resta.

Gracias por su atención. Estoy esperando críticas.

Bibliografía

1. Skvortsov A.V. Triangulación de Delaunay y su aplicación. – Tomsk: Editorial Tom. Universidad, 2002. – 128 p. ISBN 5-7511-1501-5

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.

20 de agosto de 2012 a las 22:41

Optimización del algoritmo para comprobar la condición de Delaunay mediante la ecuación circuncircular y su aplicación.

Procesamiento de imágenes ,
Programación

En mi caso, la triangulación se utiliza en el calco de imágenes para dividir el plano en sectores primitivos (triángulos). Como saben, también se divide en varias etapas: ajuste, identificación de límites, eludir los límites, barrer los contornos. Esto es en los términos más generales. Creo que me gustaría detenerme en la etapa más difícil: barrer el avión.

En la entrada

Después de detectar y atravesar los límites, obtuve muchos bucles externos en la salida. Cada contorno conmovedor tiene un color diferente. Cada uno de estos circuitos también contiene un número conocido de circuitos internos.
Por lo tanto, desde el punto de vista del "barrido del plano", si consideramos los contornos externos por separado, tenemos un conjunto de puntos, cada uno de los cuales tiene un vecino a la derecha y a la izquierda. Aquellos. todos los puntos están cerrados en una cadena, no hay un solo punto "colgante" y cada cadena contiene al menos 3 puntos (Figura 1).

Foto 1

que hay que hacer

Necesitas cubrir la figura con triángulos.

Buscar

Algoritmo

Figura 2

figura 3

Figura 4

2) Repetimos el paso 1 hasta haber barrido todo el avión.

Más sobre la quinta etapa.

Ahora, hasta donde yo sé, hay dos formas posibles de determinar si los triángulos satisfacen la condición de Delaunay o no: 1) Verificar la suma de los ángulos opuestos. Debe ser menor que 180. 2) Calcula el centro del círculo circunscrito y calcula la distancia al cuarto punto. Todo el mundo sabe que la condición de Delaunay se cumple si el punto está fuera del círculo circunscrito.

Potencia de cálculo n.º 1: 10 multiplicar/dividir y 13 sumar/restar.
Poder de cálculo n.° 2: 29 operaciones de multiplicación/división y 24 operaciones de suma/resta.

Desde el punto de vista de la potencia informática, que se calcula, por ejemplo, en el libro, la opción número 1 es más rentable. Lo habría implementado, si no... (Figura 10). Al final resultó que, después de poner este método en la “cinta transportadora”, surgió la incertidumbre. Esta es una opción cuando el ángulo A en sí tiene más de 180 grados. Se considera en el libro como uno de los métodos privados individuales. Y con esto desaparece toda su elegancia, transparencia y prestaciones. Y más tarde resultó que el método nº 2 se puede optimizar de forma muy significativa.

Figura 10

Optimización del algoritmo para comprobar la condición de Delaunay mediante la ecuación circuncírculo.

Lo siguiente son las matemáticas puras.

Entonces tenemos:
Verificar la condición para el punto M(X, Y) mediante la ecuación de un círculo que pasa por los puntos A(x1, y1), B(x2, y2), C(x3, y3) se puede escribir como:

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ signo a ≥ 0

A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);

D>=0

Figura 11

Sencillo ¿no?

Según el libro, nuevamente,

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (y1*x2 - x1*y2)<= 0

Tenemos: 15 operaciones de multiplicación/división y 14 operaciones de suma/resta.

Gracias por su atención. Estoy esperando críticas.

Bibliografía

1. Skvortsov A.V. Triangulación de Delaunay y su aplicación. – Tomsk: Editorial Tom. Universidad, 2002. – 128 p. ISBN 5-7511-1501-5

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 es el problema de conectar puntos dados mediante segmentos que no se cruzan de modo 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, coloquemos una bola de Delaunay vacía en el sistema de puntos (A). 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 de la región.

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) para 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 reducir 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. La Figura 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).