Triangulação de Delaunay

Uma Triangulação Delaunay no avião com circuncírculos mostrados

Em matemática e geometria computacional, uma triangulação de Delaunay (também conhecida como triangulação de Delone) para um determinado conjunto P de pontos discretos em uma posição geral é uma triangulação DT(P) tal que nenhum ponto em P está dentro do circuncírculo de qualquer triângulo em DT(P). As triangulações de Delaunay maximizam o mínimo de todos os ângulos dos triângulos na triangulação; eles tendem a evitar triângulos de prata. A triangulação recebeu o nome de Boris Delaunay por seu trabalho sobre esse tema desde 1934.

Para um conjunto de pontos na mesma reta não há triangulação de Delaunay (a noção de triangulação é degenerada para este caso). Para quatro ou mais pontos no mesmo círculo (por exemplo, os vértices de um retângulo), a triangulação de Delaunay não é única: cada uma das duas triangulações possíveis que dividem o quadrilátero em dois triângulos satisfaz a "condição de Delaunay", isto é, a exigência de que os circuncírculos de todos os triângulos tenham interiores vazios.

Ao considerar esferas circunscritas, a noção de triangulação de Delaunay se estende a três dimensões ou mais. Generalizações são possíveis para métricas diferentes da distância euclidiana. No entanto, nesses casos, uma triangulação de Delaunay não é garantida de existir ou ser única.

Relação com o diagrama de Voronoi

A Triangulação Delaunay com todos os circuncírculos e seus centros (em vermelho).

Conectar os centros das circuncírculos produz o diagrama Voronoi (em vermelho).

A triangulação de Delaunay de um conjunto de pontos discretos P em posição geral corresponde ao gráfico dual do diagrama de Voronoi para P. Os circuncentros dos triângulos de Delaunay são os vértices do diagrama de Voronoi. No caso 2D, os vértices de Voronoi são conectados por arestas, que podem ser derivadas de relações de adjacência dos triângulos de Delaunay: Se dois triângulos compartilham uma aresta na triangulação de Delaunay, seus circuncentros devem ser conectados com uma aresta na tesselação de Voronoi.

Casos especiais em que essa relação não é válida ou é ambígua, incluem casos como:

• Três ou mais pontos de collinear, onde as circuncírculos são de raios infinitos.
• Quatro ou mais pontos em um círculo perfeito, onde a triangulação é ambígua e todos os circuncentros são trivialmente idênticos.
• As bordas do diagrama Voronoi indo para o infinito não são definidas por esta relação em caso de um conjunto finito P. Se a triangulação Delaunay é calculada usando o algoritmo Bowyer-Watson, então os circuncentros de triângulos com um vértice comum com o triângulo "super" devem ser ignorados. As bordas que vão ao infinito começam de um circuncentro e são perpendiculares à borda comum entre o triângulo mantido e ignorado.

D-dimensional Delaunay

Para um conjunto P de pontos no ( d-dimensional) Espaço euclidiano, uma triangulação de Delaunay é uma triangulação DT(P) tal que não ponto em P está dentro da circun-hiperesfera de qualquer d -simplex em DT(P). Sabe-se que existe uma triangulação Delaunay única para P se P é um conjunto de pontos em posição geral; isto é, o casco afim de P é d-dimensional e nenhum conjunto de d + 2 pontos em P estão no limite de uma bola cujo interior não intercepta P.

O problema de encontrar a triangulação Delaunay de um conjunto de pontos no espaço euclidiano d-dimensional pode ser convertido no problema de encontrar o envoltório convexo de um conjunto de pontos em (d + 1) espaço dimensional. Isso pode ser feito dando a cada ponto p uma coordenada extra igual a |p|², virando assim em um hiper-parabolóide (isso é chamado de "lifting"); tomando o lado inferior do casco convexo (já que a tampa superior está voltada para cima, longe da origem, e deve ser descartada); e mapear de volta para o espaço d-dimensional excluindo a última coordenada. Como o casco convexo é único, a triangulação também é, assumindo que todas as facetas do casco convexo são simplices. Facetas não-simpliciais ocorrem apenas quando d + 2 dos pontos originais estão no mesmo d-hiperesfera, ou seja, os pontos não estão em posição geral.

Propriedades

Exemplo de passos

Cada quadro da animação mostra uma triangulação Delaunay dos quatro pontos. A meio caminho, a borda triangulante vira mostrando que a triangulação Delaunay maximiza o ângulo mínimo, não o comprimento de borda dos triângulos.

Seja n o número de pontos e d o número de dimensões.

• A união de todos os simplices na triangulação é o casco convexo dos pontos.
• A triangulação Delaunay contém O(n⌈ ⌈ D/2⌉ ⌉ ){displaystyle Oleft(n^{lceil d/2rceil }right)} Simplices.
• No avião (D = 2), se houver b) vértices no casco convexo, então qualquer triangulação dos pontos tem no máximo 2n – 2 – b) triângulos, além de uma face exterior (ver característica Euler).
• Se os pontos forem distribuídos de acordo com um processo de Poisson no plano com intensidade constante, então cada vértice tem em média seis triângulos circundantes. Mais geralmente para o mesmo processo em D dimensões o número médio de vizinhos é uma constante dependendo apenas de D.
• No plano, a triangulação Delaunay maximiza o ângulo mínimo. Comparado a qualquer outra triangulação dos pontos, o menor ângulo na triangulação Delaunay é pelo menos tão grande quanto o menor ângulo em qualquer outro. No entanto, a triangulação Delaunay não minimiza necessariamente o ângulo máximo. A triangulação Delaunay também não minimiza necessariamente o comprimento das bordas.
• Um círculo circunscrevendo qualquer triângulo Delaunay não contém quaisquer outros pontos de entrada em seu interior.
• Se um círculo que passa por dois dos pontos de entrada não contém quaisquer outros pontos de entrada em seu interior, então o segmento que conecta os dois pontos é uma borda de uma triangulação Delaunay dos pontos dados.
• Cada triângulo da triangulação Delaunay de um conjunto de pontos em Despaços dimensionais corresponde a uma faceta de casco convexo da projeção dos pontos em um (D + 1) parabolóide dimensional, e vice-versa.
• O vizinho mais próximo b) a qualquer ponto p está em uma borda B. na triangulação Delaunay desde o gráfico vizinho mais próximo é um subgrafo da triangulação Delaunay.
• A triangulação Delaunay é um spanner geométrico: No avião (D = 2), o caminho mais curto entre dois vértices, ao longo das bordas de Delaunay, é conhecido por não ser mais de 1.998 vezes a distância euclidiana entre eles.

Definição visual de Delaunay: Flipping

Das propriedades acima surge uma característica importante: Olhando para dois triângulos △ABD, △BCD com o comum edge BD (ver figuras), se a soma dos ângulos α + γ ≤ 180°, os triângulos atendem à condição de Delaunay.

Esta é uma propriedade importante porque permite o uso de uma técnica de inversão. Se dois triângulos não atendem à condição de Delaunay, trocando a aresta comum BD para a borda comum AC produz dois triângulos que satisfazem a condição de Delaunay:

• 

  Esta triangulação não atende a condição Delaunay (a soma de α e γ é maior que 180°).

• 

  Este par de triângulos não atende a condição Delaunay (há um ponto dentro do interior do circuncírculo).

• 

  Violação a borda comum produz uma triangulação Delaunay válida para os quatro pontos.

Essa operação é chamada de flip e pode ser generalizada para três dimensões ou mais.

Algoritmos

Precisamos de uma maneira robusta e rápida de detectar se ponto D encontra-se na circuncisão A, B, C

Muitos algoritmos para computar triangulações de Delaunay dependem de operações rápidas para detectar quando um ponto está dentro do círculo circunscrito de um triângulo e uma estrutura de dados eficiente para armazenar triângulos e arestas. Em duas dimensões, uma maneira de detectar se o ponto D está no circuncírculo de A, B, C é avaliar o determinante:

0end{aligned}}}" xmlns="http://www.w3.org/1998/Math/MathML">|AxASim.Ax2+ASim.21BxBSim.Bx2+BSim.21CxCSim.Cx2+CSim.21DxDSim.Dx2+DSim.21|= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =|Ax- Sim. - Sim. DxASim.- Sim. - Sim. DSim.(Ax2- Sim. - Sim. Dx2)+(ASim.2- Sim. - Sim. DSim.2)Bx- Sim. - Sim. DxBSim.- Sim. - Sim. DSim.(Bx2- Sim. - Sim. Dx2)+(BSim.2- Sim. - Sim. DSim.2)Cx- Sim. - Sim. DxCSim.- Sim. - Sim. DSim.(Cx2- Sim. - Sim. Dx2)+(CSim.2- Sim. - Sim. DSim.2)|>0,,, },,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,;0end{aligned}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4283d2ae1914af7b7c13c9debc8eaa91cff00bca" style="vertical-align: -12.338ex; margin-top: -0.281ex; width:55.627ex; height:25.843ex;"/>

Quando A, B, C são classificados no sentido anti-horário, esse determinante é positivo somente se D está dentro do circuncírculo.

Algoritmos de inversão

Como mencionado acima, se um triângulo não é Delaunay, podemos virar uma de suas arestas. Isso leva a um algoritmo direto: construa qualquer triangulação dos pontos e, em seguida, inverta as arestas até que nenhum triângulo seja não-Delaunay. Infelizmente, isso pode levar Ω(n²) viradas de borda. Embora esse algoritmo possa ser generalizado para três dimensões ou mais, sua convergência não é garantida nesses casos, pois está condicionada à conectividade do gráfico flip subjacente: esse gráfico é conectado para conjuntos bidimensionais de pontos, mas pode ser desconectado em dimensões superiores.

Incremental

A maneira mais direta de calcular eficientemente a triangulação de Delaunay é adicionar repetidamente um vértice por vez, retriangulando as partes afetadas do grafo. Quando um vértice v é adicionado, dividimos em três o triângulo que contém v, então aplicamos o algoritmo flip. Feito ingenuamente, isso levará O(n) tempo: procuramos em todos os triângulos para encontrar aquele que contém v, então podemos virar todos os triângulos. Em seguida, o tempo de execução geral é O(n²).

Se inserirmos vértices em ordem aleatória, verifica-se (por meio de uma prova um tanto complicada) que cada inserção inverterá, em média, apenas O(1) triângulos – embora às vezes ele vai virar muito mais. Isso ainda deixa o tempo de localização do ponto para melhorar. Podemos armazenar o histórico das divisões e flips realizados: cada triângulo armazena um ponteiro para os dois ou três triângulos que o substituíram. Para encontrar o triângulo que contém v, começamos em um triângulo raiz e seguimos o ponteiro que aponta para um triângulo que contémv, até encontrarmos um triângulo que ainda não foi substituído. Em média, isso também levará O(log n) tempo. Em todos os vértices, isso leva O(n log n) tempo. Embora a técnica se estenda para dimensões superiores (como provado por Edelsbrunner e Shah), o tempo de execução pode ser exponencial na dimensão, mesmo que a triangulação final de Delaunay seja pequena.

O algoritmo de Bowyer–Watson fornece outra abordagem para construção incremental. Ele oferece uma alternativa à inversão de arestas para calcular os triângulos de Delaunay contendo um vértice recém-inserido.

Infelizmente, os algoritmos baseados em inversão são geralmente difíceis de paralelizar, pois adicionar algum ponto específico (por exemplo, o ponto central de uma roda de carroça) pode levar a até O(n) flips consecutivos. Blelloch et ai. propuseram outra versão do algoritmo incremental baseado em rip-and-tent, que é prático e altamente paralelizado com span polilogarítmico.

Dividir e conquistar

Um algoritmo de divisão e conquista para triangulações em duas dimensões foi desenvolvido por Lee e Schachter e aprimorado por Guibas e Stolfi e posteriormente por Dwyer. Neste algoritmo, desenha-se recursivamente uma linha para dividir os vértices em dois conjuntos. A triangulação de Delaunay é calculada para cada conjunto e, em seguida, os dois conjuntos são mesclados ao longo da linha de divisão. Usando alguns truques inteligentes, a operação de mesclagem pode ser feita no tempo O(n), então o tempo total de execução é O(n registro n).

Para certos tipos de conjuntos de pontos, como uma distribuição aleatória uniforme, escolhendo de forma inteligente as linhas de divisão, o tempo esperado pode ser reduzido para O(n log n) enquanto ainda mantém o desempenho de pior caso.

Um paradigma de dividir e conquistar para realizar uma triangulação em dimensões d é apresentado em "DeWall: A fast divide e conquistar o algoritmo de triangulação de Delaunay em E^d" por P. Cignoni, C. Montani, R. Scopigno.

O algoritmo de divisão e conquista demonstrou ser a técnica de geração de DT mais rápida sequencialmente.

Sweephull

Sweephull é uma técnica híbrida para triangulação Delaunay 2D que usa um casco de varredura radialmente propagado e um algoritmo de inversão. O casco de varredura é criado sequencialmente iterando um conjunto de pontos 2D classificados radialmente e conectando triângulos à parte visível do casco convexo, o que fornece uma triangulação sem sobreposição. Pode-se construir um casco convexo dessa maneira, desde que a ordem dos pontos garanta que nenhum ponto caia dentro do triângulo. Mas, a classificação radial deve minimizar a inversão por ser altamente Delaunay para começar. Isso é então emparelhado com uma etapa final de inversão de triângulo iterativa.

Aplicativos

A árvore geradora mínima euclidiana de um conjunto de pontos é um subconjunto da triangulação de Delaunay dos mesmos pontos, e isso pode ser explorado para calculá-la eficientemente.

Para modelar terrenos ou outros objetos a partir de uma nuvem de pontos, a triangulação de Delaunay fornece um bom conjunto de triângulos para usar como polígonos no modelo. Em particular, a triangulação de Delaunay evita triângulos estreitos (pois eles têm circuncírculos grandes em comparação com sua área). Ver rede irregular triangular.

As triangulações de Delaunay podem ser usadas para determinar a densidade ou intensidade de amostragens de pontos por meio do estimador de campo de mosaico de Delaunay (DTFE).

Uma triangulação Delaunay de um conjunto aleatório de 100 pontos em um avião.

As triangulações de Delaunay são frequentemente usadas para gerar malhas para solucionadores de espaço discretizado, como o método de elementos finitos e o método de volumes finitos de simulação física, por causa da garantia de ângulo e porque algoritmos de triangulação rápida foram desenvolvidos. Tipicamente, o domínio a ser malhado é especificado como um complexo simplicial grosseiro; para que a malha seja numericamente estável, ela deve ser refinada, por exemplo, usando o algoritmo de Ruppert.

A popularidade crescente do método dos elementos finitos e das técnicas do método dos elementos de contorno aumenta o incentivo para melhorar os algoritmos de malha automática. No entanto, todos esses algoritmos podem criar elementos de grade distorcidos e até inutilizáveis. Felizmente, existem várias técnicas que podem pegar uma malha existente e melhorar sua qualidade. Por exemplo, a suavização (também conhecida como refinamento de malha) é um desses métodos, que reposiciona os nós para minimizar a distorção do elemento. O método da grade estendida permite a geração de malhas pseudo-regulares que atendem aos critérios de Delaunay de maneira fácil e rápida em uma solução de uma etapa.

A triangulação restrita de Delaunay encontrou aplicações no planejamento de caminhos em direção automatizada e levantamento topográfico.