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

Efficient convex hull method for simple polygon set in plane

作　　者：赵军[1] 高满屯[2] 王三民[2] 

机构地区：[1]兰州交通大学数理软件学院,兰州730070 [2]西北工业大学机电学院,西安710072

出　　处：《计算机工程与应用》2011年第1期205-207,233,共4页Computer Engineering and Applications

基　　金：国家自然科学基金重点项目No.50875210;兰州交通大学"青蓝"人才工程资助计划(No.QL-06-11A)~~

摘　　要：提出一种计算平面多边形集凸壳的快速算法。将多边形集的凸壳根据极值点划分为右上、左上、左下、右下四段,同时对集合中多边形利用其极值点提取右上、左上、左下、右下四个点列段,凸壳的每一段仅受多边形同一类点列段的影响。根据多边形集合的极值点确定四个矩形区域对四类点列段进行筛选,再按给定规则在矩形区域中进行初始找点,可求出四段凸壳初始点列,它们按顺序可确定一平面多边形,求出到此多边形的凸壳即为所求多边形集的凸壳。算法通过分段、分类、筛选等措施提高了计算效率,并且易于实现,其时间复杂度为O(N)。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 whether it is in the rectangle which is determined by the extremity point of polygon set.Finally,under the rule,four primary point clusters are gained,and they can constitute a polygon that has the same convex hull as the simple polygon set.The efficiency algorithm is easy to be realized and its time complexity is O（N）.

关 键 词：凸壳 简单多边形 极值点 多边形集 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]