Abstract:Convex hull is one of the essential issues in computational geometric of planar points set.In recent years,many scholars have put forward many excellent algorithms to calculate the convex hull of the plane point set in real time,which,however,still can not satisfy the practical real-time demand.To this end,a simple but efficient and fast convex hull algorithm is proposed in this paper.Due to the fact that the convex hull points must be located at the edge of the planar point set,the algorithm in this paper can quickly find out the few candidate points of the convex wrapping point,which is the core advantage of this algorithm.Then,by using a simple and effectively-improved Graham scan algorithm which is also put forward by this paper,or any other existing convex hull methods,the points set of the convex hull can be calculated quickly and accurately.Conventional Graham scan algorithm calculate convex hull with one basis point.Based on the convex hull of distribution of candidate points set,the improved algorithm of this paper divides basis points into four subsystems,namely 4 basis points are tested respectively in each part,then mergers all the test results of each parts,and finally gets the complete convex hull.In the experiment,a set of public animals bone points clouds were used.The convex hull calculation is perfectly correct,but the calculation time of this algorithm is 2.22 times less than that of other algorithms when the number of points is about 3×10⁵.When the number of points is about 3×10⁶,the computation time of this algorithm is 5.42 times less than that of other methods.The more points,the more obvious advantages of this algorithm.