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 d...
详细信息
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.
The medial axis is an important shape representation that finds a wide range of applications in shape analysis. For large-scale shapes of high resolution, a progressive medial axis representation that starts with the ...
详细信息
The medial axis is an important shape representation that finds a wide range of applications in shape analysis. For large-scale shapes of high resolution, a progressive medial axis representation that starts with the lowest resolution and gradually adds more details is desired. In this paper, we propose a fast and robust geometric algorithm that computes progressive medial axes of a large-scale planar shape. The key ingredient of our method is a novel structural analysis of merging medial axes of two planar shapes along a shared boundary. Our method is robust by separating the analysis of topological structure from numerical computation. Our method is also fast and we show that the time complexity of merging two medial axes is O(n log n(v)), where n is the number of total boundary generators, n(v) is strictly smaller than n and behaves as a small constant in all our experiments. Experiments on large-scale polygonal data and comparison with state-of-the-art methods show the efficiency and effectiveness of the proposed method.
The divide-and-conquer algorithm for constructing three-dimensional convex hulls is implemented in a numerically robust manner. The approach taken here is a topology-oriented approach, in which the topological consist...
详细信息
The divide-and-conquer algorithm for constructing three-dimensional convex hulls is implemented in a numerically robust manner. The approach taken here is a topology-oriented approach, in which the topological consistency is considered more important than the result of numerical computation. This is the first implementation of the divide-and-conquer algorithm for the three-dimensional convex hull using the topology-oriented approach. Implementation details are described together with computational experiments.
The divide-and-conquer algorithm for constructing three-dimensional convex hulls is implemented in a numerically robust manner. The approach taken here is a topology-oriented approach, in which the topological consist...
详细信息
The divide-and-conquer algorithm for constructing three-dimensional convex hulls is implemented in a numerically robust manner. The approach taken here is a topology-oriented approach, in which the topological consistency is considered more important than the result of numerical computation. This is the first implementation of the divide-and-conquer algorithm for the three-dimensional convex hull using the topology-oriented approach. Implementation details are described together with computational experiments.
暂无评论