Optimum Algorithm for Constructing Convex Hull of Planar Point Set Utilizing Plus or Minus Characteristic of Demarcation
Hao Jian-qiang · 2007
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.