Point triangulation using Graham???s scan

摘要

In this paper, we propose a triangulation method for a set of points in the plane. The method is based on the idea of constructing convex layers by Graham???s scan. It allows to develop an algorithm with the optimal complexity of O(N logN) (in case of constant number of layers) and an easy implementation. Firstly, convex hulls are constructed for the set S of N points, forming k layers. Then, each layer is triangulated in one scan of the adjacent convex hulls. Algorithm is easily parallelized: each layer can be triangulated independently. The main feature of the proposed algorithm is that it has a very simple implementation and the elements (triangles) of the resulting triangulation are presented in the form of simple and at the same time fast data structures: concatenable triangle queue or triangle tree. This makes the algorithm convenient for solving a wide range of applied problems of computational geometry and computer graphics, including simulation in science and engineering, rendering and morphing.