一种基于多核架构的计算凸壳的并行方法

摘要

本发明针对上述现有凸壳算法存在的不足，提供了一种基于多核架构的计算凸壳的并行算法，包括以下步骤：（1）找到初始点集合的初始不完全凸壳，其各边用逆时针方向的有向边表示；（2）根据初始不完全凸壳对点集合进行分类，找出各条有向边的所有外点；（3）迭代地并行地生长初始不完全凸壳中的每一条有向边；（4）删除最终所得凸壳上的非凸壳顶点。本发明有效地对原算法进行了优化从而充分节省了运算资源。并对原算法中点集分类过程和迭代过程进行了并行扩展，充分利用了多核处理器的并行计算资源；更进一步通过并行、串行的自适应选择来控制并行任务粒度以控制并行加速比，并消除了可能产生的瓶颈。