离散点集最小包围圆算法分析与改进

被引:11
作者
李红军 [1 ,2 ]
张晓鹏 [2 ]
机构
[1] 北京林业大学理学院
[2] 中国科学院自动化研究所模式识别国家重点实验室&中法联合实验室
关键词
最小包围圆; 随机增量算法; 最小包围圆性质; 计算几何;
D O I
暂无
中图分类号
TP301.6 [算法理论];
学科分类号
摘要
针对平面上的离散点集求取最小包围圆的问题,评述现有算法并给出一种改进算法,称为较远点对定义初始包围圆的增量算法。首先概述了几条对算法理解和设计有直接影响的最小包围圆性质或判定;然后对求取最小包围圆的随机增量算法、最远点优先渐近算法、对偶决策算法等3种典型算法进行概述和简要分析;再对随机增量算法和最远点优先渐近算法进行改进;最后,以二维区域随机点集、一维共线随机点集和共线有序点集3类数据进行实验对比。实验结果表明,最远点优先渐近算法是过去3种算法中效率最高的;论文提出的较远点对定义初始包围圆的增量算法大大提高了随机增量算法的时间效率,是该文所列举的方法中最快的算法,并且是一种确定性算法。离散点集最小包围圆的快速计算有助于碰撞检测和机器人等领域的广泛应用。
引用
收藏
页码:34 / 38
页数:5
相关论文
共 1 条
[1]   求一个包含点集所有点的最小圆的算法 [J].
汪卫 ;
王文平 ;
汪嘉业 .
软件学报, 2000, (09) :1237-1240