测试两个线段的交叉时算术精度问题

Question

我为平面中两个线段的交叉编写了一个代码测试.我不会打扰你的所有细节.

代码采用两个线段,每个线段由两个端点描述,然后通过拟合a和bin 将每个线段拟合到一条线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

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

例如,对于(0,0)和(3,5)之间的line1和(3,5)和(7,1)之间的line2,得到的交点x是2.9999999999999996,这给出了错误的答案.应该是3.

你能建议一个解决方案吗？

Answer 1

这是浮点运算的问题/特征.有一些方法可以通过某些方式排序指令来最小化错误,但最终,您将获得近似答案,因为您可能使用有限位数表示可能无限的数字.

您需要定义您构建的任何函数,使它们能够容忍这些错误.看看你的例子,"正确"值和你得到的值之间的差异是订单1e-16- 极其极低.

由于不平等,尤其是平等,放松精确/双向匹配的约束是值得的.例如,如果你想测试它x == 3,你可以将其写为abs(x - 3) < EPSILON,where EPSILON = 1e-6或EPSILON = 1e-9.基本上,您想要拥有的和您拥有的之间的差异小于非常小的值.同样,对于不平等,你可以测试那个3 - EPSILON <= x或x <= 3 + EPSILON.