VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments
VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments
复制标题
DOI：
10.1016/s0925-7721(01)00003-7
复制
发表时间：
2001-03-01
影响因子：
0.6
通讯作者：
Held, M
中科院分区：
文献类型：
--
作者：
Held, M
讨论了二维欧氏空间中点、线段的Voronoi图的拓扑计算算法的设计与实现。我们工作的主要重点是设计和设计一种在实践中完全可靠且快速的算法。该算法在ANSI C中实现，使用标准浮点运算。除了Sugihara和Iri的面向拓扑的方法之外，它还基于所需数值计算的非常仔细的实现，自动放松阈值，以及与“绝望模式”相结合的多级恢复过程。由此产生的代码名为vroni，在真实世界的数据上进行了广泛的测试，结果证明是可靠的。CPU时间统计文件表明，它总是比其他流行的Voronoi代码快。在我们的计算环境中，vroni需要大约0.01n log（2）n毫秒来计算n个线段的Voronoi图，这个公式适用于各种各样的合成和真实世界的数据。特别是，它的CPU时间消耗几乎不受输入数据的实际分布的影响。Vroni还具有计算偏移曲线的功能，它已经成功地在几个工业软件包中进行了测试并集成到其中。(C)2001 Elsevier Science B.V.保留所有权利。
We discuss the design and implementation of a topology-oriented algorithm for the computation of Voronoi diagrams of points and line segments in the two-dimensional Euclidean space. The main focus of our work was on designing and engineering an algorithm that is completely reliable and fast in practice. The algorithm was implemented in ANSI C, using standard floating-point arithmetic. In addition to Sugihara and Iri's topology-oriented approach, it is based on a very careful implementation of the numerical computations required, an automatic relaxation of epsilon thresholds, and a multi-level recovery process combined with "desperate mode". The resulting code, named vroni, was tested extensively on real-world data and turned out to be reliable. CPU-time statistics document that it is always faster than other popular Voronoi codes. In our computing environment, vroni needs about 0.01n log(2) n milliseconds to compute the Voronoi diagram of n line segments, and this formula holds for a wide variety of synthetic and real-world data. In particular, its CPU-time consumption is hardly affected by the actual distribution of the input data. Vroni also features a function for computing offset curves, and it has been successfully tested within and integrated into several industrial software packages. (C) 2001 Elsevier Science B.V. All rights reserved.