如何通过并行化加速CGAL三角剖分及Alpha Shape算法

问题背景 #

我当前使用CGAL 5.5.2开展项目，涉及2D Delaunay三角剖分、2D约束Delaunay三角剖分及2D Alpha Shape计算。由于输入数据量较大（约4000万个点），计算耗时过长（Alpha Shape计算超11分钟），希望通过CGAL的并行化功能利用多核处理器提升性能，寻求以下指导：

• 如何为上述三类计算启用并使用CGAL并行化；
• 提供代码示例或修改现有代码的步骤。

同时附上现有Alpha Shape实现代码，询问是否存在API使用错误：

现有Alpha Shape实现代码 #

typedef CGAL::Exact_predicates_inexact_constructions_kernel EPIC;
typedef CGAL::Alpha_shape_vertex_base_2<EPIC> AlphaShapeVertexBase;
typedef CGAL::Alpha_shape_face_base_2<EPIC> AlphaShapeFaceBase;
typedef CGAL::Triangulation_data_structure_2<AlphaShapeVertexBase, AlphaShapeFaceBase> AlphaShapeTDS;
typedef CGAL::Delaunay_triangulation_2<EPIC, AlphaShapeTDS> AlphaShapeDelaunayTriangulation;
typedef CGAL::Alpha_shape_2<AlphaShapeDelaunayTriangulation, CGAL::Tag_false> Alpha_shape_2;
typedef EPIC::Point_2 Point_2;
            
std::vector<Point_2> points;
points.reserve(numPoints);
const size_t pointDimension = 3;
for (size_t pointIndex = 0; pointIndex < numPoints; ++pointIndex) {
    const size_t offset = pointIndex * pointDimension;
    const size_t xCoordinateIndex = offset;
    const size_t yCoordinateIndex = offset + 1;
    points.push_back(Point_2(pPoints[xCoordinateIndex], pPoints[yCoordinateIndex]));
}

const double maxTriangleEdgeLength = 50;
auto start = std::chrono::high_resolution_clock::now();
const Alpha_shape_2 alphaShape(points.begin(), points.end(), maxTriangleEdgeLength, Alpha_shape_2::REGULARIZED);
auto stop = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::minutes>(stop - start);

计算耗时 #

2D Alpha Shape calculation for 39651210 points took: 11 min.

并行化启用方案及代码修改 #

1. 前置编译条件 #

确保CGAL编译时开启线程支持，需在编译选项中添加：

• 编译定义：-DCGAL_ENABLE_THREADS=ON
• 链接选项：-lpthread（Linux/macOS）或对应Windows线程库

2. 各类计算的并行化实现 #

2D Delaunay三角剖分

替换原串行Delaunay类为并行版本CGAL::Parallel_delaunay_triangulation_2，自动利用多核处理点插入与三角剖分：

// 修改原Delaunay类型定义
typedef CGAL::Parallel_delaunay_triangulation_2<EPIC, AlphaShapeTDS> AlphaShapeDelaunayTriangulation;
// 其余类型定义保持不变

2D约束Delaunay三角剖分

使用CGAL::Parallel_constrained_Delaunay_triangulation_2，搭配标准约束三角剖分的顶点/面基类：

typedef CGAL::Exact_predicates_inexact_constructions_kernel EPIC;
typedef CGAL::Constrained_triangulation_vertex_base_2<EPIC> Vb;
typedef CGAL::Constrained_triangulation_face_base_2<EPIC> Fb;
typedef CGAL::Triangulation_data_structure_2<Vb, Fb> TDS;
typedef CGAL::Parallel_constrained_Delaunay_triangulation_2<EPIC, TDS> PCDT;

添加约束边时，并行版本会自动加速处理流程。

2D Alpha Shape

Alpha Shape依赖底层Delaunay三角剖分，只需将底层Delaunay替换为并行版本即可（参考上述2D Delaunay的修改方式），无需额外修改Alpha Shape的构造逻辑。

3. 现有代码的优化说明 #

你的现有代码无API使用错误，未利用并行化是耗时过长的核心原因。修改步骤：

1. 将AlphaShapeDelaunayTriangulation的类型定义替换为并行版本；
2. 编译时添加线程支持的编译定义与链接选项；
3. （可选）使用CGAL::remove_duplicates的并行版本预处理点数据，移除重复点以减少计算量。

额外性能优化建议 #

• 启用内存池：添加编译定义-DCGAL_MEMORY_POOL=ON，减少大数据量下的内存分配开销；
• 点数据预处理：确保输入点无重复、无冗余，避免无效计算；
• 内核选择：当前使用的EPIC核已适配大数据量场景，无需切换；若有高精度需求可考虑Exact_predicates_exact_constructions_kernel，但会牺牲部分性能。

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