Как избежать ошибок округления при расчете площади треугольника?

Question

Как избежать ошибок округления при расчете площади треугольника?

Я пытаюсь вычислить площадь треугольника с вершинами

{{0,1000000000},{1,0},{0,-1000000000}}

Легко видеть, что площадь этого треугольника должна быть 1,000,000,000, но когда я пытаюсь вычислить площадь в Java, используя формулу Heron или формулу шнурка, я получаю 0 для этой площади.

Я уверен, что это связано с ошибкой округления при использовании double s, но я не уверен, как продолжить. Есть указания?

Программа:

private static double areaShoelace(int[][] v) {

    return 0.5 * Math.abs(v[0][0]*v[1][1] + v[1][0]*v[2][1] + v[2][0]*v[0][1] +

            v[1][0]*v[0][1] + v[2][0]*v[1][1] + v[0][0]*v[2][1]);

}



private static double areaHeron(double a, double b, double c) {

    double p = (a + b + c) / 2.0d;

    return Math.sqrt(p * (p - a) * (p - b) * (p - c));

}



private static double length(int[] a, int [] b) {

    return Math.hypot(a[0] - b[0], a[1] - b[1]);

}



public static void main(String[] args) {

    int[][] tri = new int[][]{{0,1000000000},{1,0},{0,-1000000000}};

    System.out.println(areaShoelace(tri));

    System.out.println(areaHeron(length(tri[0], tri[1]), length(tri[1],tri[2]), length(tri[0],tri[2])));

}

Вывод:

0.0

0.0

637 3

java floating-point precision area

3 ответов:

Comments

Ничего не найдено.

Simon Byrne · Accepted Answer · 2016-05-24 23:53:07

На самом деле здесь есть 2 различных ошибки.

В ваших реализациях формулы шнурка Некоторые знаки неверны (половина должна быть отрицательной). После того, как вы исправите это, вы должны получить правильный ответ в этом случае, однако вы должны заметить, что умножения и сложения выполняются с использованием целочисленной арифметики, которая имеет потенциал переполнения для больших чисел.

Если вы измените их на операции с плавающей запятой, это также может иметь смысл сгруппируйте их, чтобы уменьшить как количество операций, так и потенциал для деструктивного аннулирования, я бы предложил
0.5*Math.abs(v[0][0]*(v[1][1] - v[2][1]) + v[1][0]*(v[2][1] - v[0][1]) +
        v[2][0]*(v[0][1] - v[1][1]))
Численные задачи с формулой Херона хорошо установлены и объяснены самим мастером плавающей точки Уильямом Каханом: неверный расчет площади и углов игольчатого треугольника .
Однако в этом случае ваша проблема возникает еще раньше: результат Math.hypot(1, 1000000000) численно равен 1000000000 (остальные цифры теряются до округление с плавающей точкой), и, следовательно, при подаче в Формулу Херона (даже если вычисляется точно), даст 0.

Sneftel · Accepted Answer · 2016-05-24 19:50:13

Формула Херона не очень хорошо подходит для чрезвычайно острых или тупых треугольников, потому что по крайней мере один из членов p или (p-x) будет страдать от катастрофической отмены.
Более надежный подход заключается в вычислении высоты треугольника по отношению к самой длинной стороне, а затем использовать формулу A=0.5*b*h. Вычислите высоту, найдя положение на базе, ближайшей к третьей вершине, и измерив ее расстояние до этой вершины, а не с помощью обычного поперечного произведения (который сам пострадает от катастрофической отмены).

Nikem · Accepted Answer · 2016-05-24 21:05:09

Один из способов избежать ошибок округления в java-это использовать java.math.BigDecimal вместо примитивных двойников или поплавков.