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

• 作者: WU Zhe-hui 吴哲辉 崔先国 李行 毛定山
• 来源期刊: 工程图学学报
• 学科: 工学
• 关键词: 计算机应用 多边形集凸包 单调折线 归并排序
• 年，卷（期）: 2007,（6）
• 所属期刊栏目: 计算几何与应用
• 页码范围: 96-101
• 页数: 6页
• 分类号: TP391
• 字数: 2097字
• 语种: 中文
• DOI: 10.3969/j.issn.1003-0158.2007.06.019

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吴哲辉	中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室	88	638	14.0	19.0
3	崔先国	山东科技大学地球信息科学与工程学院	28	253	11.0	15.0
4	李行	华东师范大学河口海岸学国家重点实验室	9	189	8.0	9.0
5	毛定山	中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室	4	43	3.0	4.0
9	WU Zhe-hui	山东科技大学信息科学与工程学院	1	14	1.0	1.0