【摘要】 目前,很多三维Voronoi图生成算法都是先构造Delaunay三角剖分,然后根据剖分后的数据结构来提取出Voronoi信息。在这个过程中,一种简单易处理的数据结构可以提高算法的效率,而在提取Voronoi信息时需要这种数据结构提供足够多的拓扑信息,以便快速简便地提取Voronoi信息。因此一种易于处理而又保有足够多拓扑信息的数据结构显得尤为重要。描述了一种数据结构,使Delaunay三角剖分算法的实现更加直观、简单,而且足够的拓扑信息简化了Voronoi信息的提取过程。更多还原

【Abstract】 There already exist many algorithms for computing three-dimensional Voronoi diagram which always generate the Delaunay triangulation first, and then compute the Voronoi diagram according to the data structure of Delaunay triangulation. In that process, a data structure which could be easily coped with will not only improve the efficiency of the algorithm, but also give more topological information for computing Voronoi diagram so that it could be done simply and quickly. So a data structure which could be coped with easily and keeps enough topological information is quite necessary.Such a data structure is presented which makes the implementation of the algorithm for Delaunay triangulation clear and straightforward, and makes the extraction of Voronoi diagram from it easier for the enough topological information.更多还原