java - 两条线会在笛卡尔平面相交吗

Question

我在“Crack the Coding Interview”一书中遇到了这个问题。

Given two lines on a Cartesian plane, determine whether the two lines would intersect.`

解决方法如下:

public class Line {

    static double epsilon = 0.000001;
    public double slope;
    public double yintercept;

    public Line(double s, double y) {
        slope = s;
        yintercept = y;
    }

    public boolean intersect(Line line2) {
        return Math.abs(slope - line2.slope) > epsilon ||
        Math.abs(yintercept - line2.yintercept) < epsilon;
    }
}

为什么没有简单的解决方案，如果坡度不同，那么它们就会相交。为什么 epsilon 和 y 截距。

在建议中它说

Don’t assume that the slope and y-intercept are integers. Understand limitations of floating point representations. Never check for equality with ==.

Answer 1

“解决方案”是错误的。

这个“解决方案”中隐含了一个概念，即传递的参数不准确，即在调用 intersect 之前，这些值已经过计算，可能会产生带有舍入误差的结果.因为值中存在错误，所以如果精确计算应该相等的数字是不相等的。为了认识到这些是相等的，这个“解决方案”接受了一些实际上不相等的值。

这个推理的一个缺陷是 intersect 例程不知道错误可能有多大，因此没有基础知道它应该是什么 epsilon 的值采用。理想值可能是零，也可能是一百万。鉴于所提供的信息，所使用的值 1e-5 在任何工程原理中都没有依据。不仅如此，没有像这段代码那样使用绝对误差的基础。根据具体情况，使用的适当容差可能是相对误差、以 ULP 命名的误差或其他一些技术。根本没有理由相信当传递理想情况下表示相交线但以某种未知方式计算的参数时，此代码将返回 true。

另一个缺陷是例程错误地将不相等的值接受为相等值。该例程将报告为不与许多相交的线相交。这段代码并没有解决例程返回错误答案的问题；它只是改变了返回错误答案的情况，很可能会大大增加错误答案的数量。