快速凸包并行设计与研究

Parallel Design and Research of Fast Convex Hull

凸包在计算几何中占有着重要地位,不仅仅是作为理论基础,其他研究领域内求解凸包的思想可以简化复杂的问题。传统的凸包生成算法在处理点集规模较大的数据时,消耗时间随之增多影响解决问题的高效性。本文基于三维快速凸包算法,通过对快速凸包算法深入分析,分割计算任务,进而提取算法能够并行部分。实验表明结合GPU并行计算能力可以降低大规模数量点集情况下计算消耗的时间,算法的时间性能上得到加速。

Convex hull occupies an important position in computational geometry,it is not only the theoretical basis,but can simplify complex problems in other research fields.Dealing with large point set scale of data,traditional convex hull generation algorithm consumes time increasely and affects efficiency of solving problems.The article analyzes fast convex hull algorithm deeply based on 3D fast convex hull algorithm,segments computation task,and extracts parallel parts of algorithm.Experiments shows combining GPU parallel computing capacity can reduce computation time of large scale point sets,and accelerate time performance of algorithm.