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