基于象限划分的简单多边形方向与顶点凸凹性快速判别算法

• 作者: 卢章平 庞明勇
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: 简单多边形 多边形方向 顶点凸凹性 象限划分 算法
• 年，卷（期）: 2005,（9）
• 所属期刊栏目: 算法
• 页码范围: 111-114
• 页数: 4页
• 分类号: TP3
• 字数: 5410字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386X.2005.09.043

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	卢章平	江苏大学图形技术研究所	226	1599	18.0	29.0
2	庞明勇	湖州师范学院信息工程学院	2	4	1.0	2.0