An efficient convex hull algorithm for planar point sets
In order to improve the efficiency of convex hull calculation,three-level filtering measures have been proposed based on the characteristics of orthophoto point clouds of islands.These measures involve downsampling the planar point set to a pseudo-edge point set and sorting it,followed by improvements to the Graham algorithm.By calculating the point clouds of six islands including Kaishan Island in the Yellow Sea,and comparing them with multiple classical algorithms under three types of situations:normal,concentrated,and scattered,the results show that the average efficiency of this algorithm is 1.68 times that of the Quickhull algorithm,8.93 times that of the Andrew algorithm,and 20.65 times that of the Graham algorithm.Therefore,this algorithm can be regarded as a key algorithm for calculating convex hulls of orthophoto point clouds of islands,coastlines,and independent structures.
orthophoto point cloudconvex hull calculationplanar point setsextreme pointsapproximate maximum inscribed circle
国家科技期刊平台
NSTL
万方数据
