基于格网划分的海量数据Delaunay三角剖分

Massive Data Delaunay Triangulation Based on Grid Partition Method

提出基于格网划分、面向海量数据的Delaunay三角剖分方法,它首先把数据集划分为若干格网块,按照格网划分的逆序对每个格网块采用基于自适应格网划分的分割 合并算法进行Delaunay三角剖分,把格网块Delaunay三角网中不受边界影响的三角形进行存储并释放内存,然后顺序合并相邻格网块Delaunay三角网,形成全局或类全局Delaunay三角网。该方法对计算机硬件配置要求较低,适合于并行处理,可以实现面向海量数据的Delaunay三角剖分。

A Delaunay triangulation method is brought forward oriented massive data, which based on the grid partition method. It divides the data set into some grid tiles, constructs Delaunay triangulation for each grid tile by divide-and-conquer algorithm based on self-adapt gird partition, and store some unaffected triangles, then merges adjacent Delaunay triangulations to whole or whole-like Delaunay triangulation. This method requires low computer hardware, fits for parallel processing, can process Delaunay triangulation of massive data.