多边形中的点可见性快速算法

摘要：

针对点的可见性计算这一计算几何中的基础问题,提出一种支持任意查询点的可见多边形快速计算的基于多边形Voronoi图的点可见性算法.以与Voronoi骨架路径对应的Voronoi通道概念,以及相应的局部最短路径概念为基础,按照深度优先策略对Voronoi图进行遍历,在计算Voronoi骨架路径的同时计算局部最短路径,并基于局部最短路径计算所遍历的多边形边的可见部分.该算法可以处理“带洞”多边形,而且只对多边形进行局部访问；对于“带洞”多边形,由于该算法的数据结构比较简单、剖分空间合理且易于实现,因此仅需O(n)空间和O(nlgn)预处理时间.最后给出了在三维室内虚拟场景设计与漫游系统中的应用实例,结果表明文中算法是实际可行,且运行时间与点的可见多边形的边数和多边形的边数均呈线性关系.

关键词："带洞"多边形、可见多边形、Voronoi图、最短路径

所属期刊栏目：25

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金61272243,61202146,61202147;山东省优秀中青年科学家基金BS2012DX014;山东省自然科学基金ZR2012FQ026;山东大学自主创新基金2010HW010

在线出版日期：2013-06-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：331-340