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

作者：赵海森; 杨承磊; 吕琳; 王筱婷; 杨义军; 孟祥旭

来源：计算机辅助设计与图形学学报, 2013, (03): 331-340.

• “带洞”多边形
• 可见多边形
• Voronoi图
• 最短路径 polygon with holes
• visibility polygon
• Voronoi diagram
• shortest path

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

• 出版日期2013
• 单位山东大学