基于区域正交化分割的平面点集凸包算法EI北大核心CSCD

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

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

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.