Orientation, Convexity-Concavity and Inclusion Test Algorithms for Polygons

Orientation of polygon, convexity or concavity of vertices and point inclusion test are three fundamental problems in geometry. In this paper, a novel method to identify the orientation of a triangle using its extreme vertex order is proposed. The orientation of a polygon can be determined by a triangle which is composed of an extreme vertex and its two adjacent vertices. It determines the convexity-concavity of the vertex whether the orientation of polygon is same as the orientation of a triangle which is composed of a vertex and its two adjacent vertices or not. Even-odd rule is employed to point inclusion test, but the ray is omitted and intersection calculation is avoided. Test results show the high efficiency and stability of this algorithm.