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

Have you looked at this question: "What is the inclusive range of float and double in Java?" It might shed some light on your problem. http://stackoverflow.com/questions/1650505/what-is-the-inclusive-range-of-float-and-double-in-java — Alos, May 24 '16 at 16:24
Your `areaShoelace()` still gives 0 even with smaller numbers. — Daniel Widdis, May 24 '16 at 16:27

score 2 · Answer 1 · answered May 24 '16 at 16:50

Heron's formula is not a good match for extremely acute or obtuse triangles, because at least one of the p or (p-x) terms will suffer from catastrophic cancellation.

A more robust approach is to calculate the altitude of the triangle with respect to the longest side, then use the formula A=0.5*b*h. Calculate the altitude by finding the position on the base closest to the third vertex and measuring its distance to that vertex, rather than with the conventional cross product (which itself would suffer from catastrophic cancellation).

Simon Byrne · Accepted Answer · 2016-05-24T20:53:07.807

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.

@Sneftel has an informative answer as well but your answer points out the defects in the code. Good eye! — jimpudar, May 25 '16 at 00:46

score 1 · Answer 3 · answered May 24 '16 at 18:05

1

One way to avoid rounding errors in java is to use java.math.BigDecimal instead of primitive doubles or floats.

answered May 24 '16 at 18:05

Nikem

5,716
3
32
59

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

3 Answers3