| |
| Acadêmico(a): Luciano Raitz |
| Título: Estudo e Avaliação de Alguns Métodos de Triangularizações de Pontos Dispersos em uma Superfície 3D |
| |
| Introdução: |
| A grande maioria dos problemas de engenharia requer a construção prévia de um mapa topográfico que represente adequadamente a superfície do terreno, e que se constitui assim num ponto de apoio fundamental para o projeto e execução das obras (Paredes, 1994). O objetivo da representação do relevo topográfico é registrar e permitir a visualização da forma do terreno, e ao mesmo tempo fornecer os dados numéricos necessários para a solução dos problemas da engenharia: distâncias, e principalmente cotas de pontos desejados, com a precisão suficiente (Cintra,1984). Como a superfície do terreno é constituída por infinitos pontos, impõem-se uma escolha de valores discretos, que sejam representativos e permitam uma representação confiável. Os critérios que norteiam essa escolha devem ser técnicos e econômicos, procurando conciliar o pouco dispêndio (reduzido número de pontos) com a qualidade do mapa (mais pontos, fidelidade do terreno) (Cintra, 1984). Através destes pontos, pode-se gerar redes triangulares que segundo Cintra (1984), fornecidos alguns pontos distribuídos de maneira aleatória, trata-se de uní-los convenientemente para formar uma rede de triângulos. A malha triangular deve ter como vértices somente os pontos fornecidos, isto é, não deve haver cruzamentos de linhas que unem dois pontos, o que daria origem a um vértice fictício. Não deve haver pontos isolados ou não totalmente conectados. Por exemplo, cada vértice de fronteira deve estar unido a pelo menos duas arestas e cada vértice interno a pelo menos três. Caso contrário seria necessário completar a triangulação. Triangularizações tem um papel importante na teoria da aproximação, métodos de elementos finitos, análise numérica e projeto geométrico auxiliado por computador entre inúmeras aplicações, onde freqüentemente são usadas para definir um domínio particionado que permite aproximar ou modelar superfícies (Reis, 1997). Entre as possíveis formas de se gerar os triângulos, a triangularização Delaunay permite obter um conjunto de triângulos mais eqüi-angulares. Permite melhorar a representação das superfícies geradas de pontos interpolados a partir dos vértices destes triângulos, pois asseguram que cada ponto sobre a superfície está o mais próximo possível de um vértice (Spatial, 1994; Goodchild, 1995). A cobertura convexa (convex hull) de um conjunto planar de pontos é um polígono convexo que contém todo o conjunto planar com a área mínima (Eddy 1977; Goodchild, 1995). Alguns algoritmos de triangularização necessitam da cobertura convexa, já que os seus segmentos seguramente serão lados dos triângulos, ou mais, dos triângulos otimizados (triangularização Delaunay), como também seguramente os pontos mínimos e máximo em ambos os eixos de coordenadas pertencerão à cobertura convexa. O cálculo da cobertura convexa (particularmente no plano) também é extensivamente estudado e aplicado em reconhecimento de padrões e processamento de imagens (Preparata, 1985). A triangularização Delaunay possui interessantes propriedades, tais como: ela é única entre as diversas topologias que uma triangularização pode ter, maximiza os mínimos ângulos internos de cada triângulo, os pontos de um triângulo não podem ser colineares, a cobertura convexa sempre faz parte da grade Delaunay e triângulos Delaunay não são hierárquicos (eles não podem ser agregados ou particionados) (Goodchild, 1995; Lee, 1980; Preparata, 1985; Spatial, 1994). O estudo da cobertura convexa é necessário devido a utilização destes em alguns dos métodos de triangularizações que posteriormente deverão ser otimizados para, desta forma, se chegar a um resultado para a devida avaliação de cada um dos algoritmos estudados através do protótipo. |
| |
|
