Will the two lines intersect in a Cartesian plane

Question

I have this problem from the book 'Crack the Coding Interview'.

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

Here is the solution:

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;
    }
}

Why doesnt it have the simple solution that if the slopes are not same, then they will intersect. Why the epsilon and the y intercept.

In the Suggestions it says that

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

Answer 1

The “solution” is wrong.

Implicit in this “solution” is a notion that the arguments that have been passed are inaccurate, that, before intersect is called, the values have been subject to computations that may produce results with rounding errors. Because there are errors in the values, numbers that would be equal if calculated exactly are unequal. To recognize these as equal, this “solution” accepts as equal some values that are actually unequal.

One flaw in this reasoning is that the intersect routine has no knowledge of how large the errors may be and therefore has no basis for knowing what value of epsilon it should use. The ideal value might be zero, or it might be a million. The value that is used, 1e-5, has no basis in any engineering principle given the information provided. More than that, there is no basis for using an absolute error, as this code does. Depending on circumstances, the proper tolerance to use might be a relative error, an error denominated in ULPs, or some other technique. There is simply no reason to believe that this code will return true when passed arguments that ideally would represent intersecting lines but that have been calculated in some unknown way.

Another flaw is that the routine falsely accepts as equal values that are not equal. The routine will report as not intersecting many lines that do intersect. This code has not solved the problem of the routine returning the wrong answer; it has only changed the cases for which wrong answers are returned, and it may well have greatly increased the number of wrong answers.

Answer 2

First because the simple solution that if the slopes are not the same they will intersect is not complete. They could have the same slope and intercept and would therefore be identical.

The epsilon as the suggestion says is because the number representation in computers is not exact. According to the IEEE-standard a double has about 15 precise calculated digits therefore slope and intercept can have a rounding error due to previous calculations and therefore a simple check with == could yield that they are not identical while they just differ by a rounding error.

Answer 3

Why doesnt it have the simple solution that if the slopes are not same, then they will intersect. Why the epsilon and the y intercept.

The solution takes in consideration the approximation errors due to floating-point arithmetic. Because of floating point numbers doesn't represent all possible real numbers, but a relative small subset (more dense in [-1,+1] interval), it's common when you have to deal with floating points arithmetic use a threshold to perform equality checks.

The epsilon valure represent a threshold under which 2 different floating-point values would be considered equals.