CAJ | 학술논문

针对点的可见性计算这一计算几何中的基础问题,提出一种支持任意查询点的可见多边形快速计算的基于多边形Voronoi图的点可见性算法.以与Voronoi骨架路径对应的Voronoi通道概念,以及相应的局部最短路径概念为基础,按照深度优先策略对Voronoi图进行遍历,在计算Voronoi骨架路径的同时计算局部最短路径,并基于局部最短路径计算所遍历的多边形边的可见部分.该算法可以处理“带洞”多边形,而且只对多边形进行局部访问；对于“带洞”多边形,由于该算法的数据结构比较简单、剖分空间合理且易于实现,因此仅需O(n)空间和O(nlgn)预处理时间.最后给出了在三维室内虚拟场景设计与漫游系统中的应用实例,结果表明文中算法是实际可行,且运行时间与点的可见多边形的边数和多边形的边数均呈线性关系.
침대점적가견성계산저일계산궤하중적기출문제,제출일충지지임의사순점적가견다변형쾌속계산적기우다변형Voronoi도적점가견성산법.이여Voronoi골가로경대응적Voronoi통도개념,이급상응적국부최단로경개념위기출,안조심도우선책략대Voronoi도진행편력,재계산Voronoi골가로경적동시계산국부최단로경,병기우국부최단로경계산소편력적다변형변적가견부분.해산법가이처리“대동”다변형,이차지대다변형진행국부방문；대우“대동”다변형,유우해산법적수거결구비교간단、부분공간합리차역우실현,인차부수O(n)공간화O(nlgn)예처리시간.최후급출료재삼유실내허의장경설계여만유계통중적응용실례,결과표명문중산법시실제가행,차운행시간여점적가견다변형적변수화다변형적변수균정선성관계.