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

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

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

基　　金：国家自然科学基金 

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

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

页      码：275-282页

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

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

学科分类：0810[工学-土木类] 0808[工学-自动化类] 07[理学] 0839[0839] 08[工学] 080203[080203] 0835[0835] 0802[工学-机械学] 070102[070102] 0811[工学-水利类] 0701[理学-数学类] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3321/j.issn:0254-4164.1999.03.008

馆 藏 号：203179680...