SIMPLICITY, ORIENTATION, AND INCLUSION TEST ALGORITHMS FOR POLYGONS
Zhi Wang · Chinese Journal of Computers · 1998
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.