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 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）.

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