Uma proposta para a triangulação de Delaunay 2D e localização planar de pontos em OCaml

AUTOR(ES)
DATA DE PUBLICAÇÃO

2006

RESUMO

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.

ASSUNTO(S)

localização planar de pontos dinâmica malha bidimensional engenharia elétrica - matemática balanced tree incremental delaunay triangulation multiárvore-b intervalar engenharia eletrica interval multi-b-tree Árvore balanceada triangulação de delaunay incremental ocaml dynamic planar point location two dimensional meshing

ACESSO AO ARTIGO

Documentos Relacionados