Academic Article
Fast topological construction of delaunay triangulations and voronoi diagrams
- Title
- Fast topological construction of delaunay triangulations and voronoi diagrams
- Creator(s)
- Tsai, Victor J. D.
- Date
- 1993
- Is Part Of
- Computers & Geosciences
- Volume
- 19
- Issue
- 10
- Pages
- 1463-1474
- Language
- eng
- ISSN
- 0098-3004
- Abstract
- This paper describes a Convex Hull Insertion algorithm for constructing the Delaunay triangulation and the Voronoi diagram of randomly distributed points in the Euclidean plane. The implemented program on IBM-compatible personal computers takes benefits from the partitioning of data points, topological data structures of spatial primitives, and features in C++ programming language such as dynamic memory allocation and class objects. The program can handle arbitrary collections of points, and delivers several output options to link with GIS and CAD systems. Empirical results of various sets of up to 50,000 points show that the proposed algorithm speeds up the construction of both tessellations of irregular points in expected linear time.
Linked resources
Export
Position: 9783 (4 views)
