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

【Abstract】 Visibility computation is a fundamental problem in computational geometry.This paper presents a Voronoi diagram-based algorithm for computing the visibility polygon of any point in the polygon.First,the definitions of Voronoi corridors and local shortest paths in Voronoi corridors are proposed.Then the depth-first search for traversing the Voronoi diagram is performed to compute Voronoi skeleton paths and the local shortest paths from a point to the vertices of the polygon.Afterwards,the visibility portions of the polygon edges are computed.Compared with the popular visibility algorithms based on triangulation,the proposed algorithm can deal with the polygon with holes and partially visiting the polygon only.Compared with algorithms based on visual cell subdivision or visible graphs,the proposed algorithm has a simpler data structure,more reasonable space subdivision,easier implementation,and only takes O(n) space and O(n lg n) preprocessing time.Examples show that the algorithm is of practical effectiveness,and the running time is approximately linear to the number of the edges of the visibility polygon of a point and the number of the edges of the polygon.更多还原