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

	简单多边形集凸包的快速算法
	毛定山 2; 崔先国 3; 李行 1; 吴哲辉 3
刊名	工程图学学报
	2007
卷号	028 期号:006 页码:96
ISSN号	1003-0158
英文摘要	提出了一个简单多边形集凸包的快速算法。先求出每个简单多边形的（子）凸包，根据凸包的切线性质，从有关的子凸包中抽取一段严格单调的折线。应用归并排序方法把位于一条直线右侧的一组严格单调的折线合并成一条折线，把合并后的折线和子凸包集的外接矩形上的边连结成一条封闭折线，即一个简单多边形，使其能够把所有子凸包包围起来，最后求出这个简单多边形的凸包。算法的时间复杂度为线性O（n），并且给出一个例子进行了验证。
语种	英语
内容类型	期刊论文
源URL	[http://ir.igsnrr.ac.cn/handle/311030/116138]
专题	中国科学院地理科学与资源研究所
作者单位	1.华东师范大学 2.中国科学院地理科学与资源研究所 3.山东科技大学
推荐引用方式 GB/T 7714	毛定山,崔先国,李行,等. 简单多边形集凸包的快速算法[J]. 工程图学学报,2007,028(006):96.
APA	毛定山,崔先国,李行,&吴哲辉.(2007).简单多边形集凸包的快速算法.工程图学学报,028(006),96.
MLA	毛定山,et al."简单多边形集凸包的快速算法".工程图学学报 028.006(2007):96.