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

Question

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

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

Нетрудно видеть, что площадь этого треугольника должна быть 1000000000, но когда я пытаюсь вычислить площадь в Java с использованием либо формулы Герона или формулу Шойла, я получаю 0 для области.

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

Программа:

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 

Answer 1

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

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

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

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])) 

Численные проблемы с Формула Херона хорошо установлена ​​и объяснена самим мастером с плавающей точкой, Уильямом Каханом: Miscalculating Area and Angles of a Needle-like Triangle.

Однако в этом случае ваша проблема возникает еще до этого: результат Math.hypot(1, 1000000000) численно равен 1000000000 (оставшиеся цифры теряются при округлении с плавающей запятой), и, следовательно, при подаче в формулу Херона (даже если она вычисляется точно) , даст 0.

Answer 2

формула Герона не хороший матч для чрезвычайно острых или тупых треугольников, потому что по крайней мере один из p или (p-x) условиях будет страдать от катастрофической отмена.

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

Answer 3

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