An Algorithm for Rapidly Identifying Convexo-Concave Vertices of Simple Polygon Based on Comparing the Slopes of Two Adjacent Edge Vectors
Pang Ming-yong · Journal of Engineering Graphics · 2004
For a given simple polygon in plane that all its edge vectors are connected sequentially in clockwise or counterclockwise sense, a feasible approach of identifying convexo-concave vertices of it is to calculate the sign of the cross-products of its adjacent edge vector pairs. This will expend product operators at least 2 times for each vertex. In this paper, a new algorithm, which has time-complexity of )(nO, to rapidly identify the orientation of a arbitrary simple planar polygon and convexity-concavity of its vertices is presented. In the algorithm, the plane is divided into two parts by a line contacted with a vertex of the polygon and 4 configurations of two vertices in the two parts adhered to the vertex can be obtained subsequently. Each configuration gives us a relation between convexity-concavity of vertices of the polygon and the slopes of lines decided by two edge vectors. According to the relation, the convexity-concavity of the vertices can be determined using a predicting and checking method and no more than one times of the product operating is involved in calculation for a vertex.