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

作者：李可; 高清维^*; 卢一相; 孙冬; 竺德

来源：自动化学报, 2022, 48(12): 2972-2980.

DOI：10.16383/j.aas.c190590

• 平面点集
• 凸包
• 正交化分割
• 并行算法

为解决实际工程应用中具有超大规模的平面点集的凸包计算问题,提出了一种基于点集所在区域正交化分割的新算法.利用点集几何结构的部分极点对平面点集进行正交化分割,以获取不相干的点集子集簇,再对所有点集子集分别计算其凸包极点,最后合并极点得到凸包点集.在不同层级的正交化分割过程中,根据已知极点的信息,逐层舍去对于凸包极点生成没有贡献的无效点,进而提高算法运行效率.在与目前常用凸包算法的对比实验中,该算法处理超大规模的平面点集时稳定性高且速度更快.

• 单位
  安徽大学; 自动化学院