基于二叉树的散乱点集快速凸包算法

作者：刘广忠; 黄琳娜

来源：测绘科学, 2008, (04): 87-88+86.

• 计算机应用
• 散点集
• 凸包
• 二叉树
• 算法 computer application
• discrete point set
• convex hull
• binary tree
• algorithm

在右壳树和左壳树概念的基础上,提出了基于二叉树的散乱点集快速凸包算法,它在查找每一个凸包顶点的同时,通过去除若干非凸包顶点来迅速、动态地减小散点集的规模,通常情况下能达到线性时间复杂度。算法省却了凸包顶点间连接关系的判断过程,适用于任何复杂的散点分布情况,并且简单,易于实现。

• 单位
  河北工程技术高等专科学校