CGAL Delaunay三角剖分性能优化咨询：百万级点集提速方案

一、编译与CGAL配置优化 #

• 开启最高等级编译优化：编译时添加-O3参数，CGAL的模板化算法在高优化等级下性能提升显著。
• 启用并行计算支持：如果CGAL编译时依赖了TBB或OpenMP，在定义三角剖分类时指定Parallel_tag，利用多核加速插入过程：

  typedef CGAL::Delaunay_triangulation_2<
      Kernel,
      CGAL::Triangulation_data_structure_2<
          CGAL::Triangulation_vertex_base_2<Kernel>,
          CGAL::Triangulation_face_base_2<Kernel>,
          CGAL::Parallel_tag
      >
  > Delaunay;
  

• 选择合适的内核：在精度要求允许的情况下，使用CGAL::Exact_predicates_inexact_constructions_kernel替代精确构造内核，能大幅降低计算开销。

二、分块构建与合并方案 #

分块构建的核心是拆分任务并行处理，再合并结果，具体步骤如下：

1. 点集分块：将1000万点划分为多个子块（建议每个子块50-100万点），子块间保留一定重叠区域，避免合并时边界三角剖分断裂。
2. 并行子剖分：为每个子块单独构建Delaunay三角剖分，这一步可通过多线程并行执行，充分利用多核CPU。
3. 合并子剖分：创建全局三角剖分对象，将每个子剖分的点增量插入其中。注意提前对全局点集去重，避免重复插入：

   Delaunay global_dt;
   // 假设sub_delaunays是存储子剖分的容器
   for (const auto& sub_dt : sub_delaunays) {
       for (auto v = sub_dt.finite_vertices_begin(); v != sub_dt.finite_vertices_end(); ++v) {
           global_dt.insert(v->point());
       }
   }
   

   若CGAL版本支持，可尝试使用join方法直接合并两个剖分，效率比逐点插入更高，但要求两个剖分的区域有重叠。

三、数据预处理优化 #

• 点集去重：先对原始点集去重，减少无效插入操作。可通过排序+去重实现：

  std::vector<Point> points = read_csv("points.csv");
  std::sort(points.begin(), points.end());
  auto last = std::unique(points.begin(), points.end());
  points.erase(last, points.end());
  

• CSV读取加速：如果文件读取是瓶颈，改用fscanf或内存映射文件读取整个CSV，避免逐行流读取的开销。
• 内存布局优化：确保点集存储在连续内存中（如std::vector），避免内存碎片化影响插入效率。

四、进阶优化方向 #

• 点集简化：在精度允许的前提下，使用CGAL::Grid_simplify_point_set对密集点集进行网格简化，减少点的数量，直接降低剖分时间。
• GPU加速：CGAL本身不支持GPU，但可将点集导出到CUDA等GPU加速的Delaunay库完成剖分，再导入CGAL进行后续插值计算。
• 动态三角剖分：若不需要保留完整的全局剖分，可考虑动态插入/删除点，但该方案仅适用于特定场景。

附参考代码示例 #

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <fstream>
#include <vector>
#include <algorithm>

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point;
typedef CGAL::Delaunay_triangulation_2<Kernel> Delaunay;

std::vector<Point> read_csv(const std::string& filename) {
    std::vector<Point> points;
    std::ifstream in(filename);
    double x, y;
    // 假设CSV每行是x,y格式
    while (in >> x >> y) {
        points.emplace_back(x, y);
    }
    return points;
}

int main() {
    std::vector<Point> points = read_csv("points.csv");
    
    // 点集去重
    std::sort(points.begin(), points.end());
    auto last = std::unique(points.begin(), points.end());
    points.erase(last, points.end());
    
    Delaunay dt;
    dt.insert(points.begin(), points.end());
    
    // 后续插值计算逻辑...
    
    return 0;
}

内容的提问来源于stack exchange，提问作者Daniel Ocanto