Introdução
Há diversas formas de triangularizar um conjunto de pontos. Dentre elas, a triangulação de Delaunay tem destaque na geração de malhas para computação gráfica, pois ela maximiza o menor ângulo dos triângulos que a compõem. Como motivação, considere triangulações de um conjunto de pontos de um determinado relevo, onde os pontos centrais representam os pontos mais altos.
Ambas são triangulações válidas. No entanto, uma delas aparenta ser mais natural devido ao seu triângulo central não estar tão achatado quanto o da outra. Esse achatamento está diretamente relacionado ao menor ângulo do triângulo, sendo possível comparar a qualidade entre essas triangulações a partir desse ângulo.
Delaunay: a triangulação ideal
Considere Υ(T) = (β1, β2, β3, ..., β3t) o vetor dos ângulos de uma triangulação T em ordem crescente. Uma triangulação T1 é dita melhor que T2 se Υ(T1) > Υ(T2), segundo a ordem lexicográfica. Ao comparar duas triangulações, avalia-se inicialmente o menor ângulo; caso eles sejam iguais, passa-se ao segundo menor, e assim sucessivamente.
Partindo de uma triangulação não ideal, é possível chegar a uma versão melhorada através de flips de arestas, de forma que o menor ângulo dos novos triângulos seja maximizado. Arestas que aumentam os ângulos mínimos ao serem flipadas são chamadas de arestas ilegais e podem ser identificadas utilizando o Teorema de Tales. Através de flips sucessivos dessas arestas ilegais, obtém-se a triangulação ideal, conhecida como triangulação de Delaunay.
A triangulação de Delaunay é considerada ideal pois maximiza o menor ângulo dos triângulos, minimiza o maior circuncírculo e, consequentemente, produz triângulos menos achatados. Por definição, um triângulo é chamado de Delaunay se seus vértices pertencem a um conjunto finito de pontos P e se o seu circuncírculo é vazio, isto é, não contém nenhum outro ponto de P em seu interior.
Malha de Delaunay
Malhas de Delaunay são excelentes opções quando se deseja evitar triângulos com ângulos muito pequenos. Existem diversos métodos para a obtenção dessas malhas; neste trabalho, serão abordados os métodos de Flipping e Parabolic Lifting.
Parabolic Lifting
Considere um conjunto P de pontos no plano e um paraboloide acima desse plano. O método de Parabolic Lifting consiste em elevar cada ponto do plano para o espaço tridimensional. Um ponto (x, y) ∈ R² é transformado em (x, y, x² + y²) ∈ R³, posicionando todos os pontos sobre um paraboloide convexo.
Em seguida, constrói-se o fecho convexo dos pontos elevados sobre o paraboloide. A projeção do casco convexo inferior de volta ao plano resulta em uma triangulação de Delaunay.
Flipping
O método de Flipping é de fácil visualização e bastante intuitivo. Inicialmente, constrói-se um grande triângulo que contenha todos os pontos do conjunto. Em seguida, escolhe-se um ponto e conecta-se esse ponto aos vértices do triângulo no qual ele está inserido, subdividindo-o.
Esse processo é repetido para os pontos restantes. Sempre que surgirem arestas ilegais, realizam-se flips até que todas sejam eliminadas. Caso um ponto esteja localizado exatamente sobre uma aresta, essa aresta é removida e o ponto é conectado aos quatro vértices acessíveis, formando novos triângulos.
Ao final do processo, remove-se o triângulo inicial que envolvia todos os pontos. A malha obtida é uma malha de Delaunay.
Aplicação
Triângulos pouco achatados tornam as malhas de Delaunay extremamente úteis em problemas de interpolação. Considere novamente duas triangulações de um relevo. Suponha que a altura de um ponto intermediário seja desconhecida.
Ao realizar a interpolação pela média dos pontos conectados, obtêm-se valores muito distintos a depender da triangulação utilizada. A triangulação que maximiza o menor ângulo tende a conectar o ponto a vizinhos mais próximos, produzindo resultados mais realistas e coerentes com a geometria do relevo.
Malhas de Delaunay Conformadas (CDT)
A construção de uma CDT começa com a geração de uma triangulação de Delaunay sobre o conjunto de pontos PPP. Em seguida, cada segmento restrito s ∈ S é imposto à malha: se ele não estiver presente, identifica-se os triângulos que o intersectam e inserem-se pontos Steiner ao longo do segmento até que ele possa ser representado como uma aresta da triangulação. Após incorporar todos os segmentos, aplica-se um refinamento de qualidade (como os métodos de Ruppert ou Chew) para remover triângulos pobres e melhorar a distribuição dos elementos. O resultado é uma triangulação que respeita o contorno e garante boa qualidade geométrica.
A construção de uma CDT começa com a geração de uma triangulação de Delaunay sobre um conjunto de pontos. Em seguida, cada segmento restrito é imposto à malha. Caso ele não esteja presente, inserem-se pontos de Steiner ao longo do segmento até que ele possa ser representado como uma aresta da triangulação. Após isso, aplica-se um refinamento de qualidade, como os métodos de Ruppert ou Chew.
Implementações do Código
parabolic_lifting: parabolic_lifting: Este código aplica a técnica de elevar pontos 2D para 3D sobre um paraboloide. Dado um ponto (x,y) do plano ele é transformado em um ponto tridimensional: de forma:(x,y,x +y2 ). Essa transformação vai colocar todos os pontos sobre um paraboloide2 convexo. Ao elevar pontos nessa superfície faz com que a triangulação de Delauney no plano corresponda exatamente às faces da casca convexa inferior. Assim, as propriedades complexas difíceis de se verificar em 2D tornam-se mais simples na convexidade 3D.
delaunay_triangulation:delauney_triangulation: Essa função implementa a técnica para construir a trianuglação 2D para um conjunto de pontos, explorando a propriedade fundamental que um conjunto de pontos no plano é equivalente a projeção do Lower Hulln (casco inferior) do casco convexo dos pontos após serem elevados a R3 por um mapeamento parabólico (a função parabolic lifting). Dessa forma, o método transforma o problema de otimização geométrixa 2D em um problema convexo 3D. Portanto, a função parabolic_lifting irá realizar o mapeamento parabólica, enquanto a função delaunay_triangulation aplica o casco convexo e extrai os triângulos válidos
]
O que é CDT?
A Triangulação de Delaunay com Restrição, ou CDT, é uma extensão da triangulação de Delaunay desenvolvida para lidar com domínios que possuem contornos, interfaces internas, furos ou qualquer estrutura geométrica que deve ser preservada exatamente. Enquanto a triangulação de Delaunay comum busca apenas otimizar propriedades geométricas, como evitar triângulos muito agudos, a CDT adapta essa triangulação para incorporar obrigatoriamente as fronteiras definidas pelo problema.
Sua origem está na necessidade de aplicar Delaunay em situações reais, onde a geometria não é simplesmente um conjunto de pontos, mas sim um domínio com limites bem definidos. No contexto da morfologia computacional, a CDT é especialmente útil porque permite representar regiões complexas antes de aplicar operações morfológicas, garantindo que a análise de forma, a segmentação ou a reconstrução estrutural ocorram de modo consistente com a geometria verdadeira do domínio.
O que é PLC?
O Piecewise Linear Complex, ou PLC, é a estrutura que descreve com precisão a geometria do domínio onde a triangulação será feita. Ele é formado por vértices e segmentos que representam bordas, interfaces internas, furos e qualquer elemento que precisa ser preservado. Em essência, o PLC reúne todas as restrições que a CDT deve obrigatoriamente incorporar.
O PLC também introduz o conceito de visibilidade, essencial quando o domínio possui fronteiras e obstáculos internos. Dois pontos são considerados visíveis se o segmento que os conecta está inteiramente contido no domínio e não é interceptado por nenhum segmento do PLC. Essa noção é fundamental para adaptar o critério clássico do círculo vazio às CDTs.
Implementação da Recuperação de Restrições
Quando um segmento do contorno precisa ser incorporado à triangulação, o passo essencial é eliminar todas as arestas que o interceptam. Cada aresta que cruza um segmento do PLC viola a CDT e precisa ser removida. Para isso, o algoritmo utiliza o flip de diagonal.
Ao identificar uma aresta que cruza o segmento restrito, analisam-se os dois triângulos adjacentes, que formam um quadrilátero convexo. A diagonal que causa a interseção é substituída pela outra possível, gerando dois novos triângulos que não cruzam mais o segmento do PLC.
Esse processo é repetido até que o segmento restrito esteja completamente presente na malha.
Em seguida, as novas arestas são verificadas para restaurar a condição de Delaunay sempre que
possível dentro das restrições impostas.
Refinamento de Triangulações de Delaunay em 2D
Depois de construir uma triangulação de Delaunay para o conjunto de pontos do “lago”, o código aplica dois esquemas de refinamento de malha: um no estilo de Chew e outro no estilo de Ruppert. O objetivo em ambos os casos é melhorar a qualidade dos triângulos, controlando ângulos muito agudos e respeitando a fronteira do polígono que representa o lago. A triangulação de Delaunay em si é obtida pela função delaunay_triangulation, que usa o parabolic lifting e o casco convexo em (R^3). Sobre esta triangulação, as funções chew_refinement e ruppert_refinement iterativamente inserem novos pontos, recalculando a triangulação a cada passo.
Critério de Qualidade
Na implementação, o critério de qualidade é baseado no ângulo mínimo de cada triângulo. Esse cálculo é feito pela função triangle_geom(pts, tri), que recebe o vetor de pontos pts e um triângulo tri (índices dos vértices) e devolve três informações: a área do triângulo; o menor ângulo interno (em graus);o comprimento da maior aresta.
Para calcular os ângulos, a função usa a lei dos cossenos. Dados os comprimentos das arestas (a), (b) e (c), o ângulo oposto ao lado (a), por exemplo, é obtido por
cos(theta_a) = {b^2 + c^2 - a^2}/{2bc},
e depois (theta_a = arccos(cos(theta_a))), convertido para graus. O menor entre os três ângulos é tomado como medida de qualidade: quanto menor esse valor, mais fino e pior é o triângulo.
A função get_bad_triangles(pts, tris, min_angle_deg, poly, max_bad) percorre todos os triângulos tris e
1.Calcula o centroide do triângulo e verifica se ele está dentro do polígono do lago usando point_in_polygon. Triângulos fora do domínio são ignorados.
2. Usa triangle_geom para obter a área e o ângulo mínimo
3. Descarta triângulos quase degenerados (área muito pequena).
4. Marca como “ruins” aqueles cujo ângulo mínimo é menor que o limiar min_angle_deg (por exemplo, 28° ou 30°).
A função devolve a lista de índices desses triângulos ruins, ordenados pelo ângulo mínimo (do pior para o menos ruim) e, opcionalmente, limitada por max_bad para não refinar tudo de uma vez
Cálculo do circuncentro e pontos de refinamento
Quando um triângulo é identificado como ruim, a posição natural para inserir um novo vértice é o seu circuncentro. Isso é feito pela função triangle_circumcenter(pts, tri):
● primeiro, ela chama circumcircle(p1, p2, p3), que recebe as coordenadas dos três vértices e resolve analiticamente o sistema das mediatrizes, obtendo:
○ o centro ((u_x, u_y)) do circuncírculo;
○ o raio ao quadrado (r^2);
● se o triângulo for degenerado (determinante próximo de zero), a função retorna o baricentro como fallback;
● caso contrário, devolve o ponto ((c_x, c_y)) correspondente ao circuncentro
Esse ponto é, em princípio, o candidato a ser inserido na malha para eliminar o triângulo skinny. No entanto, antes de inseri-lo, o código verifica se o circuncentro está dentro do lago (point_in_polygon(cc, poly)); circuncentros fora do domínio são descartados.
Refinamento tipo Chew
A função chew_refinement(points, segments, poly, min_angle_deg, iterations, max_new_each) implementa um refinamento simplificado no estilo de Chew. A lógica é:
Recebe:
○ points: conjunto inicial de pontos (fronteira + pontos internos);
○ segments: lista de arestas que representam a fronteira do lago;
○ poly: polígono do lago (para o teste ponto-no-polígono);
○ parâmetros de qualidade: min_angle_deg (ângulo mínimo desejado), iterations (número máximo de ciclos) e max_new_each (limite de novos pontos por iteração).
Recalcula a triangulação de Delaunay com delaunay_triangulation(pts).
○ Usa get_bad_triangles para identificar triângulos com ângulo mínimo abaixo de min_angle_deg, limitando o número de triângulos examinados a max_new_each.
○ Se não há novos pontos a inserir, o processo é interrompido. ○ Caso contrário, os novos pontos são empilhados em pts via np.vstack, e passa-se para a próxima iteração.
4. Ao terminar todas as iterações (ou quando não há mais triângulos ruins), o código faz uma última chamada a delaunay_triangulation e recover_constraints, resultando em uma malha refinada. A função retorna pts (pontos finais) e tris (triângulos finais).
Nesse esquema, o refinamento atua exclusivamente inserindo circuncentros de triângulos ruins. As fronteiras são preservadas pela rotina de recuperação de restrições, mas não há ainda o tratamento explícito de “segmentos invadidos” típico de Rupper
Para lidar com fronteiras de forma mais sofisticada, o código introduz o conceito de segmento encroached na função find_encroached_segment(candidate_point, pts, segments). A ideia é aproximar o critério do círculo diametral:
● para cada segmento ((a, b)) da lista segments, calcula-se:
,○ o ponto médio mid = 0.5 * (pa + pb);
○ o raio ao quadrado do círculo diametral, r2 = ||pa - mid||² (metade do comprimento do segmento ao quadrado);
○ a distância ao quadrado do candidato ao ponto médio, d2 = ||candidate_point - mid||².
● se d2 r2 - 1e-10, interpreta-se que o ponto candidato está dentro do círculo diametral do segmento ((a, b)); isso caracteriza o segmento como encroached e a função devolve esse segmento.
Se nenhum segmento for invadido, a função retorna None. Esse teste é usado para decidir se o refinamento deve inserir um circuncentro diretamente ou, antes disso, subdividir algum segmento de fronteira.
Refinamento tipo Ruppert
A função ruppert_refinement(points, segments, poly, min_angle_deg, iterations, max_new_each) usa a mesma base que chew_refinement, mas incorpora o tratamento de segmentos encroached, aproximando o algoritmo clássico de Ruppert:
○ pts começa com os pontos iniciais (fronteira + pontos internos);
○ segs é a lista de segmentos de fronteira do lago
○ Calcula a triangulação de Delaunay com delaunay_triangulation(pts).
○ Recupera as restrições com recover_constraints(pts, tris, segs).
○ Identifica triângulos ruins com get_bad_triangles, como antes.
Para cada triângulo ruim:
○ Calcula o circuncentro cc
○ Descarta circuncentros fora do lago (point_in_polygon(cc, poly)).
○ Chama find_encroached_segment(cc, pts, segs)
■ se não existir segmento encroached, o circuncentro é aceito como novo ponto de refinamento (new_pts.append(cc)).
■ se existir um segmento encroached ((a, b)), o código
calcula o ponto médio mid = 0.5 * (pts[a] + pts[b])
■ verifica se o ponto médio está dentro do lago;
■ reserva um índice para o novo ponto (será len(pts) + len(new_pts));
■ substitui o segmento ((a, b)) por dois subsegmentos ((a, new_index)e(new_index, b)emnew_segs`;
■ adiciona o ponto médio à lista de novos pontos
4. Ao final da iteração
○ se não há novos pontos, o refinamento é encerrado;
○ caso contrário, empilha-se new_pts em pts e, se houve encroachment, atualiza-se a lista de segmentos segs = new_segs.
Ao final de todas as iterações (ou na interrupção antecipada), faz-se uma última triangulação com delaunay_triangulation e recover_constraints, obtendo-se a malha refinada e a nova lista de segmentos. A função retorna pts, tris e segs.
Em resumo, o refinamento tipo Ruppert implementado segue a lógica:
● prioridade para segmentos encroached: se o circuncentro invadir o círculo diametral de algum segmento, o segmento é subdividido;
● só quando não há encroachment é que o circuncentro é de fato inserido.
Isso faz com que a fronteira do lago seja refinada onde necessário, evitando triângulos de baixa qualidade junto à borda.
Geração das figuras de evolução da malha
Por fim, a função generate_all() organiza a aplicação desses métodos e gera as imagens que ilustram a evolução da malha:
1. generate_lake_polygon constrói um polígono irregular (“lago”) em ([0,1]^2).
2. sample_points_in_polygon adiciona pontos internos aleatórios.
3. A lista segments contém os segmentos de fronteira do lago, conectando os vértices da borda.
4. São geradas, em sequência
○ a triangulação de Delaunay sem restrições;
○ a triangulação com restrição (CDT aproximada
○ a malha refinada por chew_refinement;
○ a malha refinada por ruppert_refinement.
Cada uma dessas malhas é desenhada por plot_triangulation, que plota apenas triângulos cujo centroide está dentro do lago, desenha os segmentos de fronteira e salva o resultado em arquivos PNG. Essas imagens são usadas para visualizar o efeito do refinamento: redução de triângulos com ângulos muito agudos e melhor adaptação da malha à geometria do domínio
Autores
Trabalho desenvolvido por alunos da disciplina de Introdução à Modelagem, abordando conceitos de Triangulação de Delaunay, CDT, PLC e refinamento de malhas.
Autores:
• João Pedro Pereira Balieiro:elaboração dos textos, slides,Código e apresentação
• Millena Farias dos Santos: desenvolvimento dos textos e slides
• Mariana Barbosa Queroz: desenvolvimento dos textos, slides, apresentação e homepage
•Bruno Mendonça: desenvolvimento dos textos, slides e apresentação
Fontes e Referências
BERG, M. et al. Computational Geometry: Algorithms and Applications.
Lecture Notes on
Delaunay Mesh Generation:Jonathan Richard Shewchuk
February 5, 2012
Desenvolvimento de um gerador de malhas
Delaunay em três dimensões:Bruno Nogueira Machadobr>