c# - 试图检查一个点是否在线的误差范围

Question

通过比较应该相同的数量，使用浮点值就像呼吸一样容易在近似误差上运行。我想知道在某些 MSDN(甚至外部)库中是否有一种方法可以让 C# 忽略该问题。

一个例子可能是:不仅仅是像这样比较 2 个浮点值

if(myVector3.X == anotherVector3.X)

我会很感激这样的

if(myVector3.X.isInTheNeighbourhood(anotherVector3.X))

这个写得不好，我知道。那只是为了简化解释。我正在做的是检查一个点( Vector3 )是否位于线段上。所以基本上我做的计算无非就是

(x - x1)/(x2 - x1) = (y - y1)/(y2 - y1) = (z - z1)/(z2 - z1)

但是这些值并不总是相同的，所以我需要写下一些代码，其中包括一种容差，一种邻域数学概念，以接受接近线的值。

希望我说清楚了。
有没有人解决这个问题？

Answer 1

我建议使用精确谓词。这是您实际询问的另一种方法，但可能值得考虑。

假设您的三个点确实位于它们各自的 double 坐标所指示的位置。像您的问题中建议的那样简单的 double 计算可能仍会返回错误的结果。但是，有一些技术可以获得准确的结果来检测这些情况。一种技术是将所有数字转换为任意精度的浮点数(或整数)，并在后台使用整数进行大部分计算。另一个应该在现代硬件上运行得更快，将中间结果表示为 double 数之和。例如。计算时a+b ，你得到两个结果数字，第一个是你通常计算的总和，另一个是记下错误的修正项。在很多情况下，较大的项足以做出选择，这就引出了自适应精度的概念。

Jonathan Richard Shewchuk 在他的页面 Adaptive Precision Floating-Point Arithmetic and Fast Robust Predicates for Computational Geometry 中很好地概述了所有这些，包括几何谓词的应用。 .他有a paper on it , 和 some C code这应该可以适应C#。或者也许用 C 编译并链接到 C#，从而形成一个混合语言项目。但是请注意，它对编译器如何处理浮点计算做出了一些假设。特别是，您必须小心某些中间结果没有过高的精度，例如 the 80-bit numbers存储在 80387-style floating point unit .我有 looked into this myself recently ，最简单的解决方案可能是要求编译器使用 SSE指令而不是 x87那些。

在您的情况下，您是在询问点 p 是否位于连接 p1 和 p2 的线段上。一个非常符合该论文精神的谓词是第四个点相对于由其他三个跨越的平面的位置:它在该平面的上方、下方或内部，以及orient3d。谓词可以告诉你哪个。因此，一种可能的方法是在一般位置上取四个任意点 q1 到 q4，即不是全部在一个平面上，也不是三个在一条线上。然后你可以检查 p,p1,p2,qi 对于所有 i ∈ {1,2,3,4} 是否共面(符号为零)。如果是，那么 p 至少位于 p1 和 p2 跨越的线上。接下来，您可以检查不同 i,j 的 p,p1,qi,qj 的方向，直到找到一个非零符号，然后您可以查看 p,p2,qi,qj 是否具有不同的符号。如果是这样，那么 p 确实在 p1 和 p2 之间，因此在同一行。如果你发现没有 i,j 使得 p,p1,qi,qj 不为零，那么 p=p1。同样，如果你找到一个非零符号，但 p,p2,qi,qj 的对应符号为零，则 p=p2。是否要包括线段的端点取决于您。本段可能不是最优雅的方法，但它利用了现有的 orient3d实现，因此它可能比从头开始编写新谓词更容易使用。

请注意，在大多数情况下，由于点坐标本身的舍入，点不会完全位于线段上。以上只会帮助您可靠地检测到那些罕见的情况，以便您可以处理它们。它还可能允许您对其他谓词做出一致的选择。在 CGAL 的世界里，这种方法将被称为“exact predicates, inexact constructions ”，因为谓词可以可靠地计算，但它们所操作的几何对象仍需近似。如果您确实需要可靠地位于线段上的点，而不仅仅是靠近，那么使用某些精确数字类型的精确构造方法将是更可取的。或者您采用其他答案建议的方法。