How can I avoid rounding errors in this triangle area calculation?

Question

I am trying to calculate the area of a triangle with vertices

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

It is easy to see that the area of this triangle should be 1,000,000,000, but when I try to calculate the area in Java using either Heron's formula or the Shoelace formula, I get 0 for the area.

I am pretty sure this is due to a rounding error while using doubles but I am not sure how to proceed. Any pointers?

Program:

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

Output:

0.0
0.0

Answer 1

There are actually 2 different errors here.

In your shoelace formula implementations, some of the signs are incorrect (half should be negative). Once you fix that, you should get the correct answer in this case, however you should note that the multiplications and additions are being performed using integer arithmetic, which have the potential to overflow for large numbers.

If you change these to floating point operations, it might also make sense to group them to reduce both the number of operations, and the potential for destructive cancellation, I would suggest

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

The numerical problems with Heron's formula are well-established and explained by the master of floating point himself, William Kahan: Miscalculating Area and Angles of a Needle-like Triangle.

However in this case your problem occurs even before this: the result of Math.hypot(1, 1000000000) is numerically equal to 1000000000 (the remaining digits are lost to floating point rounding), and hence when fed in to Heron's formula (even if computed exactly), will give 0.