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

被引：10

作者：

毛定山 ^{[1
]}

崔先国 ^{[2
]}

李行 ^{[3
]}

吴哲辉 ^{[4
]}

机构：

[1] 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室

[2] 山东科技大学地球信息科学与工程学院

[3] 华东师范大学河口海岸学国家重点实验室

[4] 山东科技大学信息科学与工程学院

来源：

工程图学学报 | 2007年 / 06期

关键词：

计算机应用; 多边形集凸包; 单调折线; 归并排序;

D O I：

暂无

中图分类号：

TP391.4 [模式识别与装置];

学科分类号：

0811 ; 081101 ; 081104 ; 1405 ;

摘要：

提出了一个简单多边形集凸包的快速算法。先求出每个简单多边形的(子)凸包,根据凸包的切线性质,从有关的子凸包中抽取一段严格单调的折线。应用归并排序方法把位于一条直线右侧的一组严格单调的折线合并成一条折线,把合并后的折线和子凸包集的外接矩形上的边连结成一条封闭折线,即一个简单多边形,使其能够把所有子凸包包围起来,最后求出这个简单多边形的凸包。算法的时间复杂度为线性O(n),并且给出一个例子进行了验证。

引用

页码：96 / 101

页数：6

共 8 条

[1] 寻求平面上线段集凸壳的扫描算法 [J].

周培德 ;

张金玲 .

工程图学学报, 2003, (04) :110-115

[2] 简单多边形凸包的双动线检测算法 [J].

孔宪庶 ;

蔡洪学 .

计算机学报, 1994, (08) :596-600

[3] 对平面简单多边形求凸包的线性时间算法 [J].

汪嘉业 ;

刘鼎元 .

计算机学报, 1989, (01) :38-43

[4]

T. M. Chan.Output-Sensitive Results on Convex Hulls, Extreme Points, and Related Problems[J].Discrete & Computational Geometry,1996

[5]

D. T. Lee.On finding the convex hull of a simple polygon[J].International Journal of Parallel Programming,1983

[6]

M.deBerg[等]著,邓俊辉译.计算几何[M].北京:清华大学出版社,2005

[7]

周培德著.计算几何[M].北京:清华大学出版社,2005

[8]

严蔚敏,吴伟民编著.数据结构[M].北京:清华大学出版社,1997

← 1 →