Gerador de Triangulação de Delaunay

O Gerador de Triangulação de Delaunay transforma qualquer conjunto de pontos 2D na triangulação única que maximiza o menor ângulo interno — o padrão ouro para modelagem de terreno, geração de malha de elementos finitos, interpolação pelo vizinho mais próximo e salas de aula de geometria computacional. Cole as coordenadas (ou escolha um padrão de início rápido) e a ferramenta executa o algoritmo de Bowyer-Watson no lado do servidor, colore cada triângulo por sua qualidade e mostra a propriedade do círculo circunscrito vazio, o fecho convexo e o dual de Voronoi sob demanda.

Como Ler a Malha Gerada

O que Torna este Triangulador de Delaunay Diferente

O que É uma Triangulação de Delaunay?

Dado um conjunto de pontos 2D, geralmente existem muitas maneiras de conectá-los em uma triangulação (um ladrilhamento completo de seu fecho convexo por triângulos sem sobreposições ou lacunas). A triangulação de Delaunay, batizada em homenagem ao matemático russo Boris Delaunay (1934), é aquela que satisfaz a propriedade do círculo circunscrito vazio: para cada triângulo na malha, o círculo que passa por seus três vértices não contém outros pontos de entrada. Esta única propriedade tem uma consequência notável: entre todas as triangulações do mesmo conjunto de pontos, a de Delaunay maximiza o menor ângulo interno. Em bom português, produz os triângulos mais "gordos" e "equilibrados" possíveis.

Como Funciona o Algoritmo de Bowyer-Watson

1. Cerque todos os pontos de entrada com um supertriângulo muito grande.
2. Insira um ponto de entrada de cada vez. Para cada novo ponto, encontre cada triângulo existente cujo círculo circunscrito contenha o novo ponto — estes são os triângulos "ruins".
3. Remova os triângulos ruins. O buraco que eles deixam para trás tem um limite poligonal.
4. Conecte o novo ponto a cada aresta desse limite, formando novos triângulos.
5. Depois que todos os pontos forem inseridos, remova qualquer triângulo que ainda toque um vértice do supertriângulo. O que resta é a triangulação de Delaunay do conjunto de pontos original.

Onde a Triangulação de Delaunay É Usada

• Modelagem de terreno (GIS): amostras de elevação (normalmente com espaçamento irregular, como estações de terreno) são conectadas em uma Rede Irregular Triangulada (TIN) para consultas de elevação, sombreamento e visualização 3D.
• Análise de elementos finitos: triângulos de Delaunay bem formados geram soluções numéricas estáveis para equações diferenciais parciais em mecânica, transferência de calor e eletromagnetismo.
• Computação gráfica: geração de malhas para renderização, esqueleto de personagens (rigging) e terreno procedural — a garantia de "nenhum triângulo fino" de Delaunay evita artefatos de estiramento de textura.
• Interpolação por vizinho natural: superfícies suaves são reconstruídas a partir de amostras dispersas computando os vizinhos naturais de cada ponto de consulta por meio do dual de Voronoi.
• Aulas de geometria computacional: um algoritmo canônico com conexões profundas com fechos convexos, diagramas de Voronoi, localização de pontos e divisão e conquista.
• Fatiadores de impressão 3D e trajetórias de ferramentas CNC: O Delaunay 2D (e seu primo 3D, a tetraedrização de Delaunay) serve como base para muitas estratégias de fatiamento e preenchimento.

Delaunay vs Voronoi: Dois Lados da Mesma Moeda

O diagrama de Voronoi particiona o plano em uma célula por ponto de entrada, onde cada célula contém tudo o que está mais próximo de seu ponto do que de qualquer outro. Conecte os pontos cujas células compartilham um limite e você obterá exatamente a triangulação de Delaunay. Por outro lado, os circuncentros dos triângulos de Delaunay adjacentes, unidos por segmentos de reta, formam as arestas de Voronoi. Alterne "Dual de Voronoi" nesta ferramenta para ver as linhas tracejadas laranjas sobrepostas no mesmo gráfico — cada aresta de Delaunay cruza exatamente uma aresta de Voronoi em ângulos retos.

Qualidade, Triângulos Finos e Refinamento de Malha

Delaunay maximiza o ângulo interno mínimo global, mas não pode corrigir uma distribuição de pontos fundamentalmente ruim. Se os seus pontos de entrada forem quase colineares, agrupados ou deixarem grandes regiões vazias, alguns triângulos ainda serão finos (ângulo mínimo abaixo de 20°). A correção é a inserção de pontos de Steiner: algoritmos como o algoritmo de Ruppert e o segundo algoritmo de Chew adicionam iterativamente novos pontos no circuncentro de triângulos finos, retriangulando a cada vez, até que cada triângulo atinja um limite de qualidade planejado. Este gerador mostra quais triângulos são finos para que você saiba onde adicionar pontos de Steiner se quiser uma malha mais fina.

Exemplo Prático

Clique na predefinição "Círculo + centro". A ferramenta coloca 18 pontos ao redor de um círculo e 1 ponto no centro, e os triangula. O resultado é um leque perfeito de 18 triângulos isósceles que se encontram no centro — cada um tem ângulos de 10° na borda e 80°–80° no centro. O pior ângulo mínimo é 10°, todos os triângulos são sinalizados como finos e o histograma mostra tudo no intervalo de 0°–10°. O exemplo é um ótimo caso de ensino: até mesmo a triangulação ótima de Delaunay pode ter triângulos finos quando a entrada os força. Agora clique em "Nuvem aleatória" — o mesmo algoritmo produz triângulos bem formados porque os pontos estão espalhados uniformemente, e o histograma se desloca para a direita.

Equívocos Comuns

• "A triangulação de Delaunay é única": geralmente sim, mas se quatro pontos de entrada forem cocirculares (todos estiverem no mesmo círculo), existem duas triangulações de Delaunay válidas para esse grupo. O gerador escolhe uma de forma consistente.
• "Mais pontos sempre significam melhor qualidade": adicionar pontos mal posicionados pode introduzir novos triângulos finos. Os algoritmos de pontos de Steiner posicionam os novos pontos com cuidado — nos circuncentros — para que a qualidade certamente melhore.
• "Delaunay é o mesmo que um fecho convexo": não. O fecho convexo é o limite externo; a triangulação de Delaunay preenche o interior com triângulos.
• "Todas as triangulações parecem quase iguais": a diferença é dramática. Uma "inversão" a partir de uma aresta de Delaunay pode transformar um triângulo de 25° em um de 5°. O mapa de calor de qualidade da ferramenta torna a diferença visível.

Perguntas Frequentes