作者：庞明勇; 卢章平简单多边形多边形方向顶点凸凹性象限划分算法判别算法象限平面划分时间复杂度快速判别
摘要：文中提出一种快速判别简单多边形方向与顶点凸凹性的新算法.通过对简单多边形的每一个顶点引入伴随坐标系,将平面划分为与该顶点相关的四个部分;由此可以得到简单多边形中与该顶点相邻的两个顶点在该平面划分中的16种配置关系;不同的配置关系对判别该顶点的凸凹性所需要的计算量是不同的,从而使大量凸凹性判别工作由'比较'运算来完成,只有在必要时才运用'乘/除法'运算;算法利用'假设-检测'方法,通过获取诸顶点中横坐标值最大的顶点,最终确定简单多边形的方向和诸顶点的凸凹性.文中算法的时间复杂度为O(n).一般情况下,计算一个顶点的凸凹性所使用的乘法次数平均不超过一次,最坏时也仅为一次.
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
