求平面多边形集凸壳的方法

• 作者: 王三民 赵军 高满屯
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 凸壳 简单多边形 极值点 多边形集
• 年，卷（期）: 2011,（1）
• 所属期刊栏目: 图形、图像、模式识别
• 页码范围: 205-207,233
• 分类号: TP301.6
• 字数: 2816字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2011.01.058

摘要

提出一种计算平面多边形集凸壳的快速算法.将多边形集的凸壳根据极值点划分为右上、左上、左下、右下四段,同时对集合中多边形利用其极值点提取右上、左上、左下、右下四个点列段,凸壳的每一段仅受多边形同一类点列段的影响.根据多边形集合的极值点确定四个矩形区域对四类点列段进行筛选,再按给定规则在矩形区域中进行初始找点,可求出四段凸壳初始点列,它们按顺序可确定一平面多边形,求出到此多边形的凸壳即为所求多边形集的凸壳.算法通过分段、分类、筛选等措施提高了计算效率,并且易于实现,其时间复杂度为O(N).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	高满屯	西北工业大学机电学院	114	795	14.0	24.0
2	王三民	西北工业大学机电学院	173	1875	21.0	37.0
3	赵军	兰州交通大学数理软件学院	28	187	8.0	12.0