摘要
简单多边形可见点问题是计算几何的基本问题之一，在许多领域均有应用．本文在参考现有算法（尤其是Ｌｅｅ算法）的基础上，提出了改进的方法．文中方法先用射线法求取第一个可见点，然后利用文中设定的规则搜索后续可见点．本文算法继承和发展了Ｌｅｅ算法的几何直观性，且也只采用一个堆栈，但无须耗时的坐标变换和三角函数运算，而且彻底修改了Ｌｅｅ算法的错误，避免了Ｌｅｅ算法中的不足之处，并且算法的时间和空间复杂度仍为Ｏ（ｎ）．本文算法已应用于工厂设计配管软件ＰＤＳＯＦＴｆｏｒＰｉｐｉｎｇ中，实践证明效果很好．
Point visibility problem is one of the fundamental problems in computational geometry, and used in many fields. An improved algorithm, based on the algorithms now available (especially the Lee's algorithm), is proposed, it first finds the first visible point by the radial method, and then searches other visible points by using those regulations specified in the paper. The algorithm presented in this paper is composed of such process as: the initial status process (to look for the first visible point), six location status process (the main process) and the spiral status process. The Lee's algorithm will obtain wrong visible points link in some special cases, and it has to transform coordinates, and has no concern with co line points. The presented algorithm inherits and develops the geometric feature of Lee's method, and also uses only one stack, but does not transform coordinates and has no need to calculate trigonometric functions. The method not only corrects the mistakes embedded in the Lee's algorithm, but also avoids its limitation. And the time and space complexity of the algorithm are still O(n) . The presented algorithm has been applied in plant design piping software PDSOFT for Piping. The results of the method in practice are remarkable.
出处
《计算机学报》
EI
CSCD
北大核心
1999年第3期275-282,共8页
Chinese Journal of Computers
基金
国家自然科学基金
关键词
简单多边形
计算几何
可见点问题
计算机图形学
Simple polygon, point visibility, visible polygon, computational geometry.
