Delaunay triangulation using a uniform grid
- 1 May 1993
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Computer Graphics and Applications
- Vol. 13 (3) , 36-47
- https://doi.org/10.1109/38.210490
Abstract
An algorithm for triangulating 2-D data points that is based on a uniform grid structure and a triangulation strategy that builds triangles in a circular fashion is discussed. The triangulation strategy lets the algorithm eliminate points from the internal data structure and decreases the time used to find points to form triangles, given an edge. The algorithm has a tested linear time complexity that significantly improves on that of other methods. As a by-product, the algorithm produces the convex hull of the data set at no extra cost. Two ways to compute the convex hull using the algorithm are presented. The first is based on the edge list and the second is based on the grid structure.Keywords
This publication has 10 references indexed in Scilit:
- Algorithms in Combinatorial GeometryPublished by Springer Nature ,1987
- Computational Geometry and Software EngineeringPublished by Springer Nature ,1987
- Primitives for the manipulation of general subdivisions and the computation of VoronoiACM Transactions on Graphics, 1985
- Computational GeometryPublished by Springer Nature ,1985
- Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopesThe Computer Journal, 1981
- Computing Dirichlet tessellationsThe Computer Journal, 1981
- Two algorithms for constructing a Delaunay triangulationInternational Journal of Parallel Programming, 1980
- Computing Dirichlet Tessellations in the PlaneThe Computer Journal, 1978
- Locally equiangular triangulationsThe Computer Journal, 1978
- Neue Darstellung der geometrischen KristallographieZeitschrift für Kristallographie - Crystalline Materials, 1933