Будут ли две линии пересекаться в декартовой плоскости

Question

У меня есть эта проблема из книги «Crack the Coding Interview».

Учитывая две линии на декартовой плоскости, определить, будут ли эти две линии 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; 
    } 
} 

Почему оленья кожа это есть простое решение, если склоны не одинаковы, то они пересекаются. Почему эпсилон и y перехватывают.

В Suggestions он говорит, что

Не думайте, что наклон и у-перехватывать целые числа. Понять ограничения в представлениях с плавающей запятой. Никогда не проверяйте равенство с ==.

Answer 1

«Решение» неверно.

Неявное в этом «решении» является понятием, что переданные аргументы неточны, что до того, как вызывается intersect, значения были подвергнуты вычислениям, которые могут приводить к результатам с ошибками округления. Поскольку в значениях есть ошибки, числа, которые были бы равны, если бы они были точно рассчитаны, были неравными. Чтобы признать их равными, это «решение» принимает как равные некоторые значения, которые на самом деле неравны.

Один из недостатков в этом рассуждении состоит в том, что рутина intersect не знает, насколько велики ошибки и поэтому не имеет оснований знать, какое значение должно быть epsilon. Идеальное значение может быть нулевым, или это может быть миллион. Значение, которое используется, 1е-5, ​​не имеет оснований ни в каком инженерном принципе, учитывая предоставленную информацию. Более того, нет оснований для использования абсолютной ошибки, как это делает этот код. В зависимости от обстоятельств, правильная допуск к использованию может представлять собой относительную ошибку, ошибку, выраженную в ULP, или какой-либо другой метод. Просто нет оснований полагать, что этот код вернет true при передаче аргументов, которые идеально представляли бы пересекающиеся линии, но которые были вычислены каким-то неизвестным способом.

Другой недостаток заключается в том, что процедура ложно принимает равные значения, которые не равны. Подпрограмма будет сообщать, что она не пересекает многие строки, которые пересекаются. Этот код не решил проблему рутины, возвращающей неправильный ответ; он только изменил случаи, когда возвращаются неправильные ответы, и, возможно, он значительно увеличил количество неправильных ответов.

Answer 2

Почему оленья кожа это есть простое решение, если склоны не совпадают, то они будут пересекаться. Почему эпсилон и y перехватывают.

Решение принимает во внимание ошибки аппроксимации из-за арифметики floating-point. Поскольку числа с плавающей точкой не представляют все возможные действительные числа, но относительное небольшое подмножество (более плотное в интервале [-1, + 1]), обычно, когда вам приходится иметь дело с арифметикой с плавающей запятой, используйте пороговое значение для выполнения проверки равенства.

Эпсилон-вал представляет собой пороговое значение, при котором считаются равными 2 различных значения с плавающей запятой.

Answer 3

Во-первых, потому что простое решение, что, если наклоны не совпадают, они пересекаются не полностью. Они могли иметь одинаковый наклон и перехват и поэтому были бы одинаковыми.

Эпсилон, как говорится в предположении, состоит в том, что числовое представление в компьютерах не является точным. Согласно IEEE-standard у двойника имеется около 15 точных вычисленных цифр, поэтому наклон и перехват могут иметь ошибку округления из-за предыдущих вычислений, и поэтому простая проверка с помощью == может привести к тому, что они не идентичны, в то время как они просто отличаются погрешностью округления.

Answer 4

Под всем этим номера преобразуются в двоичные коды при их обработке. Невозможно представить большинство чисел с плавающей запятой как точный двоичный код (потому что они будут бесконечной серией из 1s и 0s), и поэтому приближаются, путем усечения двоичной последовательности. Например, число с плавающей запятой 0,1 (т. Е. Одна десятая) не представляется в виде точного двоичного числа, скорее оно представлено приближением, которое выглядит как 0,000110011 ... Усечение этого двоичного числа вызывает потенциальные ошибки округления, и поэтому точное равенство «==» может вызвать ложный ответ, когда на самом деле это ошибка округления, которая дает фальшивый негатив. Представляя epsilon пытается избежать этих ошибок, говоря «что-нибудь ниже этого числа, мы считаем равным нулю». См. Раздел «фракции в двоичном формате» wikipedia, чтобы узнать больше.