Engenharia

Triangulação de Delunay

José Igor Dias Rolim

1. 1 Introdução

        O estudo a respeito de triangulações vem sendo cada vez mais difundido nos meios acadêmicos, uma vez que este está inserido nos métodos matemáticos que compõe os sistemas computacionais. Tais sistemas passaram a ser incorporados no cotidiano de cada pessoa, seja na visualização de uma simples imagem na tela de um computador ou celular, até na descoberta do caminho mais próximo através de um sistema de GPS. Na área de Construção Civil é muito usado por programas computacionais geradores de curvas de níveis. A triangulação de Delaunay foi inventada pelo matemático Boris Delaunay em 1934, no qual ele propunha diversos teoremas entre eles o da maximização do menor ângulo de todos os triângulos dentro de uma triangulação.

1. 2 Conceitos Fundamentais

2.1 Convexividade

2.1.1 Combinação Convexa

        Sejam P1 e P2  pontos de uma reta, a combinação linear destes pontos será dita convexa quando estes novos pontos estiverem entre P1 e P2,, ou seja, quando λ1 e λ2 somados for igual a 1.

Figura 1: Demonstração da combinação linear entre dois pontos[pic 2]

2.1.2 Conjunto Convexo

        Um conjunto S é dito convexo se para qualquer segmento de reta traçado dentro do conjunto, este pertença integralmente a S.

Figura 2: Conjunto Convexo[pic 3]

Figura 3: Conjunto NÃO Convexo[pic 4]

        

        A partir de estudos matemáticos com conjuntos convexos podemos afirmar que:

• A bola aberta é um conjunto convexo.
• A interseção de convexos é convexa.

2.1.3 Fecho Convexo

        O fecho convexo de um conjunto pertencente ao[pic 5] é a menor região convexa do[pic 6] que contém todos os pontos do conjunto.

        Achar o fecho convexo de um conjunto de pontos, por exemplo, é um problema que aparece quando queremos organizar o conjunto, agrupar os pontos em uma região simples.

Figura 4: Fecho Convexo de um conjunto de pontos[pic 7]

2.2 Subespaço afim

        Seja S um conjunto de vetores pertencentes ao[pic 8] .É dito subespaço afim um conjunto de todos os vetores que são combinações afim de S. Subespaço afim pode ser visto como translações de espaços vetoriais.

2.3 Independência Geométrica

        Um conjunto de pontos em[pic 9] é dito geometricamente independente se, e somente se, houve um conjunto de vetores a ele relacionando linearmente independente.

2.4 Teorema de Carathéodory

        Seja S um conjunto pertencente ao[pic 10] . Então todo x pertencente ao fecho convexo S é uma combinação convexa de no máximo d+1 pontos de S.

2.5 Simplexo

        Um simplexo de dimensão d, é o fecho convexo de d+1 pontos geometricamente independentes de[pic 11] , os quais são vértices deste simplexo.

        Um complexo simplicial S é uma coleção finita de simplexos tais que cada face de um simplexo de S é um simplexo de S e a intersecção de dois simplexos de S é vazia ou uma face de ambos. Um complexo simplical K em[pic 12] é dito puro, se todo simplexo de K está contido em um simplexo de dimensão máxima.

Figura 5: Complexo Simplicial Puro[pic 13]

2.6 Triangulações

        Uma triangulação é um complexo simplicial puro.

        Um conjunto de pontos são trianguláveis. Mas nem sempre existe triangulações, é o caso do poliedro de Schönhardt.

Figura 6: Conjunto de pontos trianguláveis[pic 14]

Figura 7: Poliedro de Schönhardt[pic 15]

1. 3 Triangulação de Delaunay

        Criada por Boris Delaunay em 1934. Uma triangulação é dita de Delaunay se puder ser feito uma circunferência na qual nenhum ponto do triângulo esteja dentro da mesma. É dito circuncirculo vazio. Daí vem a relação com o Diagrama de Voronoi, ligando-se o centro de todas as circunferenciais na triangulação encontramos o diagrama. Para que um triângulo seja deito Delaunay também é necessário que suas arestas sejam legais, ou seja, para um conjunto de pontos A, B, C, D e ABC, ACD triângulos, e AC uma aresta, dizemos que esta é legal se, e somente se, o ponto D estiver fora do circuncirculo formado por ABC, caso contrário será ilegal, e o triângulo não será de Delaunay.