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

简单多边形可见点问题是计算几何的基本问题之一。在许多领域均有应用。本文在参考现有算法的基础上，提出了改进的方法，文中方法先用射线法求取第一个可见点，然后利用文中设定的规则搜索后续可见点。

A FAST POINT VISIBILITY ALGORITHM FOR SIMPLE POLYGON

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.