简单多边形顶点凹凸性判断算法综述

An Analysis and Investigation of Algorithms for Identifying Convexity-Concavity of a Simple Polygon

简单多边形顶点凹凸性判断算法种类繁多,在模式识别及计算机图形学等领域具有重要应用。为了研究不同种类算法的内在联系与区别,以便在实际应用中根据情况选择合适的算法,分析了目前较为流行的角度法、左右点法、矢量面积法、向量积法、射线法、斜率法和极点顺序法等算法。经过详细的推导论证发现,这些算法都可以使用公式b=p*m来表示,且各种算法在本质上是等价的。但通过对算法计算量的对比,推荐在程序设计中使用向量积法、射线法和斜率法。

Algorithms for identifying convexity - concavity of a simple polygon has a very important application in many fields. The authors analyzed the present popular algorithms for identifying convexity - concavity of a simple polygon such as angling method, left - right - point method, vector - area method, vector - product method, raying method, slopping method and extremity - vertices - order method. A detailed derivation of these algorithms has revealed that these algorithms can all use the formula b = p ＊ m as the expression, and are equivalent to each other in nature; nevertheless, the pole -order method still have some problems to be further studied. Based on an analysis of the computation, the authors hold that theoretically the vector - product method, the slopping method and the raying method could be used effectively in programming.