Triangulação de Delauney
Um pedaço da superfície terrestre é chamado de terreno. Um terreno é uma
superfície 2-dimensional em um espaço 3-dimensional com uma propriedade especial:
cada linha vertical intercepta o terreno em um ponto. Formalmente, um terreno é um
grafo da função
que atribui uma altura f(p) para cada ponto p no
domínio, A, do terreno. A representação (virtual) do terreno (real) em forma de
estrutura de dados, segundo os valores da função f, é chamada de malha. Quando
unimos cada três pontos vizinhos de uma malha, de forma a representá-la por
triângulo, chamamos essa malha de malha triangular. Uma vez que a terra é redonda,
em uma escala global, esta maneira de definir a terra não é muito adequada. Mas, se
considerarmos uma escala local, essa ideia é uma boa aproximação para terrenos em
geral. Um terreno pode ser então visualizado como um desenho em perspectiva,
como mostrado na Figura 1.
Figura 1: Perspectiva de Visualização de um Terreno
Claro, não temos como saber a altura de cada ponto na superfície da terra; sabemos
apenas os valores de altura onde podemos medir. Isso significa que, quando nos
referimos acerca de algum terreno, nós sabemos apenas o valor da função f de um
conjunto finito pontos em
, que é apenas uma amostra de A. Usando a altura
em uma vizinhança, podemos inferir de alguma forma a altura de pontos que não
puderam ser medidos no domínio dentro dessa vizinhança. Entretanto, temos assim
apenas um terreno discreto, o que não parece muito natural. Assim, nossa abordagem
para aproximar um terreno por uma malha triangular é a seguinte: Inicialmente,
determinamos uma triangulação de P. Uma triangulação de P é uma subdivisão planar
cujas faces são triângulos, cujos vértices são os pontos de P. Então, levantamos cada
ponto de P até sua altura correta, mapeando assim cada triangulo na triangulação
como um triângulo no espaço 3-dimensional. A Figura 2 ilustra essa ideia:
Figura 2: Malha triangular: obtenção de um terreno poliedral a partir de uma amostra
de pontos P que aproximam um terreno.
O que é obtido no final é um terreno poliedral: um grafo de uma função contínua
linear. Assim, o terreno poliedral, chamada malha triangular, é usada como uma
aproximação do terreno original.
Resta uma questão: como triangular o conjunto de pontos P amostrados? De uma
maneira geral, isso pode ser feito de diversas maneiras. Mas qual triangulação é mais
apropriada para nossos objetivos; ou seja, para aproximar um terreno? Por maior e
melhor que tenha sido a captura dos pontos do terreno, não existe ainda nenhuma
resposta definitiva para essa questão, principalmente porque não conhecemos a altura
de cada ponto possível do terreno original, mas apenas em uma certa amostragem.
Uma vez que não conhecemos nenhuma outra informação, e a altura dos pontos
amostrados são as alturas corretas para qualquer triangulação, qualquer triangulação
pra P parece ser igualmente boa. No entanto, algumas triangulações parecem ser mais
naturais do que outras. Por exemplo, observe a Figura 3, que mostra duas
triangulações do mesmo conjunto de pontos. Observando somente as alturas dos
pontos amostrados, temos a impressão de que trata-se de uma montanha com um
certo cume. A triangulação (a) reflete esta ideia intuitiva. Por outro lado, a
triangulação (b), onde uma simples aresta foi flipada, parece ter introduzido um
grande vale exatamente no cume. Intuitivamente, a triangulação (b) parece errada.
Podemos, no entanto, assumir intuitivamente que a triangulação (a) é melhor do que a
triangulação (b)?
Figura 3: Alternando uma única aresta pode fazer uma grande diferença na
triangulação.
O problema com a triangulação (b) é que a altura do ponto q é determinada por dois
pontos que estão relativamente distantes um do outro. Isso acontece porque q está no
meio de uma aresta de dois triângulos com ângulos muito pequenos. As pequenas
espessuras desses triângulos são as causadoras desse problema. Então, intuitivamente,
parece que triangulações com menores ângulos são piores. Assim, ordenamos de
forma crescente as triangulações pelos seus ângulos para compará-las. Se os menores
ângulos de duas triangulações são idênticos, comparamos os dois próximos ângulos
nas sequencias ordenadas, e assim por diante. Uma vez que existe um número finito
de diferentes triangulações para cada amostra P, isso implica que deve haver uma
triangulação ótima, uma que maximiza os ângulos mínimos. Esta triangulação é aquela
que buscamos na construção de malhas triangulares.
Triangulação de Conjunto de Pontos Planares
Seja
um conjunto de n pontos no plano. Para definirmos
formalmente uma triangulação de P, inicialmente temos que definir subdivisão planar
máxima como sendo uma subdivisão de modo que nenhuma aresta conectando dois
vértices pode ser adicionada a sem destruir sua planalidade. Em outras palavras,
qualquer aresta que não está em intersecta uma das arestas que estão em . Assim,
definimos formalmente uma triangulação de P como sendo uma subdivisão planar
máxima cujos vértices são os pontos de P.
Com esta definição fica óbvio que uma triangulação existe. Mas ela consiste mesmo de
triângulos? A resposta é sim, para cada face interna (àquelas das bordas não-livres da
subdivisão), deve existir um triângulo: uma face externa (a de borda não-livre) forma
um polígono, e sabemos que qualquer polígono pode ser triangularizado. E com
relação às bordas internas? Não é difícil observar que qualquer aresta externa (aquelas
que pertencem à envoltória convexa de P) é uma aresta de qualquer triangulação de
P. O número de triângulos é o mesmo em qualquer triangulação de P. Isso também é
válido para o número de arestas. Mas o número exato, tanto de triângulos quanto de
arestas depende do número de elementos de P que pertencem à sua envoltória
convexa. Isso é dado pelo seguinte teorema:
Teorema 1: Seja P um conjunto de n pontos no plano, nem todos colineares, e seja h o
número de pontos em P que pertencem à envoltória convexa de P. Qualquer
triangulação de P possui 2n-h-2 triângulos e 3n-3-h arestas.
A prova desse teorema está na referência [1].
Seja uma triangulação de P, e suponha que possua m triângulos. É fácil ver que o
número de ângulos internos de
é 3m. Considere que esses 3m ângulos são
ordenados de forma crescente. Seja
essa sequencia de ângulos
ordenados;
então
para
qualquer
.
Denotamos
por
( )
(
) o vetor de ângulos de . Seja
uma nova triangulação de
(
) seu vetor de ângulos. Dizemos que a triangulação
P, e seja ( )
é melhor que a triangulação
se ( ) é lexicograficamente maior do que ( ).
Em outras palavras, se existe um índice i, com
, de modo que:
para todo
e
. Essa ideia é denotada como ( )
( ).
Definição Formal de Triangulação de Delauney: Uma triangulação
de P é dita ser
de Delauney se, para qualquer outra triangulação
e P ( )
( ).
Computando a Triangulação de Delauney
Vimos até agora que, para nossos objetivos ── aproximar um terreno por uma malha
triangular, cujos vértices são os pontos de um conjunto P, que por sua vez é uma
amostra dos pontos do terreno ── a triangulação de Delauney de P é uma boa
aproximação com boas chances de ficar boa. Vimos que a razão disso é porque a
triangulação de Delauney maximiza os ângulos mínimos. Então como computar a
triangulação de Delauney?
A estratégia usada aqui é aleatória e incremental. Inicialmente, construímos um
grande triângulo que contem todos os pontos de P para evitar problemas nas bordas
do conjunto P. À luz dessa ideia, construímos um grande triângulo cujos vértices são
. O uso aqui de índices negativos para os vértices é para poder diferenciálos que qualquer ponto em P. Isso significa que
e
são vértices especiais.
Após a obtenção da triangulação de Delauney para o conjunto
,a
triangulação de Delauney de P é obtida descartando-se os pontos
e todas
as suas arestas ligadas à P. Para que essa estratégia funcione corretamente,
escolhemos
como sendo valores os maiores possíveis, de modo que
nenhuma
aresta
do
triângulo
formado
por
intercepte qualquer aresta da triangulação de Delauney para P. A Figura 4 mostra um
exemplo:
Figura 4: Configuração inicia para triangulação de Delauney
Uma vez definido o triângulo
, o algoritmo vai adicionando aleatoriamente
cada ponto de P ao mesmo tempo que vai mantendo a propriedade de Delauney para
cara triangulação corrente. Considere que em algum momento foi adicionado um
ponto
. Primeiro, procuramos pelo triângulo da triangulação que está sendo
construída onde
caiu ── como isso será feito, será explicado mais tarde ──. Em
seguida, são adicionadas arestas de ao vértice do triângulo onde ele caiu. Se caiu
em uma aresta e da triangulação corrente, adicionamos arestas a partir de
para os
dois vértices opostos nos triângulos que compartilham a aresta e. A figura 5 ilustra
esses dois casos.
Figura 5: Configurações possíveis após a inserção do ponto pr na triangulação de
Delauney.
Assim, passamos a ter uma nova triangulação corrente, mas não necessariamente ela é
de Delauney, uma vez que as arestas adicionadas a partir de pode ter deixa algumas
arestas ilegais. Uma aresta ilegal é uma aresta que, se flipada dentro de um
quadrilátero, melhora a triangulação, caso contrário, a aresta é legal. Para verificar se
uma aresta é ilegal, chamamos um procedimento LegalizeAresta, que recebe cada
aresta potencialmente ilegal e a flipa se necessário. Este procedimento substitui
arestas ilegais por arestas legais através de flips de arestas. O Algoritmo para construir
a triangulação de Delauney a partir dessa ideia é dado a seguir:
REFERÊNCIAS:
[1] Esse material foi traduzido e adaptado por Paulo Sérgio Rodrigues do
livro: “Computational Geometry: Algorithms and Applications”, Segunda
Edição Revisada, dos autores Mark de Berg, Mark Van Kreveld, Mark
Overmars e Otfried Schwarzkopt, pela editora Springer. É para uso
restrito nas aulas de Computação Gráfica do Centro Universitário da FEI.