简单多边形可见点问题的快速求解算法

作     者：金文华 何涛 唐卫清 唐荣锡 刘慎权 JIN Wen-hua;He Tao;TANG Wei-Qing;TANG Rong-xi;LIU Shen-Quan

作者机构：中国科学院计算技术研究所CAD开放实验室 北京航空航天大学制造工程系 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：1999年第22卷第3期

页      面：275-282页

核心收录：

学科分类：07[理学] 08[工学] 080203[工学-机械设计及理论] 070102[理学-计算数学] 0802[工学-机械工程] 0701[理学-数学] 

基　　金：国家自然科学基金 

主　　题：简单多边形 计算几何 可见点问题 计算机图形学 

摘      要：简单多边形可见点问题是计算几何的基本问题之一，在许多领域均有应用．本文在参考现有算法（尤其是Ｌｅｅ算法）的基础上，提出了改进的方法．文中方法先用射线法求取第一个可见点，然后利用文中设定的规则搜索后续可见点．本文算法继承和发展了Ｌｅｅ算法的几何直观性，且也只采用一个堆栈，但无须耗时的坐标变换和三角函数运算，而且彻底修改了Ｌｅｅ算法的错误，避免了Ｌｅｅ算法中的不足之处，并且算法的时间和空间复杂度仍为Ｏ（ｎ）．本文算法已应用于工厂设计配管软件ＰＤＳＯＦＴｆｏｒＰｉｐｉｎｇ中，实践证明效果很好．