Determining Convexo-Concave Vertices of Polygon By Topological Mapping

Given a simple polygon, all its edge vectors are connected sequentially in clockwise or counterclockwise sense. A feasible approach of determining the convexity or concavity of a vertex is to compute the sign of the cross product of its two adjacent edge vectors. In our approach, a circle of certain radius is constructed surrounding each vertex and compute the intersection points of every two adjacent edges with a pair of offset lines parallel to the X-axis and located at both sides of each vertex. Comparing the X-coordinates of these two intersection points immediately predicts the convexity or concavity of a vertex, computing the X-coordinates of line-line intersections points is quicker than computing the cross product of two vectors.