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

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.