基于区域正交化分割的平面点集凸包算法  

A Convex Hull Algorithm for Plane Point Sets Based on Region Normalization Segmentation

作　　者：李可 高清维[1,2] 卢一相 孙冬[1,2] 竺德 LI Ke;GAO Qing-Wei;LU Yi-Xiang;SUN Dong;ZHU De(School of Electrical Engineering and Automation,Anhui University,Hefei 230601;Key Laboratory of Computational Intelligence and Signal Processing of Ministry of Education,Anhui University,Hefei 230601)

机构地区：[1]安徽大学电气工程与自动化学院,合肥230601 [2]安徽大学计算智能与信号处理教育部重点实验室,合肥230601

出　　处：《自动化学报》2022年第12期2972-2980,共9页Acta Automatica Sinica

基　　金：国家自然科学基金(61402004,61370110);安徽省自然科学基金(2008085MF183,2008085MF192)资助。

摘　　要：为解决实际工程应用中具有超大规模的平面点集的凸包计算问题,提出了一种基于点集所在区域正交化分割的新算法.利用点集几何结构的部分极点对平面点集进行正交化分割,以获取不相干的点集子集簇,再对所有点集子集分别计算其凸包极点,最后合并极点得到凸包点集.在不同层级的正交化分割过程中,根据已知极点的信息,逐层舍去对于凸包极点生成没有贡献的无效点,进而提高算法运行效率.在与目前常用凸包算法的对比实验中,该算法处理超大规模的平面点集时稳定性高且速度更快.In order to solve the convex hull calculation problem of ultra-large scale planar point set in practical engineering applications,a new algorithm based on orthogonal segmentation of the region where the point set is located is designed.The partial point of the point set geometry is used to orthogonalize the plane point set to obtain the incoherent point set subset cluster,and then the convex hull poles are calculated for all the point set subsets,and finally the convex hull point set is obtained by combining the poles.In the process of orthogonalization and segmentation in different levels,according to the information of the existing convex hull poles,many of invalid points are discarded layer by layer,which improves the efficiency of the algorithm.In the comparison experiment with the commonly used convex hull algorithm,the proposed algorithm has high stability and speed when dealing with super large-scale planar point sets.

关 键 词：平面点集 凸包 正交化分割 并行算法 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]