An Algorithm for Determining the Orientation and Convexity-Concavity of Simple Polygons

摘要

This paper presents an algorithm which can determine the orientation of a polygon according to the sequence of extreme vertexes. The convexity and concavity of polygon vertices can be determined by examining whether the orientation of the triangle formed by the vertex and its two adjacent vertices is the same as the orientation of polygon. However, the existing algorithms need calculate three order-determinant or vector multiplication. By this proposed algorithm, the efficiency of a point inclusion test method has been greatly improved. Test results show the high efficiency and stability of this algorithm.