简单多边形集凸包的快速算法  

A Fast Algorithm for Computing Convex Hull of a Set of Simple Polygons

作　　者：毛定山[1] 崔先国[2] 李行[3] 吴哲辉[4] 

机构地区：[1]中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室,北京100101 [2]山东科技大学地球信息科学与工程学院,山东青岛266510 [3]华东师范大学河口海岸学国家重点实验室,上海200062 [4]山东科技大学信息科学与工程学院,山东青岛266510

出　　处：《工程图学学报》2007年第6期96-101,共6页Journal of Engineering Graphics

基　　金：国家自然科学基金资助项目(40571129);973计划资助项目(2006CB701305)

摘　　要：提出了一个简单多边形集凸包的快速算法。先求出每个简单多边形的(子)凸包,根据凸包的切线性质,从有关的子凸包中抽取一段严格单调的折线。应用归并排序方法把位于一条直线右侧的一组严格单调的折线合并成一条折线,把合并后的折线和子凸包集的外接矩形上的边连结成一条封闭折线,即一个简单多边形,使其能够把所有子凸包包围起来,最后求出这个简单多边形的凸包。算法的时间复杂度为线性O(n),并且给出一个例子进行了验证。A fast algorithm for computing convex hull of a set of simple polygons is presented. According to the tangent property of convex hull, a strict monotone polygonal line is extracted from the related sub-convex-hulls of simple polygons, which are constructed based on the algorithm of convex hull of simple polygon, and then some strict monotone polygonal lines are merged to a strict monotone polygonal line, so that these strict monotone polygonal lines and some edges that are on the box of the set of sub-convex-hulls form a closed polygonal line, namely a simple polygon. The time complexity of the algorithm is linear. An example is taken to verify the algorithm.

关 键 词：计算机应用 多边形集凸包 单调折线 归并排序 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]