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

作     者：赵海森 杨承磊 吕琳 王筱婷 杨义军 孟祥旭 Zhao Haisen;Yang Chenglei;Lu Lin;Wang Xiaoting;Yang Yijun;Meng Xiangxu

作者机构：山东大学计算机科学与技术学院济南250101 山东省软件工程重点实验室济南250101 

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

出 版 物：《计算机辅助设计与图形学学报》 (Journal of Computer-Aided Design & Computer Graphics)

年 卷 期：2013年第25卷第3期

页      码：331-340页

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

主 题 词：“带洞”多边形 可见多边形 Voronoi图 最短路径 

学科分类：081203[081203] 08[工学] 0835[0835] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3969/j.issn.1003-9775.2013.03.007

馆 藏 号：203664355...