geometry-predicates

是"自适应精度浮点数算术和快速鲁棒几何谓词"的安全 Rust 实现

此库提供了用于计算几何中广泛使用的有效精确几何谓词的 Rust 解决方案。

以下谓词在根级别公开

• orient2d
• incircle
• orient3d
• insphere

以及它们的近似（不精确）对应物

• orient2d_fast
• incircle_fast
• orient3d_fast
• insphere_fast

此外，这些谓词的构建块，即自适应精度浮点数算术原语也被公开，以便扩展到其他谓词或精确几何构造。

此库支持使用标准 IEEE 754 浮点数的 no-std 目标。

背景

这些谓词已经是在计算几何中多年的基本组成部分，并在工业界得到广泛使用。在几何算法的背景下，确定点相对于线（或平面）的方向以及点是否在圆（或球）内部常常是至关重要的。这些测试通常需要精确的原因是因为许多几何算法都会问一些问题（为了确定方向或在圆/球内）关于点配置，这些问题需要一致的答案。例如，如果 a、b 和 c 是二维平面上三个点，询问 b 相对于通过 a 和 c 的线的位置（左侧、右侧或重合）与询问 a 相对于通过 c 和 b 的线的位置是相同的。形式上，这个条件可以写成

sgn(orient2d(a,c,b)) == sgn(orient2d(c,b,a))

从数学上讲，像 orient2d 这样的谓词被定义为

                                        ⎛⎡ax ay 1⎤⎞
orient2d([ax,ay],[bx,by],[cx,cy]) := det⎜⎢bx by 1⎥⎟
                                        ⎝⎣cx cy 1⎦⎠

很容易看出，这些谓词解决了计算小矩阵行列式的问题，并且无论矩阵多么接近奇异，都可以得到正确的符号。

例如，为了计算矩阵 [a b; c d] 的行列式并得到正确的符号，我们可以调用

orient2d([a,b], [c,d], [0,0])

有关更多详细信息，请参阅 Jonathan Shewchuk 的原始网页，其中包含这些谓词。

注意事项

这些谓词不处理指数溢出 [1]，这意味着小于 1e-142 或大于 1e201 的浮点数输入可能不会产生准确的结果。这同样适用于 predicates.c 中的原始谓词以及其他对这些谓词的 Rust 端口和绑定。

参考文献

• [1] 自适应精度浮点算术和快速鲁棒几何谓词，离散与计算几何 18(3):305–363，1997年10月。
• [2] 鲁棒自适应浮点几何谓词，第十二届计算几何年会论文集（费城，宾夕法尼亚州），第141–150页，美国计算机协会，1996年5月。

致谢

这个端口最初是由一个名为 Corrode 的 C 到 Rust 转换器创建的。没有它，将这个库完整地转换为 Rust 将是一项艰巨的任务。在此，我特别感谢 Corrode 的作者提供了这样一个有用的工具。这个crate的0.2版本使用了 c2rust crate。同样的感激之情也献给 C2Rust 的开发者。