多边形的简单性、方向及内外点的判别算法

本文用三维空间来解决二维平面问题，从而得出一个简单的点与有向线段之间关系的判别式，并在此基础上根据凸凹点的性质及有向多边形的性质提出了不用解任何方程组也不用于计算三角函数的判定平面多边形的简单性，方向及内外点的简单，强健而高效的算法。

SIMPLICITY, ORIENTATION, AND INCLUSION TEST ALGORITHMS FOR POLYGONS

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.