基于象限划分的简单多边形方向与顶点凸凹性快速判别算法  

AN ALGORITHM FOR RAPIDLY IDENTIFYING THE ORIENTATION AND CONVEXO-CONCAVE VERTICES OF SIMPLE POLYGON

作　　者：庞明勇[1] 卢章平[2] 

机构地区：[1]湖州师范学院信息工程学院,浙江湖州313000 [2]江苏大学图形技术研究所,江苏镇江212013

出　　处：《计算机应用与软件》2005年第9期111-114,共4页Computer Applications and Software

摘　　要：文中提出一种快速判别简单多边形方向与顶点凸凹性的新算法。通过对简单多边形的每一个顶点引入伴随坐标系,将平面划分为与该顶点相关的四个部分;由此可以得到简单多边形中与该顶点相邻的两个顶点在该平面划分中的16种配置关系;不同的配置关系对判别该顶点的凸凹性所需要的计算量是不同的,从而使大量凸凹性判别工作由“比较”运算来完成,只有在必要时才运用“乘/除法”运算;算法利用“假设-检测”方法,通过获取诸顶点中横坐标值最大的顶点,最终确定简单多边形的方向和诸顶点的凸凹性。文中算法的时间复杂度为O(n)。一般情况下,计算一个顶点的凸凹性所使用的乘法次数平均不超过一次,最坏时也仅为一次。In this paper, a new algorithm to rapidly identify the orientation of a simple planar polygon and convexity-concavity of its vertices is presented. For a given simple polygon in plane that all its edge vectors are connected sequentially in clockwise or counterclockwise sense,a local reference frame, which give the plane a division,is constructed at each vertex of the ploygon. According to the frame, 16 configurations of two vertices neighboring one vertex of the polygon are obtained. Because different case in the configurations has inconsistently need of expensive calculation, a few “product”operators, which are employed to determine convexity-concavity for each vertex in traditional algorithm, are replaced by “ relation” operators here. By obtaining the maximal X-coordinate vertex of the polygon,a “predicting-checking” method is used to finally determine the orientation of a simple planar polygon and convexity-concavity of its vertices. Our algorithm has time-complexity of O （n）. Further, for each vertex,the approach uses averagely “product” operator no more than one times.

关 键 词：简单多边形 多边形方向 顶点凸凹性 象限划分 算法 判别算法 象限 平面划分 时间复杂度 快速判别 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术] TP75[自动化与计算机技术—计算机科学与技术]