利用正负划分性求平面点集凸包的最优算法

摘要

求平面点集的凸包是计算几何的一个基本算法.目前的算法较多,但这些算法均较复杂,为降低算法复杂性,首先从分析直线的正负划分性入手,利用其来对平面点集进行分类,以简化点到直线的距离计算;然后进一步详细地给出了一种改进的求平面任意散乱点集凸包的新算法.该算法在搜索凸包时,较目前流行的算法中所采用的前瞻回溯法既简单又速度快,该算法较传统的算法更是优越,尤其他不需要计算角度和欧氏距离.结果表明,利用该算法求任意平面散乱点集凸包不仅计算准确,而且计算过程中仅仅用到加、减、乘、比较运算.这样不仅使算法的每一步骤的时间复杂性大大降低,而且也使得整个算法的时间复杂性大大降低.经过分析,该算法也是一个最优的算法.