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

摘要：

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

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

所属期刊栏目：48

分类号：P301.6;TP391.41;F231.3

资助基金：国家自然科学基金;国家自然科学基金;安徽省自然科学基金;安徽省自然科学基金

在线出版日期：2023-01-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：2972-2980