An Efficient Vertices Correlation-Based Algorithm for Identifying Convexo-Concave Vertices of Simple Polygon
The concept of the convexo-concave vertices of a simple polygon is widely used in computer graphics. However,the calculation cost of the classic algorithms for identifying the convexo-concave vertices is very high. The paper deduces the correlation theory of vertices(CTV) in a simple polygon. It sets direction to the generic plane lines, and then classifies the lines according to the direction. Thus, the problem for identifying convexo-concave vertices of a simple polygon is translated from judge whether the vertex is on the right sides or the left sides of the directional line to judge the sign of plane line function. Based on the discussion, a novel algorithm for identifying convexo-concave vertices is described. Time complexity of this algorithm is only O(n). The calculation cost is smaller than conventional algorithms and the algorithm only needs one division to identify each vertex. The experiment shows that the algorithm is stable and highly efficient.
simple polygon convexo-concave vertices correlation theory of vertices, algorithm
ZHENG Jianhua LI Di
Department of Computer Science & Engineering ZhongKai University of Agriculture & Technology Dongsha College of Mechanical Engineering South China University of Technology China Guangzhou, 510640 P.R.C
国际会议
武汉
英文
317-321
2007-07-25（万方平台首次上网日期，不代表论文的发表时间）