精确几何计算

形式陈述 ​

在浮点数系统公理库浮点数系统与 IEEE 754Floating-point system · IEEE 754以有限尾数和指数表示机器数，并说明 IEEE 754 的特殊值、格式与运算语义。中实现几何算法时，有限个谓词的符号常决定组合结构，例如

$$\mathrm{orient}(a,b,c)\in \{-1,0,+1\},\mathrm{incircle}(a,b,c,d)\in \{-1,0,+1\}.$$

精确几何计算原则要求：只要输入坐标被模型精确表示，算法用于分支的谓词符号必须与相应实数或整数表达式的数学符号一致。构造出的交点、距离或坐标可以近似，但任何会改变拓扑或组合结构的分支不得由未经误差控制的浮点近似决定。

一种常见过滤框架是：

1. 用普通浮点快速计算近似值 $\hat{p}$；
2. 同时计算可靠误差界 $E$；
3. 若 $|\hat{p}|>E$，直接返回其符号；
4. 否则提升精度、使用扩展展开或精确整数/有理算术，直到符号确定。

该接口返回的是符号证书，而不是“看起来足够精确”的数值。

直觉 ​

几何算法的坐标误差通常是连续的，但组合错误是离散的。一个接近零的方向行列式若被判错，可能把左转当成右转，造成边相交、面方向颠倒、搜索循环或不合法三角剖分。提高固定浮点位数只能推迟失败，不能覆盖任意接近退化的输入。

过滤器把常见易判输入留给硬件浮点，把真正困难的近退化输入送到高精度后端，因此可以同时获得通常速度与最坏正确性。

例子与边界 ​

三点坐标规模很大而几乎共线时，方向行列式由两个大乘积相减得到很小结果。双精度可能把正值舍入成零或负值；仅比较 abs(det) < 1e-9 也没有尺度不变性。可靠过滤界必须由每次算术误差传播得到。

Delaunay 构造中的四点近共圆情况同样敏感。若相邻三角形对同一边给出不一致的 in-circle 符号，edge flip 过程可能来回振荡。自适应精确谓词可保证双方共享同一数学判定。

精确谓词不自动解决输入建模问题。十进制测量值读入二进制浮点后，算法精确回答的是这些二进制数所定义的几何，而非不可知的真实物理坐标。共线、共圆等退化还需要一致的 tie-breaking、symbolic perturbation 或多值输出策略。

推论与应用 ​

方向判定公理库方向判定Orientation test用二维或高维行列式符号判断点组转向或仿射定向的基本谓词。、内接圆判定公理库内接圆判定In-circle test · Incircle predicate · In-sphere predicate in 2D用带方向的行列式判定一点位于三点外接圆内、圆上还是圆外。、线段相交、凸包和点定位都可采用同一过滤接口。算法证明可假设谓词返回数学正确符号，数值实现则独立负责兑现该合同。

精确构造与精确判定应分层。许多算法只需精确决定组合结构，最终展示坐标可用受控近似；若输出本身将继续参与后续谓词，则还必须采用能保持代数一致性的构造表示。

参考资料

• Christoph M. Hoffmann, Geometric and Solid Modeling, Morgan Kaufmann, 1989, Chapter 4.
• Jonathan Richard Shewchuk, “Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates,” Discrete & Computational Geometry 18, 1997.
• Kurt Mehlhorn and Stefan Näher, “LEDA: A Platform for Combinatorial and Geometric Computing,” Communications of the ACM 38(1), 1995.