平面散乱点集凸包的快速生成算法

• 作者: 刘广忠 黄琳娜
• 来源期刊: 工程图学学报
• 学科: 地球科学
• 关键词: 计算机应用 凸包生成算法 平面点集凸包 计算几何
• 年，卷（期）: 2008,（4）
• 所属期刊栏目: 计算几何与应用
• 页码范围: 111-114
• 页数: 4页
• 分类号: P301.6
• 字数: 1958字
• 语种: 中文
• DOI: 10.3969/j.issn.1003-0158.2008.04.021

摘要

凸包问题是计算几何的基本问题,在实际工程中得到了广泛的应用.传统的凸包生成算法一般需要两个步骤,首先将离散点按照某种特性排序,然后进行凸包生成.依据快速排序算法的思想,提出一种"一步法"构建平面点集凸包的算法,将构建平面点集的凸包问题与排序问题结合起来,在排序过程中快速生成点集凸包.整个过程达到时间复杂度下限O(nlogn).该算法在"河北省蓄滞洪区信息管理系统"中得到了实际应用,效果理想.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘广忠		9	35	3.0	5.0
2	黄琳娜		21	81	6.0	8.0