海量数据的Delaunay三角网并行构建算法

摘要

本文对并行环境下Delaunay三角网的构建进行了研究.针对海量数据处理的高效性要求,提出了一种归并构网方法.该方法根据构网数据的实际分布特点,对数据点按x坐标进行排序,并将排序后的数据按给定的阈值点数依次分配给各线程,构建出一系列的初始子三角网,然后逐轮对相邻的子三角网进行两两归并,直至最终归并为一个三角网.该方法构网过程中子三角网间的相关性小,易于并行处理和流水线作业.实验表明,该算法的时空效率较高,最坏的串行时间复杂度为,一般情况下不超过o(n).