基于八区域的简单多边形顶点凸凹性识别算法  

AN ALGORITHM FOR IDENTIFYING CONVEXITY-CONCAVITY VERTICES OF SIMPLE POLYGON BASED ON EIGHT AREAS

作　　者：薛理 杨树文 王中辉 张珊 马吉晶 

机构地区：[1]兰州交通大学测绘与地理信息学院,甘肃兰州730070 [2]甘肃省地理国情监测工程实验室,甘肃兰州730070

出　　处：《计算机应用与软件》2018年第1期330-333,共4页Computer Applications and Software

基　　金：兰州市人才创新创业项目(2015-RC-28);甘肃省科技计划项目(1506RJZA070)

摘　　要：针对以往判断简单多边形顶点凸凹性算法计算量偏大的问题,在基于象限的简单多边形顶点凸凹性判断算法的基础上提出一种改进的识别算法。将直角坐标平面平均划分为八个区域,利用角两边在八个区域内的特性来快速判断角度的范围;将顶点凸凹性判断转化为顶点内角范围的判断,并将其引入多边形方向的判别,从而以简单的判断和逻辑运算代替耗时的乘法运算,加快了判断速度。实验分析表明,改进后的算法能有效地避免较为耗时的乘法运算,提高判断效率。Aiming at the problem that previous algorithms for identifying convexity-concavity vertices of simple polygon have exceeding calculation, an improved recognition algorithm based on quadrantal algorithm is proposed. First of all, the rectangular coordinates plane is divided into eight areas on average in which angel range is determined quickly by using the features of both edges of an angle. Secondly, judgement based on convexity-concavity vertices are transformed the angle range that identifies polygon＇ s direction so that simple judgment and logical operations can take the place of the time-consuming multiplication and speed up the judgment. Experimental analysis showed that the improved algorithm can effectively avoid time-consuming multiplication and improve the efficiency of judgement.

关 键 词：简单多边形 凸凹性 八个区域 方向 

分 类 号：TP319[自动化与计算机技术—计算机软件与理论]