海洋测绘2024，Vol.44Issue(1)：53-57,5.DOI:10.3969/j.issn.1671-3044.2024.01.011
一种高效的平面点集凸包算法
An efficient convex hull algorithm for planar point sets
摘要
Abstract
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.关键词
正射点云/凸包计算/平面点集/极点/似最大内圆Key words
orthophoto point cloud/convex hull calculation/planar point sets/extreme points/approximate maximum inscribed circle分类
天文与地球科学引用本文复制引用
梁彪,常岑..一种高效的平面点集凸包算法[J].海洋测绘,2024,44(1):53-57,5.基金项目
江苏省自然资源厅科技项目(2023019). （2023019）
