如何用CGAL验证d维单纯形集合是否为有效三角剖分（d>3）

核心验证逻辑 #

有效三角剖分必须满足两个关键条件：

1. 所有单纯形的并集完全覆盖顶点集的凸包
2. 任意两个单纯形的交集要么是空集，要么是它们的公共面（维度严格小于d）

具体实现步骤 #

1. 定义基础数据结构 #

根据目标维度d选择CGAL内核，优先推荐精确构造内核（适合严格验证场景），若对速度要求更高可改用浮点内核CGAL::Epick_d：

#include <CGAL/Exact_predicates_exact_constructions_kernel_d.h>
#include <vector>
#include <algorithm>

const int d = 4; // 替换为你的实际维度
using Kernel = CGAL::Exact_predicates_exact_constructions_kernel_d<d>;
using Point_d = typename Kernel::Point_d;
using Simplex_d = std::vector<Point_d>; // 每个d维单纯形由d+1个顶点定义

2. 计算顶点集的凸包 #

先收集所有单纯形的顶点并去重，再用CGAL的凸包模块计算凸包：

// 收集所有顶点并去重
std::vector<Point_d> all_vertices;
for (const auto& simplex : your_simplex_set) {
    all_vertices.insert(all_vertices.end(), simplex.begin(), simplex.end());
}
std::sort(all_vertices.begin(), all_vertices.end());
all_vertices.erase(std::unique(all_vertices.begin(), all_vertices.end()), all_vertices.end());

// 构建凸包
CGAL::Convex_hull_d<Kernel> convex_hull(all_vertices.begin(), all_vertices.end());

3. 验证并集覆盖凸包 #

采用随机采样验证（兼顾效率与可靠性）：在凸包内部生成大量随机点，检查每个点是否属于至少一个单纯形：

Kernel::Contained_in_simplex_d is_inside_simplex;
bool is_covered = true;

// 生成1000个凸包内的随机采样点（可根据维度调整数量）
for (int i = 0; i < 1000; ++i) {
    // 通过凸包顶点的凸组合生成内部点
    std::vector<typename Kernel::FT> weights(d+1);
    typename Kernel::FT sum = 0;
    for (auto& w : weights) {
        w = CGAL::random_double();
        sum += w;
    }
    for (auto& w : weights) {
        w /= sum;
    }

    Point_d sample = convex_hull.point(0) * weights[0];
    for (int j = 1; j < d+1; ++j) {
        sample = sample + convex_hull.point(j) * weights[j];
    }

    // 检查采样点是否在任意单纯形内（包含边界）
    bool point_found = false;
    for (const auto& simplex : your_simplex_set) {
        if (is_inside_simplex(simplex.begin(), simplex.end(), sample) != CGAL::ON_UNBOUNDED_SIDE) {
            point_found = true;
            break;
        }
    }
    if (!point_found) {
        is_covered = false;
        break;
    }
}

4. 验证单纯形交集规则 #

遍历所有单纯形对，检查它们的交集维度是否合规：

Kernel::Intersect_simplex_d check_intersection;
bool valid_intersections = true;

for (size_t i = 0; i < your_simplex_set.size() && valid_intersections; ++i) {
    for (size_t j = i+1; j < your_simplex_set.size(); ++j) {
        const auto& s1 = your_simplex_set[i];
        const auto& s2 = your_simplex_set[j];

        // 获取交集的维度：-1表示空集，≥0表示对应维度的公共面
        int intersect_dim = check_intersection(s1.begin(), s1.end(), s2.begin(), s2.end());
        if (intersect_dim >= d) { // 交集维度等于d说明两个单纯形重叠，不符合要求
            valid_intersections = false;
            break;
        }
    }
}

5. 额外验证：所有单纯形都在凸包内 #

确保每个单纯形的顶点都在凸包上，且单纯形整体包含在凸包内：

Kernel::Contained_in_convex_hull_d is_in_hull(convex_hull);
bool all_simplices_valid = true;

for (const auto& simplex : your_simplex_set) {
    for (const auto& p : simplex) {
        if (is_in_hull(p) == CGAL::ON_UNBOUNDED_SIDE) {
            all_simplices_valid = false;
            break;
        }
    }
    if (!all_simplices_valid) break;
}

最终判断 #

当is_covered、valid_intersections和all_simplices_valid均为true时，该单纯形集合是顶点凸包的有效三角剖分。

注意事项：

• 维度越高，采样点数量需适当增加以提升覆盖验证的可靠性；
• 若使用浮点内核，需注意精度误差可能导致的判断偏差；
• 去重顶点时，依赖CGAL点的默认比较算子确保正确性。

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