CGAL是构造3D Voronoi图唯一可靠方案，因其采用精确谓词避免浮点退化，并通过Delaunay对偶间接获取胞元；但需手动处理共面面片合并、半空间交、无限胞元截断及索引去重等细节。
用 CGAL 直接构造 3D Voronoi 图比手写更可靠
手动推导 3D Voronoi 胞元（即点集的垂直平分面围成的凸多面体）几乎不可行：每个胞元是若干半空间交集，需解平面方程、求面-面交线、裁剪多边形、判断顶点可见性……稍有误差就会导致面缺失或自相交。实际项目中，CGAL 是唯一被广泛验证的方案——它底层用精确几何谓词（Exact_predicates_inexact_constructions_kernel）避免浮点退化，且封装了 Delaunay_triangulation_3 与对偶的 Voronoi_diagram_3 接口。
关键点在于：CGAL 不直接输出“Voronoi 胞元多面体”，而是通过 Delaunay 三角剖分的对偶关系间接获取。每个输入点 p 对应的 Voronoi 胞元，由所有与 p 共享 Delaunay 边/面的邻点所定义的垂直平分面围成。
- 必须启用
CGAL::Exact_predicates_inexact_constructions_kernel，否则共面点、钝角四面体等常见情况会触发assertion failed: orientation != ZERO - 输入点集不能有重复点，否则
Delaunay_triangulation_3::insert()会静默失败或产生空胞元 - 若只需单个点的胞元（如模拟粒子领域），调用
voronoi_cell(p)比全量构造快一个数量级
voronoi_cell() 返回的是面片集合，不是封闭网格
CGAL 的 voronoi_cell()（在 Voronoi_diagram_3 中）返回一个 std::vector，元素是 Facet 类型，每个 Facet 包含一个 Plane_3 和所属的 Delaunay 有限面（Cell_handle）。这些面天然无序、不闭环，也**不保证共面面片已合并**——同一平面上可能拆成多个小三角形面片。
这意味着你拿到的不是 OBJ 可直接加载的 mesh，而是一组几何约束。要转成封闭多面体，得自己做三件事：
立即学习“C++免费学习笔记（深入）”；
- 按平面法向和原点距（
Plane_3::a(), b(), c(), d()）聚类共面面片，再用 CGAL 的Polygon_mesh_processing::join_collinear_edges()合并 - 用
CGAL::convex_hull_3()对所有面片顶点重算凸包——仅当胞元严格凸时成立；若输入点集非通用位置（如四点共球），胞元可能非凸，此时必须走半空间交（CGAL::Polyhedron_3+intersection_of_halfspaces_3()） - 注意：CGAL 的
Plane_3默认朝向是“指向胞元内部”，但不同版本实现略有差异，建议统一用plane.opposite()校验后取交
性能瓶颈常卡在半空间交，而非构造本身
对 n 个点做 3D Voronoi 构造，Delaunay 阶段复杂度是 O(n²) 平均、O(n⁴) 最坏；但真正拖慢的是后续把每个胞元转成显式多面体——单个胞元若有 k 个邻点，对应 k 个半空间，intersection_of_halfspaces_3() 在 k > 20 时耗时呈指数增长。实测 100 个随机点，平均胞元邻点数约 15，但最密点可达 42，该胞元计算耗时跳变到 2.3 秒（i7-11800H）。
- 预过滤：先用
dt.finite_facets()统计每个点的邻点数，对 k > 30 的点单独降采样（如移除距离最近的 2–3 个邻点再重算） - 避免重复计算：缓存
Cell_handle到面片集合的映射，不要每次调voronoi_cell()都重建 - 若只需体积或表面积，直接用 CGAL 内置的
cell_volume()和cell_surface_area()，它们绕过显式构造，快两个数量级
没有“标准格式”输出，.off 或 .ply 都得自己拼
CGAL 不提供 write_off() 这类函数。要导出可视化，必须手动提取顶点、面索引，并处理索引去重。常见错误是直接遍历 Facet 的三个顶点塞进 vector，结果同一个顶点被存几十次，.off 文件暴涨到百 MB。
正确做法是维护一个 std::map<:point_3 int></:point_3> 映射点坐标到唯一 ID（注意用 CGAL::compare_xyz() 比较，不用 ==），再为每个面生成三个 ID 构成的 std::vector<int></int>。导出时：
- 顶点列表按 ID 顺序写，确保 .off 头部的顶点数准确
- 面定义每行以
3开头，后跟三个顶点 ID（从 0 开始） - 若目标软件（如 MeshLab）报 “non-manifold edge”，大概率是共面面片未合并，或某平面法向反了导致面朝向混乱
最易被忽略的是无限胞元——边界点的 Voronoi 胞元延伸至无穷远，CGAL 用特殊顶点（Point_3(0,0,0) 加标志位）表示，导出前必须截断：选一个大球（如半径 1e6），用 CGAL::intersection(Point_3, Sphere_3) 把射线截成有限线段，再构面。
