【摘要】 凸包问题是计算几何的基本问题,分为平面点集凸包和多边形凸包2类。对传统点集快速凸包算法进行改进,通过找到点集中8个方向的极值点来准确地确定凸包上的部分顶点,得到凸包的粗略逼近,接着在逼近结果上进行遍历,使用链表或栈这样的数据结构,找到逼近结果中连续2个顶点之间的漏检点,从而得到完整的凸包。整个过程达到复杂度下限,且在通常情况下接近线性时间。该方法已经有效地应用于基于控制点的图像配准中。更多还原

【Abstract】 Convex hull is the basic topic in computational geometry.Convex hull of point set and that of a polygon are two classes of it.Based on quickqull algorithm,an improved algorithm to determine the convex hull of 2-D point set was proposed in this paper.After finding points at eight defined extremal positions,some vertices of convex hull can be exactly determined,thus the coarse approximation of convex hull was formed.Refinement was implemented by scanning the coarse result to find the missed vertices.This can be achieved with such data structure as linklist or stack.In general case,the whole process has a computational complexity near linear time.The proposed algorithm has been applied in control points-based image registration effectively.更多还原