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

摘要

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