python - 测试两条线段相交时的算术准确性问题

Question

我写了一个代码测试平面中两条线段的交点。我不会用所有的细节来打扰你。

代码采用两条线段，每条线段由两个端点描述，然后通过在 y 中拟合 a 和 b 将每个线段拟合成一条线= 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

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

例如，line1 在 (0,0) 和 (3,5) 之间，line2 在 (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 .