CGAL过滤谓词无法返回精确结果的技术求助

CGAL Filtered_predicate 工作机制 #

CGAL的Filtered_predicate核心逻辑是**“快速近似优先，不确定时回退精确”**：

• 先使用性能更高的近似内核（如Exact_predicates_inexact_constructions_kernel）执行谓词计算；
• 同时计算近似结果的误差不确定区间，如果该区间不包含临界情况（比如定向判断中的COPLANAR，对应值为0），则直接返回近似结果；
• 只有当误差区间覆盖临界值，无法确定结果正确性时，才会调用精确内核（如Exact_predicates_exact_constructions_kernel）重新计算并返回精确结果。

为何未触发精确计算 #

你当前的代码存在两个关键问题：

1. 自定义谓词未实现误差分析逻辑：Filtered_predicate依赖近似内核下的误差区间判断来触发精确计算，但你的ClosestPlaneToPoint_1D模板类仅执行了近似计算，没有输出结果的不确定性范围，导致Filtered_predicate无法判断结果是否可靠，直接返回了近似值。
2. 浮点数误差的误判：你得到的平面方程结果-1.05501e-10是浮点数计算的误差产物，但近似内核的误差分析认为这个值的不确定区间不包含0，因此判定结果为NEGATIVE是可靠的，没有触发精确计算。

数据类型选择是否错误 #

你选择的Exact_predicates_inexact_constructions_kernel（近似）和Exact_predicates_exact_constructions_kernel（精确）组合本身是合理的：

• 近似内核用double做计算，性能高；
• 精确内核用有理数类型保证计算绝对准确，适合处理临界情况。
  问题并非数据类型选错，而是自定义谓词没有利用Filtered_predicate的误差检查机制。

是否需要调整EPSILON及调整方法 #

不推荐直接调整EPSILON，因为CGAL的过滤机制基于严格的误差分析而非固定阈值，强行修改可能引入其他问题。如果确实需要临时应急，可以通过编译宏调整：

• 在编译时添加参数：-DCGAL_DOUBLE_ROUNDING_MARGIN=1e-8
• 该宏会增大近似内核的误差容忍度，当计算结果的绝对值小于这个值时，会被判定为不确定，从而触发精确计算。

最优解决方案 #

方案1：使用CGAL内置的Filtered_kernel（推荐） #

直接使用CGAL预定义的Filtered_kernel，它已经内置了完整的过滤逻辑，无需手动实现Filtered_predicate：

// 定义过滤内核，自动处理近似/精确切换
typedef CGAL::Filtered_kernel<CGAL::Exact_predicates_exact_constructions_kernel> FilteredK;

// 用过滤内核实例化你的谓词
typedef ClosestPlaneToPoint_1D<FilteredK> CP_1D;

这样所有的CGAL谓词（如orientation、parallel、intersection）都会自动触发过滤，当近似计算不确定时自动切换到精确计算。

方案2：手动添加临界值检查 #

如果必须保留自定义Filtered_predicate，可以在近似内核的计算中手动判断临界情况，主动触发精确计算：
在ClosestPlaneToPoint_1D<InK>的operator()中，当计算出的平面方程值绝对值小于阈值时，手动调用精确内核重新计算orientation：

// 在近似内核的实现中添加检查
Plane_3 back_plane2(back_plane_p1, back_plane_p2, back_plane_p3);
double plane_val = back_plane2.a() * candidate_point->x() + back_plane2.b() * candidate_point->y() + back_plane2.c() * candidate_point->z() + back_plane2.d();
CGAL::Sign sign = CGAL::orientation(back_plane_p1, back_plane_p2, back_plane_p3, *candidate_point);

// 当值接近0时，手动用精确内核重新计算
if (std::fabs(plane_val) < 1e-8) {
    // 转换点到精确内核类型
    ClosestPlaneToPoint_1D<ExK> exact_pred;
    // 这里需要把所有输入点转换为ExK的Point_3类型
    // 调用精确内核的计算，重新获取sign
    // ...（省略类型转换代码）
    sign = exact_pred(/*转换后的参数*/);
}

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