CODEWITHSUNDEEP
javamathfloating-point
Kraken
Kraken

Reputation: 24233

Will the two lines intersect in a Cartesian plane

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 ==.

Upvotes: 7

Views: 1537

Answers (4)

Eric Postpischil
Eric Postpischil

Reputation: 223693

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.

Upvotes: 9

GarethL
GarethL

Reputation: 1493

Underneath it all, numbers are all converted to binary when they are processed. It is not possible to represent most floating point numbers as an exact binary (because they would be an infinite series of 1s and 0s), and so approximations are made, by truncating the binary sequence. For example, the floating point number 0.1 (ie: one tenth) is not representable as an exact binary number, rather, it is represented by an approximation which looks like 0.000110011... Truncation of this binary number causes potential rounding errors, and so the exact equality "==" could cause a false response, when in fact it is this rounding error which is giving the fake negative. Introducing an epsilon attempts to avoid these errors by saying "anything below this number we consider to be zero". See the "fractions in binary" section of wikipedia to read more.

Upvotes: 1

Trudbert
Trudbert

Reputation: 3198

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.

Upvotes: 5

Heisenbug
Heisenbug

Reputation: 39194

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.

Upvotes: 4

Related Questions