Please use this identifier to cite or link to this item:
https://repositorio.ufu.br/handle/123456789/14331
Document type: | Tese |
Access type: | Acesso Aberto |
Title: | Uma proposta para a triangulação de Delaunay 2D e localização planar de pontos em OCaml |
Author: | Moura, Andre Luiz |
First Advisor: | Camacho, José Roberto |
First member of the Committee: | Pereira, Antônio Eduardo Costa |
Second member of the Committee: | Lamounier Júnior, Edgard Afonso |
Third member of the Committee: | Pérez, Mário Mourelle |
Fourth member of the Committee: | Mesquita, Renato Cardoso |
Fifth member of the Committee: | Guimarães Júnior, Sebastião Camargo |
Summary: | Nesta tese, é apresentado um algoritmo dinâmico de localização planar de pontos. O algoritmo foi elaborado sobre dois fundamentos: - o método das Slabs para particionar a subdivisão planar, representada por um grafo, e permitir a rápida identificação da região em que se encontra o ponto que está sendo consultado; - a Multiárvore-B Intervalar, uma estrutura de dados derivada árvore-B, aparelhada com mecanismo de pesquisa intervalar e disposta em camadas. O algoritmo é dinâmico porque altera dinamicamente a estrutura de pesquisa, à medida que surgem eventos de inserção ou remoção de segmentos na subdivisão planar que está sendo construída. O algoritmo foi implementado na linguagem OCaml, mas poderia ter sido implementado em qualquer outra linguagem de programação. Para aumentar a eficiência do algoritmo, algumas melhorias podem ser introduzidas, como por exemplo, a substituição do núcleo da Multiárvore-B Intervalar por outros tipos de árvores balanceadas. Adicionalmente, foram discutidos alguns aspectos do processso de construção de malhas de elementos finitos, em que se insere, sobretudo, o problema da localização planar de pontos. |
Abstract: | In this thesis, it is presented a planar point location algorithm. The algorithm was developed on top of two elements: - the method of slabs to divide the planar subdivision, is represented by a graph, allowing the fast identification of the region where the point being recalled is; - the Interval Multi-B-tree, a data structure derived from the B-tree, prepared with an interval search structure and disposed in layers. The algorithm is essentially dynamic since the search structure keeps changing dynamically during the process, while the planar subdivision is being built; new events of segment insertion or removal keep appearing. The algorithm was implemented in OCaml, but could be carried out in any other programming language. To increase the algorithm efficiency, some improvements can be introduced, as an example, the substitution of the Interval Multi-B-tree core by other types of balanced trees. Moreover, it was discussed some aspects of the assembling process of the finite element meshing, where it is inserted, mainly, the planar point location problem. |
Keywords: | Localização planar de pontos dinâmica Árvore balanceada Multiárvore-B intervalar Triangulação de Delaunay incremental Malha bidimensional OCaml Dynamic planar point location Balanced tree Interval multi-B-tree Incremental Delaunay triangulation Two dimensional meshing Engenharia elétrica - Matemática |
Area (s) of CNPq: | CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA |
Language: | por |
Country: | BR |
Publisher: | Universidade Federal de Uberlândia |
Institution Acronym: | UFU |
Department: | Engenharias |
Program: | Programa de Pós-graduação em Engenharia Elétrica |
Quote: | MOURA, Andre Luiz. Uma proposta para a triangulação de Delaunay 2D e localização planar de pontos em OCaml. 2006. 115 f. Tese (Doutorado em Engenharias) - Universidade Federal de Uberlândia, Uberlândia, 2006. |
URI: | https://repositorio.ufu.br/handle/123456789/14331 |
Date of defense: | 30-Jun-2006 |
Appears in Collections: | TESE - Engenharia Elétrica |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
ALMouraTESPRT.pdf | 1.48 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.