平面点集凸壳的快速近似算法

• 作者: 杨炳儒 樊广俭 马丽平
• 来源期刊: 系统工程与电子技术
• 学科: 工学
• 关键词: 计算几何 多方向极值 近似算法 凸壳 平面点集
• 年，卷（期）: 2008,（4）
• 所属期刊栏目: 系统工程
• 页码范围: 649-651
• 页数: 3页
• 分类号: TP312|TP301.6
• 字数: 3476字
• 语种: 中文
• DOI: 10.3321/j.issn:1001-506X.2008.04.015

摘要

提出并实现了平面点集凸壳的一种新的近似算法--多方向极值法.该算法首先根据用户输入的控制参数,顺序生成一系列极值方向,每个方向有对应的极值表达式;然后扫描平面点集中的点,依每个点的坐标更新各方向上的极值点信息;最后按照一定的顺序装配各极值点并去重,得到该平面点集的一个近似凸壳.实验表明,该算法执行效率高,不但可以单独应用在一些对时间要求比较苛刻而对精度要求不高的场合,而且可以作为快速凸壳算法的一个预处理过程.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨炳儒	北京科技大学信息工程学院	319	4361	32.0	49.0
2	马丽平	河北经贸大学计算机中心	12	45	4.0	6.0
3	樊广俭	河北经贸大学信息技术学院	1	4	1.0	1.0