Para cuantificación Para la calidad de la triangulación construida definiremos dos tipos de criterios: topológicos y geométricos.

El criterio topológico se basa en vecinos más cercanos puntos del conjunto. EN idealmente un punto tiene 6 vecinos para una región bidimensional y 12 vecinos para una región tridimensional. Obtenemos una estimación topológica usando la fórmula (1), donde - total puntos en un área, - el grado o número de puntos vecinos tejidos con un punto interno.

El criterio geométrico se basa en la diferencia entre los círculos inscritos y circunscritos alrededor del elemento triangular de diseño. Obtenemos una estimación geométrica usando la fórmula (2), donde es el número de triángulos, es el radio del círculo inscrito, es el radio del círculo circunscrito.

Algoritmos para construir triangulación.

Existe una gran cantidad de algoritmos para construir triangulación. Se diferencian en la intensidad del trabajo, la complejidad de la implementación en una computadora y los enfoques de construcción. Se puede encontrar más información sobre algoritmos en el libro de A.V. Skvortsova. Veamos algunos algoritmos.

Uno de los primeros en ser propuesto. algoritmo codicioso construcción de triangulación. Una triangulación de Delaunay se llama codiciosa si se construye utilizando un algoritmo codicioso. La complejidad del algoritmo codicioso con algunas de sus mejoras es. Debido a la gran intensidad de mano de obra, casi nunca se utiliza en la práctica. Veamos el algoritmo paso a paso:

Paso 1. Se genera una lista de todos los segmentos posibles que conectan pares de puntos de origen y se clasifica por longitudes de segmento.

Paso 2. Comenzando por el más corto, se insertan segmentos en la triangulación de forma secuencial. Si un segmento no se cruza con otros segmentos previamente insertados, entonces se inserta; de lo contrario, se descarta.

Tenga en cuenta que si todos los segmentos posibles tienen longitudes diferentes, entonces el resultado de este algoritmo no es ambiguo; de lo contrario, depende del orden de inserción de los segmentos de la misma longitud.

Algoritmo iterativo se basan en muy idea sencilla Suma secuencial de puntos a la triangulación de Delaunay parcialmente construida. Complejidad de este algoritmo consiste en la complejidad de buscar un triángulo al que se le añade un punto en el siguiente paso, la complejidad de construir nuevos triángulos, así como la complejidad de las correspondientes reconstrucciones de la estructura de triangulación como resultado de comprobaciones insatisfactorias de pares de vecinos. triángulos de la triangulación resultante para el cumplimiento de la condición de Delaunay. Veamos el algoritmo paso a paso:

Paso 1. Construimos un triángulo en los primeros tres puntos iniciales.

Paso 2. En el ciclo para todos los demás puntos realizamos los pasos 3-5.

Paso 3. El siguiente punto i se agrega a la estructura de triangulación ya construida de la siguiente manera. Primero, el punto está localizado, es decir. hay un triángulo (construido anteriormente) en el que cae el siguiente punto. O, si el punto no cae dentro de la triangulación, se ubica un triángulo en el borde de la triangulación, más cercano al siguiente punto.

Etapa 4. Si un punto cae en un nodo de triangulación previamente insertado, entonces dicho punto generalmente se descarta; de lo contrario, el punto se inserta en la triangulación como un nuevo nodo. Además, si el punto cae sobre algún borde, entonces se divide en dos nuevos, y ambos triángulos adyacentes al borde también se dividen en dos más pequeños. Si el punto cae estrictamente dentro de un triángulo, se divide en tres nuevos. Si el punto queda fuera de la triangulación, entonces se construyen uno o más triángulos.

Paso 5. Se llevan a cabo comprobaciones locales de que los triángulos recién obtenidos cumplan la condición de Delaunay y se realizan las reconstrucciones necesarias.

Al construir nuevos triángulos, son posibles dos situaciones: el punto agregado cae dentro o fuera de la triangulación. En el primer caso, se construyen nuevos triángulos y se fija el número de acciones realizadas por el algoritmo. En el segundo, es necesario construir triángulos adicionales externos a la triangulación actual, y su número puede, en el peor de los casos, ser igual a? 3. Sin embargo, durante todos los pasos del algoritmo no se agregarán más triángulos, donde: numero total puntos de partida. Por tanto, en ambos casos, el tiempo total dedicado a construir triángulos es.

Algoritmo de cadena Uno de los primeros algoritmos eficaces para construir triangulación se basa en el procedimiento de regularización de un gráfico plano y triangulación de polígonos monótonos. La complejidad de este algoritmo es dónde está el número de segmentos iniciales. Veamos el algoritmo paso a paso:

Paso 1. A partir del conjunto de segmentos estructurales iniciales formamos un gráfico plano conectado (Figura 4, a).

Paso 2. El gráfico está regularizado, es decir. Se agregan nuevas aristas que no se cruzan con otras, de modo que cada vértice del gráfico se vuelve adyacente a al menos un vértice encima y otro debajo. La regularización se realiza en dos pasadas mediante barrido plano vertical. En la primera pasada de abajo hacia arriba se encuentran secuencialmente todos los vértices de los que no emerge ninguna arista que conduzca hacia arriba. Por ejemplo, en (Figura 4, b) este es el vértice B. Al realizar linea horizontal, encontramos los bordes más cercanos del gráfico AD y EF que intersecta a la izquierda y a la derecha. Luego, en el cuadrilátero DEHG encontramos el vértice más bajo y dibujamos un borde desde B hacia él. La segunda pasada de arriba a abajo se realiza de manera similar (Figura 4,c). Como resultado de este paso, cada región del gráfico plano se convierte en un polígono monótono.

Paso 3. Cada región del gráfico debe dividirse en triángulos. Para hacer esto, puede utilizar el algoritmo de fusión no convexa de dos triangulaciones (Figura 4, d).

Figura 4. Esquema de funcionamiento del algoritmo de triangulación de cadenas: a) - segmentos iniciales; b - paso ascendente de la regularización del gráfico; c) - paso de arriba a abajo; d) - triangulación de polígonos monótonos

Para implementar un algoritmo encadenado, es mejor utilizar estructuras de datos en las que las aristas se representen explícitamente, como “dobles aristas” o “nodos, aristas y triángulos”.

La desventaja del algoritmo en cadena es que no se puede decir nada de antemano sobre la forma de la triangulación resultante. Esta no es una triangulación óptima, ni codiciosa, ni una triangulación de Delaunay restringida. El algoritmo de cadena puede producir triángulos alargados muy largos.

Para mejorar la calidad de la triangulación resultante, se pueden comprobar todos los pares de triángulos adyacentes que no están separados por un borde estructural para la condición de Delaunay y, si es necesario, realizar reconstrucciones. El resultado será una triangulación de Delaunay con restricciones.

Teplov a.a., Licenciatura, MSTU que lleva el nombre de N.E. Bauman, departamento " Software computadora y tecnologías de la información", Moscú, [correo electrónico protegido]

MAYKOV K.A., Doctor en Ciencias Técnicas, Profesor de la Universidad Técnica Estatal de Moscú que lleva el nombre de N.E. Bauman, Departamento de Software Informático y Tecnologías de la Información, Moscú, [correo electrónico protegido]

Algoritmo modificado
Triangulación de Delaunay

Los resultados se dan análisis comparativo Métodos de triangulación de Delaunay con alto rendimiento y bajo consumo de recursos. La elección de un prototipo para su posterior modernización se fundamenta en la construcción de objetos tridimensionales dinámicos en tiempo real con un grado de detalle prácticamente necesario. Se propone un algoritmo para la partición de intervalos de un conjunto de puntos de triangulación de acuerdo con la densidad de distribución, que permite evitar errores en la implementación del hardware. Un análisis de la propuesta. algoritmo modificado Triangulación de Delaunay

Introducción

Una de las etapas que determina la intensidad de recursos para la construcción de objetos 3D dinámicos con un determinado nivel de detalle es la triangulación. En la práctica, existe la necesidad de determinar un prototipo de método de triangulación que satisfaga el requisito de alto rendimiento y baja intensidad de recursos, con modificaciones posteriores para una clase específica de problemas.

Establecer las tareas a resolver.

Una serie de problemas prácticos se caracterizan por la necesidad de modelar objetos 3D descritos por un conjunto correspondiente de puntos con una ley de distribución desconocida. Ejemplo tareas similares es el modelado de una cadena montañosa o estructuras superficiales complejas e irregulares, cuyas alturas se obtienen previamente mediante teledetección. En este caso, es necesario realizar una triangulación sobre el conjunto original de puntos, asegurando el mayor "grado de corrección" de los triángulos, que se caracteriza por la exclusión de la construcción de triángulos "delgados" con un valor mínimo de la suma. de los radios de los círculos circunscritos.

El problema del “grado de regularidad” de los triángulos se resuelve mediante una triangulación que satisface la condición de Delaunay.

Los algoritmos de triangulación de Delaunay conocidos se pueden dividir en las siguientes cuatro categorías: algoritmos iterativos, algoritmos de fusión, algoritmos de dos pasos y algoritmos por pasos; Características clave algoritmos especificados se analizan a continuación.

Algoritmos iterativos para construir la triangulación de Delaunay.

Los algoritmos iterativos implementan la suma secuencial de puntos a una triangulación de Delaunay parcialmente construida. La complejidad de los algoritmos iterativos de Delaunay se define como O(N2), y para el caso distribución uniforme puntos – O(N) . Las desventajas de los algoritmos iterativos de Delaunay son Número grande bucles iterativos, la dependencia del algoritmo de clasificación de la estructura de los datos de origen, así como la necesidad de comprobar la condición de Delaunay en cada bucle. Las ventajas de los algoritmos iterativos de Delaunay son la facilidad de implementación y la selección de alta velocidad. algoritmo eficiente clasificación basada en un conjunto específico de datos de entrada.

Algoritmos para construir la triangulación de Delaunay mediante fusión

Los algoritmos de fusión implementan la división del conjunto original de puntos en varios subconjuntos, en los que se construyen triangulaciones con la posterior fusión de varias soluciones. La complejidad promedio de los algoritmos de fusión es O (N). Los algoritmos de fusión se caracterizan por la redundancia, determinada por la necesidad de construir áreas convexas para franjas "estrechas" y, en consecuencia, la formación de triángulos largos y "estrechos", reconstruidos durante la fusión. Los algoritmos de fusión tienen un alto rendimiento, lo que determina su ventaja práctica.

Algoritmos de dos pasos para construir la triangulación de Delaunay.

La característica ventajosa de los algoritmos de dos pasadas es que en el primer ciclo se construye una determinada triangulación sin tener en cuenta la condición de Delaunay, que se modifica en la segunda etapa según la condición de Delaunay. La complejidad de los algoritmos de dos pasadas es, en promedio, O(N) y, en el caso menos favorable, O(N 2). La desventaja de los algoritmos de Delaunay de dos pasos es la necesidad de grandes cantidades tipos para cada carril. Al mismo tiempo, este algoritmo se caracteriza por un alto rendimiento, porque No se comprueba que el siguiente triángulo que cae en la triangulación cumpla la condición de Delaunay, lo que requiere importantes recursos de hardware.

Algoritmos paso a paso para construir la triangulación de Delaunay

Los algoritmos de construcción paso a paso implementan sólo triángulos que satisfacen la condición de Delaunay en la triangulación final y, por tanto, no requieren reconstrucción. Con una gran concentración de puntos, el uso de un algoritmo celular paso a paso no es práctico. La complejidad de este algoritmo es, en promedio, O(N) y, en el peor de los casos, O(N 2).

Selección de un prototipo para modificar la triangulación de Delaunay.

Las características prácticas del problema de construir objetos 3D dinámicos en tiempo real determinan requisitos para los algoritmos de triangulación de Delaunay como alto rendimiento y baja intensidad de recursos. Como se desprende de los resultados del análisis anterior, los algoritmos considerados no satisfacen completamente estos requisitos. Por lo tanto, existe la necesidad de construir un algoritmo que no dependa de la división del área de triangulación en primitivas que contengan puntos de la triangulación misma, y ​​que no requiera verificar la condición de Delaunay en cada iteración de agregar el triángulo actual a la triangulación original. .

De los resultados anteriores del análisis comparativo se deduce que los algoritmos de triangulación de Delaunay de dos pasos, en particular el algoritmo del ventilador de dos pasos, satisfacen sólo parcialmente los criterios de alto rendimiento y baja intensidad de recursos.

Sin embargo, los algoritmos de este tipo necesitan modificaciones para mejorar el rendimiento cuando sean aplicables a tareas en tiempo real. El algoritmo del ventilador de dos pasadas es redundante para determinar el centro de masa de los puntos. Al determinar la coordenada de un centro de masa puntual utilizando OX u OY, con una gran cantidad de puntos no es apropiado calcular el valor de la media aritmética, y cuando valores grandes coordenadas de puntos, puede producirse un desbordamiento de datos, lo que provocará un error o una falla del programa. Por tanto, es recomendable dividir todos los valores de los puntos de triangulación en intervalos a lo largo del eje X en Δx 1, Δx 2, Δx 3 ... Δx n y a lo largo del eje Y en Δy 1, Δy 2, Δy 3 ... Δy n. También es necesario determinar el número de puntos pertenecientes a los intervalos correspondientes a lo largo de los ejes X e Y. Las fórmulas resultantes para obtener el centro de masa de los puntos tienen la siguiente forma:

• x c – coordenada x del punto del centro de masa;
• Δх yo – intervalo i-ésimo en el eje X;
• Xmáx – valor máximo a lo largo del eje X entre todos los puntos de triangulación;
• X min – valor mínimo a lo largo del eje X entre todos los puntos de triangulación;

• y c – coordenada y del punto del centro de masa;
• n i – número de puntos en el i-ésimo intervalo;
• Δy i – i-ésimo intervalo en el eje Y;
• Y max – valor máximo a lo largo del eje Y entre todos los puntos de triangulación;
• Y min: el valor mínimo a lo largo del eje Y entre todos los puntos de triangulación.

Las etapas posteriores de triangulación se implementan según el algoritmo clásico del ventilador. El diagrama del algoritmo de triangulación de Delaunay modificado en forma de abanico desarrollado se muestra en la Fig. 1.

Las etapas que requieren más mano de obra en el esquema presentado son las etapas de clasificación y construcción de triangulación a convexa. Se eligió el algoritmo de fusión como algoritmo de clasificación y el algoritmo de Graham como algoritmo para construir la triangulación convexa. Ambos algoritmos funcionan en tiempo aceptable y son los más preferidos en términos prácticos entre sus representantes.

Análisis del algoritmo de triangulación de Delaunay modificado en forma de abanico.

Del que se muestra en la Fig. 1 del diagrama muestra que el valor de tiempo para construir la triangulación utilizando el algoritmo del ventilador modificado está determinado por la expresión:

• T 1 , T 2 – valores de tiempo para calcular el número óptimo de intervalos a lo largo de los ejes X e Y, respectivamente;
• T 3 , T 4 – valores del tiempo de cálculo X min y X max, respectivamente;
• T 5 , T 6 – valores del tiempo de cálculo Y min e Y max, respectivamente;
• T 7 , T 8 – valores de tiempo para calcular los valores de intervalo a lo largo de los ejes X e Y, respectivamente;
• T 9 – valor de tiempo para calcular el ángulo polar de cada punto del conjunto con respecto al punto A(X c ,Y c);
• T 10 – el valor del tiempo de clasificación fusionando todos los puntos por ángulo polar con respecto al punto A(X c ,Y c);
• T 11 – valor de tiempo para construir una arista desde cada punto de la matriz hasta el punto A(X c ,Y c);
• T 12 – valor de tiempo para completar la triangulación a convexa;
• T 13 – el valor del tiempo de reconstrucción de la triangulación que satisface la condición de Delaunay;
• n – matriz de valores de coordenadas de puntos.

Consideremos cada dependencia del tiempo por separado.

Al determinar el número óptimo de intervalos a lo largo de los ejes X e Y, utilizamos la regla de Sturges, según la cual el número de intervalos n se determina como:

• N es el número total de observaciones de la cantidad;
• [X] - Toda una parte números x.

Es obvio que las dependencias temporales T 1 y T 2 tienen representaciones constantes c 1 y c 2.

En las etapas de determinación de los valores X min , X max , Y min , Y max el pseudocódigo se verá así:

Xmín ← M

para i ← 1 a longitud (M) – 1

Si Xmin › M[i]

Xmín ← M[i]

Xmáx ← M

para i ← 1 a longitud (M) – 1

Si Xmax< M[i]

Xmáx ← M[i]

Ymín ← M

para i ← 1 a longitud (M) – 1

Si Ymin › M[i]

Ymín ← M[i]

Ymáx ← M

para i ← 1 a longitud (M) – 1

Si Ymáx< M[i]

Ymáx ← M[i]

Del pseudocódigo anterior se ve claramente que el tiempo para encontrar el máximo o valor mínimo valores x o y tiene dependencia lineal O(N), por lo tanto, T 3 (n), T 4 (n), T 5 (n), T 6 (n), tienen una característica de tiempo O(N), respectivamente.

El diagrama para determinar los valores de los intervalos a lo largo del eje X se muestra en la Fig. 2.

En el diagrama presentado anteriormente, la dependencia lineal del tiempo de O(N) también es visible, porque Todo el conjunto de coordenadas de los valores de la matriz de puntos interviene en la determinación de los valores. El esquema para determinar los valores de los intervalos a lo largo del eje Y tiene una estructura y características de tiempo similares, por lo tanto, la dependencia del tiempo para T 7 (n) y T 8 (n) tiene la forma O(N).

El esquema para determinar los valores de los ángulos polares para la matriz inicial de puntos se muestra en la Fig. 3.

Como pseudocódigo este esquema se verá así:

para puntos a puntos

# Si el punto se encuentra en el eje de coordenadas entre el primer y el cuarto trimestre

Si punto.x ≥ Xc y punto.y = Yc

Punto.ángulo ← 0

# Si el punto está estrictamente en el primer cuarto

De lo contrario, si punto.x > Xc y punto.y > Yc

Fundación ← |punto.x – Xc|

Punto.ángulo ← arctg(perpendicular/cimiento)

# Si el punto se encuentra en el eje de coordenadas entre el primer y el segundo trimestre

De lo contrario, si punto.x = Xc y punto.y > Yc

Punto.ángulo ← p/2

# Si el punto está estrictamente en el segundo cuarto

De lo contrario, si punto.x< Xc and point.y >yc

Fundación ← |punto.y – Yc|

Punto.ángulo ← p/2 + arctg(perpendicular/cimiento)

# Si el punto se encuentra en el eje de coordenadas entre los cuartos II y III

Si punto.x< Xc and point.y = Yc

Punto.ángulo ← p

# Si el punto está estrictamente en el tercer cuarto

Si punto.x< Xc and point.y >yc

Fundación ← |punto.x – Xc|

Perpendicular ← |punto.y – Yc|

Punto.ángulo ← p + arctan(perpendicular/cimiento)

# Si el punto se encuentra en el eje de coordenadas entre los trimestres III y IV

Si punto.x = Xc y punto.y< Yc

Punto.ángulo ← 3p/2

# Si el punto se encuentra estrictamente en el IV trimestre

Si punto.x > Xc y punto.y< Yc

Fundación ← |punto.y – Yc|

Perpendicular ← |punto.x – Xc|

Punto.ángulo ← 3p/2 + arctg(perpendicular/cimiento)

Obviamente, la característica de tiempo para determinar los valores del ángulo polar para la matriz original de coordenadas de puntos tiene la forma O(N), por lo tanto, T 9 (n) = O(N).

Como se muestra en , la ordenación por fusión tiene una dependencia temporal de la forma O(N), por lo tanto T 10 (n) = O(NlnN).

El diagrama para construir una arista que conecta los puntos de la matriz original se muestra en la Fig. 4.

El pseudocódigo del circuito anterior se verá así:

para i ← 0 a longitud (Puntos) – 1

Dibujar(Xc,Yc,Puntos[i].x, Puntos[i].y)

La respuesta temporal también es lineal, por lo tanto T 11 (n) = O(N).

La finalización de la triangulación resultante a una convexa se realiza según el algoritmo de Graham. El dato de entrada del procedimiento es el conjunto de puntos Q, donde |Q|≥3. Llama a la función Top(S), que devuelve el punto en la parte superior de la pila S sin cambiar su contenido. Además, también se utiliza la función NextToTop(S), que devuelve un punto ubicado en la pila S, una posición debajo del punto superior; La pila S permanece sin cambios.

Graham(Q)

Sea p 0 un punto del conjunto Q con una coordenada mínima.

Sea ‹p 1 , p 2 ,...,p N › – puntos del conjunto Q, ordenados

En orden de ángulo polar creciente.

Empujar(p 0 ,S)

Empujar (pág. 1, S)

para i=2 a N hacer

Mientras que el ángulo formado por los puntos NextToTop(S), Top(S) y pi,

Formar un giro no a la izquierda

# al moverse a lo largo de una línea discontinua formada por estos

# puntos, el movimiento se realiza en línea recta o hacia la derecha

Hacer pop

Empujar(pi,S)

devoluciones

El tiempo de ejecución del procedimiento de Graham es O(NlnN), donde N=longitud(Q). Es fácil demostrar que el ciclo while tomará tiempo O(N), y ordenar los ángulos polares tomará tiempo O(NlnN), lo que implica las asintóticas generales del procedimiento de Graham, por lo tanto, T 12 (n) = O( NlnN).

La característica temporal de reconstruir una triangulación que satisface la condición de Delaunay, como se muestra en , tiene una dependencia lineal O(N), por lo tanto T 13 (n) = O(N).

Si sustituimos todas las características de tiempo encontradas en la expresión (3), entonces la dependencia del tiempo resultante se verá así:

T(n) = c 1 +c 2 +O(N)+O(N)+O(N)+O(N)+O(N)+O(N)+O(N)+ +O(NlnN )+O(N)+O(NlnN)+O(N)

T(n) = O(NlnN)

Realizado Análisis teorico Las características temporales del algoritmo de triangulación de Delaunay modificado confirman la eficiencia y el alto rendimiento del algoritmo propuesto.

conclusiones

Como resultado del análisis comparativo de los algoritmos de triangulación de Delaunay prácticamente populares, se muestra que los métodos considerados no cumplen con los requisitos para construir objetos dinámicos tridimensionales en tiempo real con anticipación. hasta cierto punto detalle y, por tanto, existe una necesidad práctica de modificarlos. Se propone una modificación del algoritmo de triangulación de Delaunay de dos pasos del ventilador, característica funcional que consiste en calcular los valores del centro de masa del conjunto de coordenadas de puntos de triangulación dividiendo el conjunto de puntos en subconjuntos a lo largo de los ejes X e Y. Se ha realizado el análisis de las características temporales del algoritmo de triangulación de Delaunay modificado. afuera. Cálculos especificados le permitirá mejorar significativamente el rendimiento en una gran variedad de puntos al determinar las coordenadas del punto del centro de masa y evitar el desbordamiento de datos y, por lo tanto, errores en la implementación del software.

1. Knut D.E. El arte de programar. Volumen 1. Algoritmos básicos. – M.: Williams, 2008. – 680 p.
2. Knut D.E. El arte de programar. Volumen 3. Ordenar y buscar. – M.: Williams, 2008. – 800 p.
3. Mandelbrot B. Geometría fractal de la naturaleza. – M.: Instituto de Investigaciones Informáticas, 2002. – 656 p.
4. Triangulación de Skvortsov A.V.Delaunay y su aplicación. – Tomsk: Editorial Universidad de Tomsk, 2002. – 128 p.
5. Skvortsov A.V. Construcción de la triangulación de Delaunay en tiempo lineal. – Tomsk: Editorial de la Universidad de Tomsk, 1999. – P.120-126.
6. Skvortsov A.V., Mirza N.S. Algoritmos para la construcción y análisis de triangulación. – Tomsk: Editorial de la Universidad de Tomsk, 2006. – 168 p.
7. Thomas H. Corman, Charles I. Leiseron, Ronald L. Rivest, Clifford Stein. Algoritmos: construcción y análisis, 3ª ed.: Transl. De inglés – M.: Williams, 2013. – 1328 p.
8. Shaidurov V.V. Métodos de elementos finitos multired. – M.: Nauka, 1989. – 288 p.
9. Sturges H. (1926). La elección de un intervalo de clase. J.Amer. Estadístico. Asoc., 21, 65-66.

Palabras clave: realidad virtual, triangulación sobre un conjunto determinado de puntos, triangulación de Delaunay, construcción de objetos dinámicos tridimensionales.

El algoritmo de triangulación de Delaunay modificado.

Teplov a.a., Licenciatura, MSTU Bauman, Departamento de "Software y Tecnologías de la Información", Moscú, [correo electrónico protegido]

Maikov K.A., Doctor en Ciencias Técnicas, Profesor, MSTU Bauman, Departamento de "Software y Tecnologías de la Información", Moscú, [correo electrónico protegido]

Abstracto: En este artículo se describen los resultados del análisis comparativo de los métodos prácticamente populares de triangulación de Delaunay con alto rendimiento y bajo consumo de recursos. La elección del método para una mayor modernización con el objetivo de construir objetos tridimensionales dinámicos en tiempo real con un cierto grado de detalle está justificada. Se modifica una de las principales etapas de una fibra: el algoritmo de dos pasos de la triangulación de Delaunay. Existe la propuesta del algoritmo. Para el partición de intervalo de la matriz de celdas de la triangulación de acuerdo con la densidad de distribución, lo que permite evitar errores en la implementación del hardware.

Palabras clave: realidad virtual, triangulación sobre un conjunto de células determinada, triangulación de Delaunay, construcción de objetos dinámicos en 3D.

En contacto con

Triangulación espacial de Delaunay

La tarea de construir una red de triángulos que no se superpongan es una de las básicas en geometría Computacional y es ampliamente utilizado en gráficos de la máquina Y Sistemas de Información Geográfica para modelado de superficies y resolución de problemas espaciales.

El problema de construir una red de triángulos no superpuestos se planteó por primera vez en 1934 en la obra matemático soviético B. N. Delaunay, 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 Interpolación linear 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, reordenando secuencialmente pares de puntos vecinos. triangulos 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 le permite construir una 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 según 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, una de las operaciones más importantes que se realizan al construir una triangulación es verificar la condición de Delaunay para pares dados triangulos. 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 algoritmos conocidos Utilice la definición de triangulación de Delaunay como síntoma secundario triangulación. 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;

El más famoso productos de software Construya la triangulación de Delaunay utilizando el teorema de la bola vacía como principio principal y primario 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 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.

El conjunto de puntos de origen se divide líneas verticales en dos o más partes, después de lo cual cada una de ellas 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 bisectriz perpendicular hasta la línea de base (Fig. 5.7, b), busque un nodo que caiga en 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 iniciales 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, 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 tener en cuenta y mostrar su linealidad y área. elementos estructurales. Dichos elementos adicionales son líneas estructurales ampliamente utilizadas en topografía que definen el “esqueleto del relieve”: cuencas hidrográficas, vaguadas, crestas, acantilados, cornisas, lagos, barrancos, costas, límites estructuras artificiales y otros, cuya totalidad crea, por así decirlo, el marco de la triangulación de Delaunay. Estas líneas de ruptura se introducen en la triangulación como las aristas de los triángulos, que es como se logra el modelado. elementos reales alivio en el contexto de desnivel general superficie de la Tierra. 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 cumplen 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.

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 más 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, error promedio El estudio del relieve no debe exceder 1/3 de la sección 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 terrestre de una 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 altura máxima 0,15 m Es fácil calcular que no tenerlo en cuenta a la hora de representar una determinada superficie con sólo dos triángulos dará lugar a un 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 formas positivas Los terrenos planos suelen tener forma convexa, mientras que los negativos tienen 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, 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 caso bidimensional nuestro “círculo vacío” se arreglará 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 espacio tridimensional El balón no está definido 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 se llama la figura mas simple en un espacio de una dimensión determinada: 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 que son horizontales o tienen una ligera pendiente se asignan a una región separada, por ejemplo b<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.

Estructura de la conferencia Definiciones Definiciones Áreas de aplicación Áreas de aplicación Propiedades de la triangulación de Delaunay Propiedades de la triangulación de Delaunay Métodos para construir la triangulación de Delaunay Métodos para construir la triangulación de Delaunay Métodos de entrada paso a paso Métodos de entrada paso a paso Métodos de muestreo paso a paso Paso Métodos de muestreo por pasos Métodos de descomposición Métodos de descomposición Métodos de escaneo Métodos de escaneo Métodos de dos pasos Métodos de dos pasos

Triangulación La triangulación es un gráfico plano cuyas regiones interiores son todas triángulos. La triangulación es un gráfico plano cuyas regiones interiores son todas triángulos. El término "Triangulación" es un gráfico; grafico; proceso de construcción de grafos. proceso de construcción de grafos. El problema de triangulación para un conjunto de puntos S es el problema de conectar todos los puntos de un conjunto S con segmentos disjuntos para obtener un gráfico de triangulación. El problema de triangulación para un conjunto de puntos S es el problema de conectar todos los puntos de un conjunto S con segmentos disjuntos para obtener un gráfico de triangulación. Definición de triangulación Conjunto de puntos S

La triangulación óptima es una triangulación con la suma mínima de las longitudes de todos los bordes del gráfico. La triangulación óptima es una triangulación con la suma mínima de las longitudes de todos los bordes del gráfico. ! ¡Un problema O(2 n) popular, pero que requiere mucho tiempo! En la práctica, se utilizan aproximaciones (aproximaciones a) la triangulación óptima: Triangulación “codiciosa” O(N 2 *logN) Triangulación “codiciosa” O(N 2 *logN) Triangulación de Delaunay O(N*logN) Triangulación de Delaunay O(N*logN ) Definición triangulación óptima

La triangulación de Delaunay (DT(S)) es una triangulación convexa que satisface la condición de Delaunay: La triangulación de Delaunay (DT(S)) es una triangulación convexa que satisface la condición de Delaunay: ninguno de los vértices del gráfico debe caer dentro del círculo circunscrito alrededor cualquiera de sus triángulos. ninguno de los vértices del gráfico debe caer dentro del círculo circunscrito a cualquiera de sus triángulos. Definición de triangulación de Delaunay Se cumple la condición de Delaunay No se cumple la condición de Delaunay B.N. Delaunay()

Aplicación de la triangulación de Delaunay En otros problemas de VG En otros problemas de VG Abarcación mínima de un conjunto de puntos Abarcación mínima de un conjunto de puntos Construcción de zonas de amortiguamiento Construcción de zonas de amortiguamiento Construcción de un diagrama de Voronoi (zonas de proximidad) Construcción de un diagrama de Voronoi (zonas de proximidad) zonas) Encontrar el círculo vacío máximo Encontrar el círculo vacío máximo, etc. etc. En aplicaciones en CG, GIS, GM en CAD En aplicaciones en CG, GIS, GM en CAD Modelos poligonales de superficies Modelos poligonales de superficies Relieves en GIS, esculturas , maquetas industriales, maquetas en juegos, Relieves en GIS, esculturas, .maquetas industriales, maquetas en juegos, Análisis numérico de modelos Análisis numérico de modelos Isolinas, Isoclinas, FEM. Isolinas, Isoclinas, FEM.

Propiedades de cualquier triangulación convexa 1. Para un conjunto de n puntos de los cuales m son internos Número de triángulos de triangulación = n + m – 2 Número de triángulos de triangulación = n + m – 2 Número de aristas de triangulación 3n – 6 Número de aristas de triangulación 3n – 6 Ejemplo: Puntos (n) – 13 Puntos (n) – 13 Internos (m) – 4 Internos (m) – 4 Triángulos – 15 = Triángulos – 15 = Aristas – 26 3*13-6 = 33 Aristas – 26 3 *13-6 = 33

Propiedades de la triangulación de Delaunay 2. La triangulación de Delaunay tiene la suma máxima de los ángulos mínimos de todos los triángulos entre todas las triangulaciones posibles. 3. La triangulación de Delaunay tiene la suma mínima de los radios de los círculos descritos alrededor de los triángulos entre todas las triangulaciones posibles. Triangulación de Delaunay NO triangulación de Delaunay

Métodos para construir la triangulación de Delaunay Métodos de entrada paso a paso Métodos de entrada paso a paso Algoritmos iterativos () Algoritmos iterativos () Métodos de muestreo paso a paso Métodos de muestreo paso a paso Construcción directa (paso a paso) algoritmos (3) Algoritmos de construcción directa (paso a paso) (3) Métodos de descomposición Métodos de descomposición Algoritmos de fusión (2 ) Algoritmos de fusión (2) Métodos de escaneo Métodos de escaneo Algoritmos iterativos con un orden modificado de suma de puntos (1.4) Algoritmos iterativos con un orden modificado para sumar puntos (1.4) Algoritmos de dos pasos (4) Algoritmos de dos pasos (4)

Métodos de entrada paso a paso Algoritmos iterativos () Esquema general de algoritmos iterativos para construir la triangulación de Delaunay 1. Construya un triángulo en los primeros tres puntos 2. Recorra todos los puntos restantes p i del conjunto S 3. Encuentre el triángulo t j más cercano al punto p i de la triangulación actual 4. Si el punto p i está fuera del triángulo t j, entonces construya triángulos hasta el borde más cercano. 5. Si el punto p i está dentro del triángulo t j, entonces divide el triángulo en tres. 6. Si el punto p i está en una arista, divida los triángulos adyacentes en pares. 7. Si se viola la condición de Delaunay para los vecinos, reconstruya los triángulos vecinos. Opciones para acelerar la búsqueda de triángulos: Indexación de triángulos (árboles) – O(log n) Indexación de triángulos (árboles) – O(log n) Almacenamiento en caché de triángulos (malla) – O(s) Almacenamiento en caché de triángulos (malla) – O(s)

Métodos de muestreo paso a paso Algoritmos de construcción directa (paso a paso) (3) Construya los triángulos necesarios inmediatamente, sin reconstruir lo ya construido. Esquema general de algoritmos para la construcción directa de la triangulación de Delaunay. Es conveniente utilizar una pila de aristas sin procesar. 1. Encuentre cualquier borde q del casco convexo de un conjunto de puntos S. 2. Empuje el borde q dentro de la pila de bordes sin procesar. 3. Haga un bucle hasta que la pila de bordes sin procesar esté vacía. 4. Saque el borde v de la pila. 5. Para el borde v, encuentre un punto p que satisfaga la condición de Delaunay (vecino de Delaunay) 6. Si se encuentra el vecino p de Delaunay, entonces 7. Construya un triángulo desde el borde v hasta el punto p. 8. Empuje los nuevos bordes del nuevo triángulo sobre la pila de bordes sin rematar. Opciones para acelerar la búsqueda de vecinos de Delaunay: Indexación de puntos con un árbol k-D – O(log n) Indexación de puntos con un árbol k-D – O(log n) Indexación celular de puntos – O(c) Indexación celular de puntos – O(c )

Proceso del codicioso algoritmo de triangulación de Delaunay

Métodos de descomposición Algoritmos de fusión (2) Partición en subconjuntos, procesamiento independiente, fusión de resultados. Esquema general de algoritmos de fusión 0. Si no hay más de 3 puntos en el conjunto S, construya directamente; de ​​lo contrario, 1. Divida el conjunto de puntos S en subconjuntos aproximadamente iguales. 1. Divida el conjunto de puntos S en subconjuntos aproximadamente iguales. 2. Construcción de triangulación por subconjuntos. 2. Construcción de triangulación por subconjuntos. 3. Fusionar las triangulaciones resultantes en una sola. 3. Fusionar las triangulaciones resultantes en una sola. Métodos de división en subconjuntos Líneas rectas ortogonales Líneas rectas ortogonales Por el diámetro de un casco convexo Por el diámetro de un casco convexo Rayas Rayas

Algoritmos de fusión (2) Métodos para fusionar triangulaciones “Eliminar y construir” (verificar antes de la construcción) “Eliminar y construir” (verificar antes de la construcción) “Construir y reconstruir” (verificar después de la construcción) “Construir y reconstruir” (verificar después de la construcción) “ Construir, reconstruir" (verificar durante la construcción) "Construir, reconstruir" (verificar durante la construcción)

Esquema general de métodos iterativos con un orden modificado de adición de puntos 1. Organizar los puntos (construir una lista de puntos de eventos) 2. Explorar en ciclo todos los puntos de eventos 3. Para cada punto p i, construir triángulos hasta el triángulo anterior. 4. Si se viola la condición de Delaunay para los vecinos, reconstruya los triángulos vecinos. Métodos de escaneo Algoritmos iterativos con un orden modificado de suma de puntos (1.4)

Métodos de escaneo Métodos para ordenar puntos de eventos Rectilíneo Rectilíneo Polar (circular, en forma de abanico) Polar (circular, en forma de abanico) Raya Raya Cuadrado Cuadrado Por curva de Hilbert Por curva de Hilbert Por código Z Por código Z Objetivos: Construir inmediatamente un máximo de triángulos buenos Construya inmediatamente un máximo de triángulos buenos Minimice el número de cambios de carril Minimice el número de cambios de carril

Resumen de características de los métodos de triangulación de Delaunay Método de triangulación Tiempo en promedio Tiempo en el peor Tiempo seg/t Facilidad de implementación. Métodos de entrada paso a paso Métodos de entrada paso a paso Algoritmos iterativos () Algoritmos iterativos ()O(n)- O(n 3/2) O(n 2) 1,5-9,2 2-5 Paso a paso métodos de muestreo Métodos de muestreo paso a paso Método de construcción directa (3) Método de construcción directa (3) O(n)- O(n 2) O(n 2) -2 Métodos de descomposición Métodos de descomposición Métodos de fusión (2) Métodos de fusión ( 2) O(n)- O(nlogn) O (nlogn)- O(n 2) 2.5-4.52-3 Métodos de escaneo Métodos de escaneo Iterativo con un orden cambiado de agregar puntos (1.4) Iterativo con un orden cambiado de agregar puntos ( 1.4)O(n) O(n 2) 1 ,9-5,34-5 Métodos de dos pasos (4) Métodos de dos pasos (4) O(n)- O(n 2) O(nlogn)- O (n 2) 2.2-15.41-5 Skvortsov recomienda: algoritmo iterativo con almacenamiento en caché dinámico

¿De qué se trata hoy? ¡Sobre la triangulación de Delaunay! Definición Definición Áreas de aplicación Áreas de aplicación Propiedades de la triangulación de Delaunay Propiedades de la triangulación de Delaunay Métodos para construir la triangulación de Delaunay Métodos para construir la triangulación de Delaunay Métodos de entrada paso a paso Métodos de entrada paso a paso Métodos de muestreo paso a paso Paso a Métodos de muestreo en pasos Métodos de descomposición Métodos de descomposición Métodos de escaneo Métodos de escaneo Métodos de dos pasos Métodos de dos pasos