| 求平面多边形集凸壳的方法 |
| |
| 引用本文： | 赵军,高满屯,王三民.求平面多边形集凸壳的方法[J].计算机工程与应用,2011,47(1):205-207. |
| |
| 作者姓名： | 赵军 高满屯 王三民 |
| |
| 作者单位： | 1.兰州交通大学 数理软件学院，兰州 730070 2.西北工业大学 机电学院，西安 710072 |
| |
| 基金项目： | 国家自然科学基金重点项目No.50875210; 兰州交通大学“青蓝”人才工程资助计划(No.QL-06-11A)~~ |
| |
| 摘 要： | 提出一种计算平面多边形集凸壳的快速算法。将多边形集的凸壳根据极值点划分为右上、左上、左下、右下四段，同时对集合中多边形利用其极值点提取右上、左上、左下、右下四个点列段，凸壳的每一段仅受多边形同一类点列段的影响。根据多边形集合的极值点确定四个矩形区域对四类点列段进行筛选，再按给定规则在矩形区域中进行初始找点，可求出四段凸壳初始点列，它们按顺序可确定一平面多边形，求出到此多边形的凸壳即为所求多边形集的凸壳。算法通过分段、分类、筛选等措施提高了计算效率，并且易于实现，其时间复杂度为O（N）。
|
| 关 键 词： | 凸壳 简单多边形 极值点 多边形集 |
| 收稿时间： | 2009-4-17 |
| 修稿时间： | 2009-6-29
|
Efficient convex hull method for simple polygon set In plane |
| |
| ZHAO Jun,GAO Mantun,WANG Sanmin.Efficient convex hull method for simple polygon set In plane[J].Computer Engineering and Applications,2011,47(1):205-207. |
| |
| Authors: | ZHAO Jun GAO Mantun WANG Sanmin |
| |
| Affiliation: | 1.School of Mathematics，Physics & Software Engineering，Lanzhou Jiaotong University，Lanzhou 730070，China 2.School of Mechatronical Engineering，Northwestern Polytechnical University，Xi’an 710072，China |
| |
| Abstract: | An efficient algorithm for computing the convex hull of simple polygon set is proposed.Firstly,four vertex clusters are extracted from each polygon on the basis of extremity point,and are classified into four groups(right-top,left-top,left-bottom,right-bottom)by their locations in polygon.The convex hull can also be separated into four parts(right-top,left-top,left-bottom,right-bottom) and each part of the convex hull is associated with the same cluster group.Then,the cluster group is filtrated according to... |
| |
| Keywords: | convex hull simple polygon extremity point set of polygon |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
