Seja T uma triangulação dos pontos do conjunto S e suponha que T possui n triângulos. A sequência de ângulos (a1,a2,a3,...,an) de T é a lista de todos os ângulos de T ordenados do menor para o maior.
Usando a sequência de ângulos podemos comparar duas diferentes triangulações de S. Como o número de triângulos de qualquer triangulação de S é uma constante, todas as triangulações possuem sequência de ângulos do mesmo comprimento.
Então (20º, 30º, 45º, 65º, 70º, 130º) é melhor do que (20º, 30º, 45º, 60º, 75º, 130º) porque 65º > 60º na primeira posição em que as sequências diferem.
A melhor triangulação é o que procuramos, mas como é que vamos encontrá-la? Acontece que existe uma maneira elegante de obter a melhor triangulação via inversão de arestas. Começamos com uma definição.
Definição: Seja e uma aresta de uma triangulação T1, e seja Q um quadrilátero em T1 formado pelos 2 triângulos que têm e como aresta comum. Se Q e convexo, deixe T2 ser a triangulação depois de inverter a aresta e em T1. Dizemos que e é uma aresta legal se T1 for maior ou igual a T2, caso contrário e é uma aresta ilegal.
Para obter a melhor triangulação do conjunto de pontos S devemos evitar o surgimento de arestas ilegais nas triangulações.
Definição: Para um conjunto de pontos S, uma triangulação Delaunay de S (Del(S)) é uma triangulação onde ocorrem apenas arestas legais.
Algoritmo de Inversão de Arestas: Seja S um conjunto de pontos em "posição geral", sem 4 pontos cocirculares. Inicie com uma triangulação T. Se T tem uma aresta ilegal, inverta a aresta e obtenha uma aresta legal. Continue invertendo arestas ilegais, movendo-se pelas arestas do grafo de S em qualquer ordem até não restarem mais arestas ilegais.
No algoritmo de Delaunay proposto, para realizar o cálculo da aresta legal será necessário a inversão de uma diagonal, o quê envolverá a comparação de 12 ângulos em duas sequências de 6 ângulos. Há uma maneira mais simples de fazer este teste usando círculos baseado em uma extensão da um teorema clássico da geometria planar:
Teorema 3.49(Thales) Para três pontos P, Q e B em um círculo, e A dentro e C fora do círculo, o ângulo PAQ é maior que PBQ que é maior que PCQ.
Esboço da Prova: Seja O o centro do círculo. Os 3 segmentos OP, OQ e OB são radianos e tem igual comprimento. Então os triângulos POB e QOB são isóceles. Sendo assim, não é difícil mostrar que independente da posição de B no arco do círculo, o ângulo POQ é duas vezes maior que PBQ. De fato, este é o teorema de Euclides (Elementos, Livro III, Proposição 20): um ângulo inscrito em um círculo tem metade do ângulo central subtendido o mesmo arco. Isto pode ser utilizado para declarar que o ângulo PAQ é maior que PBQ e que PCQ é menor que PBQ.
Nenhum comentário:
Postar um comentário