面向规则网格的连续天际线可视域精确算法

作者：张建民; 余接情^*; 艾伟; 杜丹

来源：河北省科学院学报, 2022, 39(04): 14-20.

DOI：10.16191/j.cnki.hbkx.2022.04.005

• 可视域分析
• 可视性计算
• 天际线
• 视面综合算法

可视域分析是众多应用的基础。然而，现有可视域算法在精度及效率方面难以同时取得很好的性能。基于视面综合算法(Synthetic Visual Plane, SVP)提出了一种在时间性能代价不高的精确可视域计算算法―连续天际线可视域算法(Viewshed Based on Continuous Horizon, VCH)。为达到精确求解的目的，VCH算法采用连续线段来描述用于判断某点可视性的天际线。与此同时，为实现天际线的快速更新，利用红黑树及双向链表这一复合结构来管理天际线。分析表明，VCH算法的精度与公认的精确算法(R3算法)相当，远高于现有近似算法的精度，其时间复杂度为O(n2(logn)),实测效率高于现有精确算法(R3算法及扫描线算法)但略低于现有近似算法(SVP及R2)。

• 单位
  中国电子科技集团公司第五十四研究所; 中国矿业大学; 中国矿业大学（北京）