摘要
本文用三维空间来解决二维平面问题，从而得出了一个简单的点与有向线段之间关系的判别式，并在此基础上根据凸凹点的性质及有向多边形的性质提出了不用解任何方程组也不用计算三角函数的判定平面多边形的简单性、方向及内外点的简单、强健而高效的算法．
This paper solves the two-dimension problems in three-dimensionspace, therefor gets a simple equation for determining the position of a pointrelative to an oriented line segment. Based on the equation, the convex and concavequality of a polygon's venices and the relation of convex venices and concavevenices with the orientation of polygon, a simple and efficient algorithm for theorientation test of simple polygon is presented, it can deal with not only 2D problems,but also 3D problems. Based on this equation and the scan line method, the specialquadrilateral area for the inclusion test of simple polygon is found. This set ofalgorithms are simple, efficient and robust, it is not necessary that solving equationsystems and using trigonometric functions. Comparisons of these algorithms withthe latest algorithms are given in the end of this paper. These algorithms have thefollowing features: 1) They are easy to program and require the minimumcalculation. They are more efficient and faster than the latest algorithms. The more thereare venices of a polygon, the more efficient the algorithms are; 2) Thesealgorithms will not cause extra cases and can be used universally.
出处
《计算机学报》
EI
CSCD
北大核心
1998年第2期183-187,共5页
Chinese Journal of Computers
基金
国家自然科学基金
国家教委博士点专项基金
关键词
计算几何
多边形
算法
Computational geometry, simple polygon, algorithm
