基于边向量斜率比较的简单多边形顶点凸凹性快速判别算法
对于给定的平面简单多边形顶点序列,判别多边形方向和顶点凸凹性的传统方法为:先计算多边形相邻边向量的叉积或相邻3个顶点所确定三角形的有向面积,再由叉积或有向面积的符合来确定顶点的凸凹性,使得处理一个顶点需要2次以上的乘法运算.笔者通过边向量斜率的计算和比较,将多边形顶点的凸凹性与边向量的斜率联系起来,并采用”假设-检验”方法,提出了一种快速判别简单多边形方向与顶点凸凹性的新算法,其时间复杂度为O(n),判别多边形任一顶点凸凹性所需的乘法运算平均不超过1次.该算法原理直观简单,实现容易.实际运行结果表明,该算法速度快捷、运行稳定.
计算几何 凸凹性判别 边向量比较 多边形 判别算法
庞明勇 卢章平
江苏大学图形技术研究所(镇江)
国内会议
呼和浩特
中文
71-77
2004-08-01（万方平台首次上网日期，不代表论文的发表时间）