|
|||||
|
|
| 简单多边形集凸包的快速算法 | |
| 引用本文： | 毛定山,崔先国,李行,WU Zhe-hui,吴哲辉. 简单多边形集凸包的快速算法[J]. 工程图学学报, 2007, 28(6): 96-101 |
| 作者姓名： | 毛定山 崔先国 李行 WU Zhe-hui 吴哲辉 |
| 作者单位： | 1. 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室,北京,100101;山东科技大学信息科学与工程学院,山东,青岛,266510 2. 山东科技大学地球信息科学与工程学院,山东,青岛,266510 3. 华东师范大学河口海岸学国家重点实验室,上海,200062 4. 山东科技大学信息科学与工程学院,山东,青岛,266510 |
| 基金项目： | 国家自然科学基金 , 国家重点基础研究发展计划(973计划) |
| 摘 要： | 提出了一个简单多边形集凸包的快速算法.先求出每个简单多边形的(子)凸包,根据凸包的切线性质,从有关的子凸包中抽取一段严格单调的折线.应用归并排序方法把位于一条直线右侧的一组严格单调的折线合并成一条折线,把合并后的折线和子凸包集的外接矩形上的边连结成一条封闭折线,即一个简单多边形,使其能够把所有子凸包包围起来,最后求出这个简单多边形的凸包.算法的时间复杂度为线性O(n),并且给出一个例子进行了验证. |
| 关 键 词： | 计算机应用 多边形集凸包 单调折线 归并排序 |
| 文章编号： | 1003-0158（2007）06-0096-06 |
| 收稿时间： | 2006-08-08 |
| 修稿时间： | 2006-08-08 |
A Fast Algorithm for Computing Convex Hull of a Set of Simple Polygons |
|
| WU Zhe-hui. A Fast Algorithm for Computing Convex Hull of a Set of Simple Polygons[J]. Journal of Engineering Graphics, 2007, 28(6): 96-101 | |
| Authors: | WU Zhe-hui |
| Abstract: | 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. |
| Keywords: | computer application convex hull of polygon set monotone polygonal line merge sort |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |