基于边向量斜率比较的简单多边形顶点凸凹性快速判别算法

• 作者: 卢章平 庞明勇
• 来源期刊: 工程图学学报
• 学科: 工学
• 关键词: 计算机应用 计算几何 凸凹性判别 边向量比较 简单多边形 算法
• 年，卷（期）: 2004,（3）
• 所属期刊栏目: 计算几何
• 页码范围: 71-77
• 页数: 7页
• 分类号: TP301|TP391.72
• 字数: 4911字
• 语种: 中文
• DOI: 10.3969/j.issn.1003-0158.2004.03.012

摘要

对于给定的平面简单多边形顶点序列,判别多边形方向和顶点凸凹性的传统方法为:先计算多边形相邻边向量的叉积或相邻3个顶点所确定三角形的有向面积,再由叉积或有向面积的符号来确定顶点的凸凹性,使得处理一个顶点需要2次以上的乘法运算.笔者通过边向量斜率的计算和比较,将多边形顶点的凸凹性与边向量的斜率联系起来,并采用"假设-检验"方法,提出了一种快速判别简单多边形方向与顶点凸凹性的新算法,其时间复杂度为,判别多边形任一顶点凸凹性所需的乘法运算平均不超过1次.该算法原理直观简单,实现容易.实际运行结果表明,该算法速度快捷、运行稳定.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	庞明勇	江苏大学图形技术研究所	10	51	4.0	7.0
2	卢章平	江苏大学图形技术研究所	226	1599	18.0	29.0