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

Optimum Algorithm for Constructing Convex Hull of Planar Point Set Utilizing Plus or Minus Characteristic of Demarcation

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

Constructing convex hull of planar point set is a basic algorithm in computational geometry. Although the number of current algorithms is increasing, most of them are quite complex. In order to reduce the algorithm complexity, the paper starts with analyzing the Plus or Minus Characteristic of Demarcation of a straight line. The purpose of step is to partition planar point set and to simplify the calculation distance from a point to a straight line. Then an improved algorithm is given which is seeking the convex hull of an arbitrarily distributing planar point set. This algorithm is simpler and the speed is faster than the popular algorithm which has adopted forward-backward method in searching convex hull. Our algorithm is also superior to the traditional algorithm. In particular it is unnecessary to compute the angle, Euclidean distance. Applying the algorithm to seek the convex hull of an arbitrarily distributing planar point set can obtain accurate, results through only addition, subtraction, multiplication and comparision. The method reduces the computing time for of each step therefore it is an optimal algorithm because of its efficiency.