高级检索

简单多边形凸凹性自识别算法

An Algorithm for Identifying Convexity-Concavity of A Simple Polygon

  • 摘要: 提出一种基于极值顶点构造凸多边形和矢量叉乘的自动识别简单多边形方向性、凸凹性的算法.该算法在稳定性方面采取了有效的措施,避免因极值顶点的奇异性而导致多边形方向性、凸凹性的错误识别,具有良好的可靠性和稳定性.算法原理直观简单,效率高,时间复杂度为O(n).

     

    Abstract: Based on constructing convex-polygon by extremity vertices and computing cross-products of polygon's edge vectors, an algorithm for automatic identifying the orientation, convexity-concavity of a simply polygon is proposed. The algorithm avoids wrong identification of orientation and convexity-concavity of polygon caused by the misleading property of extremity vertices. It is very simple, straight forward and highly efficient. The complexity of its computing time reaches O(n).

     

/

返回文章
返回