Semana 2

Esta semana fiz uma pesquisa relativamente a métodos de cálculo de volumes e construção de malhas triangulares. Abaixo encontra-se um resumo da pesquisa realizada.

​

​

Métodos de cálculo de volumes

​

Os métodos de cálculo mais precisos podem ser divididos em três categorias:

• Rough Methods - calcula o volume ao usar uma fórmula empírica, onde o volume é o produto da área da secção transversal da altura, a altura mais três e um fator regulatório. Tendo em conta que objetos reais são têm geometria padrão, o erro é muito grande para estes métodos;

• SlicingMethod - corta a nuvem de pontos em fatias de igual espessura ao longo do eixo z. Depois divide-se cada corte, igualmente, ao longo do eixo y  e corta cada fatia em subintervalos ao longo do eixo x. Usam-se as coordenadas mínimas e máximas em cada subintervalo para calcular a área de cada fatia. As áreas das fatias são integradas ao longo do eixo z para estimar o volume do objeto;

• Projection Method - Os triângulos, obtidos por criação de malhas, são projetados no plano xy. Estes triângulos projetados são combinados com os triângulos da malha, obtendo assim vários pentaedros.

​

O método de projeção é o método mais simples e preciso para esta categoria de volumes.

​

Passos para obter volume usando método de projeção:

1. Obter equação da superfície de topo;

2. Equação da aresta do triângulo projetado;

3. Cálculo dos volumes dos pentaedros.

​

Malha Triangular

​

Uma malha poligonal consiste num conjunto de vértices, arestas e faces. Esta define a forma de qualquer superfície de objeto no espaço 3D. Malhas poligonais representam o ambiente de forma compacta, mas representação precisa e contínua e pode ser usado, por exemplo, para localização, rastreamento, caminho planeamento ou (como no nosso caso) cálculos de volume do objeto. As faces são polígonos convexos simples, mas geralmente é mais utilizado triângulos(malha triangular). Para tornar as informações geométricas transportadas acessíveis para cálculo do volume do objeto, a entrada os dados devem ser convertidos numa representação que possa ser tratada pelo algoritmo de cálculo de volume escolhido.

​

Um método utilizado em muitas aplicações, e um dos métodos mais populares utilizados em problemas relacionados à geração de malhas é o método Delaunay Triangulation.

A propriedade fundamental é o critério do círculo vazio. Para um conjunto de pontos em 2D, uma triangulação de Delaunay desses pontos garante que o círculo circunscrito associado a cada triângulo não contenha nenhum outro ponto no seu interior.

Muitos algoritmos para calcular triangulações de Delaunay dependem de operações rápidas para detetar quando um ponto está dentro do círculo circunscrito de um triângulo. Em duas dimensões, uma forma de detectar se o ponto D está no círculo circunscrito do triângulo ABC é avaliar o determinante da matriz M.

Quando os pontos A, B e C são ordenados no sentido anti-horário, podemos determinar a posição do ponto D escolhido arbitrariamente:

​

det(M) > 0 −→ D está dentro círculo circunscrito

det(M) = 0 −→ D está coincidente com o círculo circunscrito

det(M) < 0 −→ D está fora do círculo circunscrito

​

Propriedades da Triangulação Delaunay (DT):

• Um círculo circunscrito a um qualquer triângulo de Delaunay não contém nenhum outro ponto de entrada no seu interior.

• No plano, o DT maximiza o ângulo mínimo de todos os ângulos dos triângulos na malha. Comparado com qualquer outra triangulação dos pontos, o menor ângulo no DT é pelo menos tão grande quanto o menor ângulo em qualquer outro. No entanto, o DT não necessariamente minimizar o ângulo máximo. O DT também não necessariamente minimiza a duração das bordas.

• A união de todos os simplexos na triangulação é o casco convexo de pontos.

• Para um conjunto de pontos na mesma linha, não há DT (a noção de triangulação é degenerado para este caso).

• Para quatro ou mais pontos no mesmo círculo (por exemplo, os vértices de um quadrado, retângulo ou trapézio isósceles) o DT não é único: cada uma das duas triangulações possíveis que se dividem o quadrilátero em dois triângulos satisfaz a condição de Delaunay, ou seja, o requisito que os círculos circunscritos de todos os triângulos têm interiores vazios.

​

​

Até ao próximo relatório semanal! :)