一种高效的平面点集凸包算法  

An efficient convex hull algorithm for planar point sets

作　　者：梁彪 常岑 LIANG Biao;CHANG Cen(Jiangsu Provincial Surveying and Mapping Product Quality Supervision and Inspection Station,Nanjing 210018,China)

机构地区：[1]江苏省测绘产品质量监督检验站,江苏南京210018

出　　处：《海洋测绘》2024年第1期53-57,共5页Hydrographic Surveying and Charting

基　　金：江苏省自然资源厅科技项目(2023019)。

摘　　要：为了提高凸包计算的效率,针对海岛正射点云的特点,提出了三级过滤措施,将平面点集抽稀至似边缘点集并排序,在此基础上改进了Graham算法,算法的时间复杂度为线性对数阶。通过对黄海开山岛等6个海岛点云进行计算,在普通、集中、扩散等3种类型情况下与多个经典算法进行对比,结果表明该算法平均运行效率为Quickhull算法的1.68倍、Andrew算法的8.93倍、Graham算法的20.65倍。因此,该算法可以被作为海岛、海岸、独立建筑物等正射点云凸包计算的关键算法。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 dow nsampling 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.

关 键 词：正射点云 凸包计算 平面点集 极点 似最大内圆 

分 类 号：P23[天文地球—摄影测量与遥感]