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

A FAST POINT VISIBILITY ALGORITHM FOR SIMPLE POLYGON

作　　者：金文华[1,2] 何涛[1,2] 唐卫清 唐荣锡[1,2] 刘慎权 

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

出　　处：《计算机学报》1999年第3期275-282,共8页Chinese Journal of Computers

基　　金：国家自然科学基金

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

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

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术] O24[自动化与计算机技术—计算机科学与技术]