两线段相交检测中的算法精度问题

Question

我写了一个测试平面上两条线段相交的代码。我不想把所有的细节都告诉你。你知道吗

代码采用两个线段，每个线段由两个端点描述，然后通过拟合a中的b和y = a*x + b将每个线段拟合到一条直线上。然后通过x = (b2 - b1) / (a2 - a1)找到两条直线的交点。最后，它测试相交点x是否包含在两条线段中。你知道吗

相关部分如下所示：

# line parameterization by a = Delta y / Delta x, b = y - a*x
a1 = (line1.edge2.y - line1.edge1.y) / (line1.edge2.x - line1.edge1.x)
b1 = line1.edge1.y - a1 * line1.edge1.x
a2 = (line2.edge2.y - line2.edge1.y) / (line2.edge2.x - line2.edge1.x)
b2 = line2.edge1.y - a2 * line2.edge1.x
# The intersection's x
x = - (b2 - b1) / (a2 - a1)
# If the intersection x is within the interval of each segment
# then there is an intersection
if (isininterval(x, line1.edge1.x, line1.edge2.x) and
    isininterval(x, line2.edge1.x, line2.edge2.x)):
    return True
else:
    return False

为了简洁起见，我放弃了很多处理特定情况的测试，比如边彼此平行（a1==a2）、它们在同一条线上、边的长度为0、边沿垂直轴（然后a变得无限大）等等

函数isininterval很简单

def isininterval(x0, x1, x2):
    """Tests if x0 is in the interval x1 to x2"""
    if x1 <= x0 <= x2 or x2 <= x0 <= x1:
        return True
    else:
        return False

现在的问题是：我发现由于舍入误差，当交点与线段边缘重合时，测试将给出错误的结果。你知道吗

例如，如果第1行介于（0,0）和（3,5）之间，第2行介于（3,5）和（7,1）之间，则得到的交点x是2.9999999999999996，这将给出错误答案。应该是3岁。你知道吗

你能提出一个解决办法吗？你知道吗

Answer 1

这是浮点运算的一个问题/特点。有很多方法可以将错误最小化，通过某些方法来排序指令，但最终，你会得到近似的答案，因为你可能用有限的位数来表示无限的数。你知道吗

您需要定义您构建的任何函数，使它们能够容忍这些错误。看看你的例子，“正确的”值和你得到的值之间的差别是1e-16——非常小。你知道吗

对于不等式，尤其是等式，放松精确/位匹配的约束是值得的。例如，如果您想测试x == 3，您可以将其编写为abs(x - 3) < EPSILON，其中EPSILON = 1e-6或EPSILON = 1e-9。基本上，你想要的和你拥有的之间的差别小于一个很小的值。同样，对于不等式，可以测试3 - EPSILON <= x或x <= 3 + EPSILON。你知道吗