当前位置:主页 > 科技论文 > 数学论文 >

高维Voronoi算法研究

发布时间:2017-12-24 05:19

  本文关键词:高维Voronoi算法研究 出处:《华南理工大学》2016年硕士论文 论文类型:学位论文


  更多相关文章: 高维 Voronoi Delaunay 增量插入算法 qudatree 广度优先搜索 均匀网格


【摘要】:Voronoi图乃是计算几何的一个重要问题,被应用在很多重要的领域。Voronoi图它拥有很多优良性质,包括最邻近性质、区域控制性质。这些优良性质使其被广泛应用的2维平面和3维空间的领域,包括GIS、数据索引、路径规划、城市规划等。平面点的Voronoi算法已经非常多,有如增量构建法、增量插入法、分治法、和扫描线算法等精确算法,还有使用栅格和距离变换技术的近似算法。但是高维度的Voronoi图并没有像平面Voronoi图一样的直接求解算法。因此本文就高维Voronoi算法进行研究。高维Voronoi图一般使用间接求解法,如利用对偶Delaunay图、利用更高维的凸包或者半空间交。本文详细阐述和证明了Voronoi图和其他三者之间的关系,并介绍了高维Delaunay、高维凸包、高维半空间交的算法。本文详细阐述了Watson提出的利用对偶Delaunay求解高维Voronoi算法的实现细节,论述了算法实现时存在的问题,并针对这些问题提出了解决方案,如超球外心计算方法。重点对算法主要耗时点“冲突单形查找”进行研究。阐述了多个优化方案,包括1)利用邻接关系和广度优先搜索策略,2)记录历史单形的Delaunay Tree,3)均匀网格索引,4) Quadtree动态索引,5)单形共同顶点索引。利用以上优化可以快速定位首个冲突单形,然后查找利用广度优先搜索找到剩余冲突单形,大大提高程序效率。最后提出外存优化方案,解决了高维计算时内存不足问题和结果持久化问题。最后进行了多个对比实验,比较了笔者实现的高维Watson算法与已有计算几何库的高维Delaunay实现的性能差别。实验数据表明本文提出的查找优化带来的提升效果明显,而外存优化方案使程序只使用少量的内存就能应对更大的数据量。
【学位授予单位】:华南理工大学
【学位级别】:硕士
【学位授予年份】:2016
【分类号】:O18;TP391.7


本文编号:1327026

资料下载
论文发表

本文链接:https://www.wllwen.com/kejilunwen/yysx/1327026.html


Copyright(c)文论论文网All Rights Reserved | 网站地图 |

版权申明:资料由用户52bde***提供,本站仅收录摘要或目录,作者需要删除请E-mail邮箱bigeng88@qq.com