论文部分内容阅读
Voronoi图是计算几何(Computational Geometry)的一个重要的研究领域,在图形图像处理、计算机辅助设计(Computer Aided Design,CAD)、地理信息系统(Geographic Information System,GIS)、空间邻域分析、路径规划、虚拟现实等等领域得到了广泛的应用。Voronoi生成算法方面,学术界对于2维、3维空间的研究成果比较多。由于更高维的Voronoi图的拓扑结构、分析和实现都较为复杂,所以国内外对于任意维度上Voronoi图生成算法的研究并不是很多。本文针对这一研究领域的不足,利用了Voronoi图、Delaunay三角剖分和凸包三者之间的对应关系,研究和改进了高维凸包的生成算法,并应用于高维的Voronoi图的生成。本文首先对已有的、应为较为广泛的高维凸包算法进行了介绍和分析,并对它们的复杂度进行了研究。然后专注于Quickhull算法,出了两方面的改进,并应用于生成高维Voronoi图。关于算法效率,本文出了两点改进:一是对于数据结构改进以高搜索的效率,二是设计了算法并行执行的机制,将现有的算法改为并行执行。关于算法的健壮性也出了两点改进:一是对于点集退化情形的处理,二是算法执行的过程中进行自检验,以保证算法当前执行的结果始终是正确的。第六章做了相应的实验来对比改进前后的算法,说明改进后的算法效率得到了明显的高。在Voronoi图的应用方面,利用其各种优秀的性质,它被广泛应用在路径规划、高维聚类分析等等领域。此外学界也出现了一些跨领域应用的实例,比如与物理,化学、生物学、机械制造、移动通讯等领域相结合。随着高维Voronoi图应用需求的不断扩大,本文具有很好的理论和应用意义。