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
DOI: https://doi.org/10.1016/0098-3004(93)90062-A
URI: https://www.sciencedirect.com/science/article/pii/009830049390062A
Zotero BiDiAr: https://www.zotero.org/groups/5293298/bidiar/items/EGF44DEZ/item-list
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.
cited by: Analytical approaches and digital methods in alluvial archaeology: the ‘Ancient Shipyard’ of Pisa-San Rossore as a case study

Filter by resource type and property:

Academic Article

DHeLO