Algoritmo de triangulaci贸n de Delaunay por m茅todo de l铆nea de barrido

Buen dia

En este art铆culo, describir茅 en detalle el algoritmo que obtuve como resultado de usar la idea de "barrer la l铆nea recta" para construir la triangulaci贸n de Delaunay en un plano. Hay varias ideas que nunca conoc铆 cuando le铆 art铆culos sobre triangulaci贸n.
Quiz谩s alguien tambi茅n los encuentre inusuales. Intentar茅 hacer todo con la mejor tradici贸n e incluir lo siguiente en la historia: una descripci贸n de las estructuras de datos utilizadas, una descripci贸n de los pasos del algoritmo, prueba de correcci贸n, estimaciones de tiempo, as铆 como una comparaci贸n con un algoritmo iterativo que utiliza el 谩rbol kD.

Definiciones y enunciado del problema.


Triangulaci贸n


Se dice que la triangulaci贸n se da en el conjunto de puntos en el plano si algunos pares de puntos est谩n conectados por un borde, cualquier cara finita en el gr谩fico resultante forma un tri谩ngulo, los bordes no se cruzan y el gr谩fico es m谩ximo en el n煤mero de bordes.



Triangulaci贸n de Delaunay


Una triangulaci贸n de Delaunay es una triangulaci贸n en la que para cualquier tri谩ngulo es cierto que no hay puntos del conjunto original dentro del c铆rculo circunscrito a su alrededor.



Nota : para un conjunto dado de puntos en el que no hay 4 puntos en el mismo c铆rculo, hay exactamente una triangulaci贸n de Delaunay.

La condici贸n de Delaunay


Deje una triangulaci贸n en el conjunto de puntos. Decimos que cierto subconjunto de puntos satisface la condici贸n de Delaunay si la triangulaci贸n limitada en este subconjunto es la triangulaci贸n de Delaunay para 茅l.

Criterio para la triangulaci贸n de Delaunay


El cumplimiento de la condici贸n de Delaunay para todos los puntos que forman un cuadr谩ngulo en una triangulaci贸n es equivalente al hecho de que esta triangulaci贸n es una triangulaci贸n de Delaunay.

Nota : para los cuadr谩ngulos no convexos, la condici贸n de Delaunay siempre se cumple, y para los cuadr谩ngulos convexos (cuyos v茅rtices no se encuentran en el mismo c铆rculo) hay exactamente 2 triangulaciones posibles (una de las cuales es la triangulaci贸n de Delaunay).



La tarea es construir una triangulaci贸n de Delaunay para un conjunto dado de puntos.

Descripci贸n del algoritmo


Puntos visibles y bordes visibles.


Deje que se proporcione un casco convexo m铆nimo (en adelante MBO) de un conjunto finito de puntos (bordes que conectan algunos de los puntos para que formen un pol铆gono que contenga todos los puntos del conjunto) y un punto A que se encuentra fuera del casco. Entonces, el punto del plano se llama visible para el punto A, si el segmento que lo conecta al punto A no se cruza con el MBO.

Un borde MBO se llama visible para el punto A si sus extremos son visibles para A.

En la siguiente imagen, los bordes visibles para el punto rojo est谩n marcados en rojo:



Nota : el contorno de triangulaci贸n de Delaunay es el MBO para los puntos en los que est谩 construido.

Observaci贸n 2 : en el algoritmo, los bordes visibles para el punto A agregado forman una cadena, es decir, varios bordes MBO en una fila

Almacenar triangulaci贸n en la memoria


Hay algunos m茅todos est谩ndar que est谩n bien descritos en el libro de Skvortsov [1]. Debido a los detalles del algoritmo, ofrecer茅 mi propia versi贸n. Como queremos verificar los 4 gones para la condici贸n de Delaunay, consideramos su estructura. Cada cuadril谩tero en triangulaci贸n es 2 tri谩ngulos que tienen un borde com煤n. Cada borde tiene exactamente 2 tri谩ngulos adyacentes. Por lo tanto, cada cuadr谩ngulo en la triangulaci贸n es generado por un borde y dos v茅rtices opuestos al borde en tri谩ngulos adyacentes.
Dado que dos tri谩ngulos y su adyacencia se restauran a lo largo del borde y dos v茅rtices, podemos restaurar la triangulaci贸n para todas esas estructuras. En consecuencia, se propone almacenar un borde con dos v茅rtices en el conjunto y realizar una b煤squeda a lo largo del borde (un par ordenado de v茅rtices).



Algoritmo


La idea de la l铆nea de barrido es que todos los puntos se ordenan en una direcci贸n y luego se procesan por turnos.

  1. Ordenar todos los puntos a lo largo de una l铆nea recta (para simplificar, por coordenadas x)
  2. Construimos un tri谩ngulo en los primeros 3 puntos.

    Adem谩s, para cada punto siguiente llevaremos a cabo pasos que preserven la invariante de que hay una triangulaci贸n de Delaunay para los puntos ya agregados y, en consecuencia, un MBO para ellos.
  3. Agregue los tri谩ngulos formados por los bordes visibles y el punto en s铆 (es decir, agregue los bordes del punto en cuesti贸n a todos los extremos de los bordes visibles).
  4. Verificamos en la condici贸n de Delaunay todos los cuadr谩ngulos generados por los bordes visibles. Si en alg煤n lugar la condici贸n no se cumple, entonces reconstruimos la triangulaci贸n en el cuadril谩tero (recuerdo que solo hay dos de ellos) y ejecutamos de forma recursiva la verificaci贸n de los cuadr谩ngulos generados por los bordes del cuadr谩ngulo actual (porque solo despu茅s de ellos podr铆a violarse la condici贸n de Delaunay).

Nota : en el paso (4) durante un inicio recursivo, no puede verificar los cuadr谩ngulos generados por los bordes que provienen del punto considerado en esta iteraci贸n (siempre hay dos de cada cuatro). La mayor铆a de las veces no ser谩n convexos, porque la prueba convexa es puramente geom茅trica, se la dejar茅 al lector. Adem谩s, suponemos que solo se realizan 2 inicios recursivos para cada reconstrucci贸n.

Verificaci贸n de una condici贸n de Delaunay


Las formas de probar los cuadr谩ngulos para la condici贸n de Delaunay se pueden encontrar en el mismo libro [1]. Solo noto que al elegir un m茅todo con funciones trigonom茅tricas a partir de ah铆, con una implementaci贸n inexacta, se pueden obtener valores negativos de los senos, tiene sentido tomarlos como m贸dulo.

Buscar bordes visibles


Queda por entender c贸mo encontrar efectivamente los bordes visibles. Tenga en cuenta que el punto S anterior agregado est谩 en el MBO en la iteraci贸n actual, ya que tiene la coordenada m谩s grande x, y tambi茅n es visible para el punto actual. Luego, observando que los extremos de los bordes visibles forman una cadena continua de puntos visibles, podemos ir desde el punto S en ambas direcciones a lo largo del MBO y recoger los bordes mientras est谩n visibles (la visibilidad del borde se verifica usando el producto vectorial). Por lo tanto, es conveniente almacenar el MBO como una lista doblemente conectada, en cada iteraci贸n eliminando los bordes visibles y agregando 2 nuevos desde el punto considerado.



Visualizaci贸n de algoritmos


Dos puntos rojos: agregado y anterior. Los bordes rojos en cada momento forman la pila de recursi贸n del paso (4):



Algoritmo correcto


Para probar la exactitud del algoritmo, es suficiente probar la conservaci贸n de la invariante en los pasos (3) y (4).

Paso (3)


Despu茅s del paso (3), obviamente, obtenemos una triangulaci贸n del conjunto actual de puntos.

Paso (4)


En el proceso del paso (4), todos los cuadr谩ngulos que no satisfacen la condici贸n de Delaunay est谩n en la pila de recursi贸n (se deduce de la descripci贸n), lo que significa que al final del paso (4) todos los cuadr谩ngulos satisfacen la condici贸n de Delaunay, es decir, la triangulaci贸n de Delaunay se construye realmente. Entonces queda por demostrar que el proceso en el paso (4) alg煤n d铆a terminar谩. Esto se deduce del hecho de que todos los bordes agregados durante la reconstrucci贸n provienen del v茅rtice actual en cuesti贸n (es decir, en el paso kno hay m谩s que k1) y por el hecho de que despu茅s de agregar estos bordes no consideraremos los cuadr谩ngulos generados por ellos (ver el comentario anterior), lo que significa que no agregaremos m谩s de una vez.

Complejidad de tiempo


En promedio, el algoritmo funciona bastante bien en distribuciones uniformes y normales (los resultados se muestran en la tabla a continuaci贸n). Se supone que su tiempo de trabajo es O(NlogN). En el peor de los casos, se realiza una evaluaci贸n. O(N2).



Echemos un vistazo al tiempo de trabajo en partes y comprendamos cu谩l tiene el mayor impacto en el tiempo total:

Ordenar por direccion


Para ordenar, usaremos la estimaci贸n O(NlogN).

Buscar bordes visibles


Primero, mostramos que el tiempo total dedicado a buscar bordes visibles es O(N). Tenga en cuenta que en cada iteraci贸n encontramos todos los bordes visibles y 2 m谩s (primero no visible) en tiempo lineal. En el paso (3), agregamos 2 aristas nuevas al MBO. Por lo tanto, en total, no m谩s de 2Ncostillas, por lo tanto, y varias costillas visibles ya no estar谩n 2N. Tambi茅n encontraremos 2Nbordes que no son visibles. Por lo tanto, en total no hay m谩s 4Ncostillas que corresponde al tiempo O(N).

Construyendo nuevos tri谩ngulos


El tiempo total para construir tri谩ngulos desde el paso (3) con bordes visibles ya encontrados es obviamente O(N).

Reconstruyendo la triangulaci贸n


Queda por tratar con el paso (4). Primero, tenga en cuenta que verificar la condici贸n de Delaunay y reconstruir si no se cumple son acciones bastante costosas (aunque funcionan para O(1)) Solo al comprobar la condici贸n de Delaunay se pueden realizar unas 28 operaciones aritm茅ticas. Veamos el n煤mero promedio de reconstrucciones durante este paso. Los resultados pr谩cticos en algunas distribuciones se dan a continuaci贸n. Para ellos, realmente quiero decir que el n煤mero promedio de reordenamientos crece con una velocidad logar铆tmica, pero dejemos esto como una suposici贸n.



Aqu铆 tambi茅n quiero se帽alar que el n煤mero promedio de reordenamientos por punto puede variar mucho de la direcci贸n a lo largo de la cual se realiza la clasificaci贸n. Entonces, para un mill贸n distribuido uniformemente en un rect谩ngulo largo y bajo con una relaci贸n de aspecto de 100000: 1, este n煤mero var铆a de 1.2 a 24 (estos valores se logran al ordenar los datos horizontal y verticalmente, respectivamente). Por lo tanto, veo el punto de elegir la direcci贸n de clasificaci贸n de manera arbitraria (en este ejemplo, con selecci贸n arbitraria, se obtuvieron en promedio aproximadamente 2 reconstrucciones) o seleccionarla manualmente si los datos se conocen de antemano.

Por lo tanto, el tiempo principal que el programa suele llevar al paso (4). Si se ejecuta r谩pidamente, tiene sentido pensar en acelerar la clasificaci贸n.

Peor caso


El peor caso en kse produce la iteraci贸n k1la llamada recursiva en el paso (4), es decir, sumando todo i, obtenemos el comportamiento asint贸tico en el peor de los casos O(N2). La siguiente imagen ilustra un hermoso ejemplo en el que el programa puede funcionar durante mucho tiempo (1100 reconstrucciones en promedio al agregar un nuevo punto con una entrada de 10,000 puntos).



Comparaci贸n con un algoritmo iterativo para construir una triangulaci贸n de Delaunay usando kD-tree


Descripci贸n del algoritmo iterativo.


Describir茅 brevemente el algoritmo anterior. Cuando llega el siguiente punto, usamos el 谩rbol kD (si no lo sabe, le aconsejo que lo lea en alguna parte), encontramos un tri谩ngulo que ya est谩 bastante cerca de 茅l. Luego, evitando en profundidad, buscamos un tri谩ngulo, en el que cae el punto. Extendemos los bordes a los v茅rtices del tri谩ngulo encontrado y realmente realizamos el paso (4) desde nuestro algoritmo para los nuevos cuadr谩ngulos. Como el punto puede estar fuera de la triangulaci贸n, para simplificar se propone cubrir todos los puntos con un tri谩ngulo grande (para construirlo de antemano), esto resolver谩 el problema.

Similitud de algoritmos


De hecho, si los puntos se agregan en orden ordenado por direcci贸n, entonces nuestro algoritmo realmente funciona igual que iterativo, excepto que el n煤mero de reordenamientos es menor. La siguiente animaci贸n lo demuestra perfectamente. En 茅l, se agregaron puntos de derecha a izquierda, y todos est谩n cubiertos por un tri谩ngulo grande, que posteriormente se elimina.



Diferencias de algoritmo


En un algoritmo iterativo, la localizaci贸n de un punto (b煤squeda del tri谩ngulo deseado) ocurre en promedio sobre O(logN), en las distribuciones anteriores, en promedio, ocurren 3 reordenamientos (como se muestra en [1]) bajo la condici贸n de un orden arbitrario de suministro de puntos. Por lo tanto, la l铆nea de barrido gana el tiempo del algoritmo iterativo en la localizaci贸n, pero lo pierde en la reconstrucci贸n (lo cual, recuerdo, es bastante dif铆cil). Adem谩s, el algoritmo iterativo funciona en l铆nea, que tambi茅n es su caracter铆stica distintiva.

Conclusi贸n


Aqu铆 solo muestro algunas triangulaciones interesantes resultantes de la operaci贸n del algoritmo.

Hermoso patr贸n




Distribuci贸n normal, 1000 puntos.




Distribuci贸n uniforme, 1000 puntos




Triangulaci贸n basada en las ubicaciones de todas las ciudades de Rusia.





Aqu铆 puede ver un ejemplo de mi c贸digo para este algoritmo:
github.com/Vemmy124/Delaunay-Triangulation-Algorithm

Gracias por su atencion!

Literatura


[1] Skvortsov A.V. La triangulaci贸n de Delaunay y su aplicaci贸n. - Tomsk: editorial Tom. Universidad, 2002 .-- 128 p. ISBN 5-7511-1501-5

Source: https://habr.com/ru/post/445048/


All Articles