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.%针对以往判断简单多边形顶点凸凹性算法计算量偏大的问题,在基于象限的简单多边形顶点凸凹性判断算法的基础上提出一种改进的识别算法.将直角坐标平面平均划分为八个区域,利用角两边在八个区域内的特性来快速判断角度的范围;将顶点凸凹性判断转化为顶点内角范围的判断,并将其引入多边形方向的判别,从而以简单的判断和逻辑运算代替耗时的乘法运算,加快了判断速度.实验分析表明,改进后的算法能有效地避免较为耗时的乘法运算,提高判断效率.
展开▼
