java - 如何避免此三角形面积计算中的舍入误差？

Question

我正在尝试计算带顶点的三角形的面积

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

很容易看出这个三角形的面积应该是 1,000,000,000，但是当我尝试使用 Heron 公式或 Shoelace 公式在 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]))

Heron 公式的数值问题由浮点大师 William Kahan 本人确立和解释:Miscalculating Area and Angles of a Needle-like Triangle .

然而，在这种情况下，您的问题甚至在此之前就出现了:Math.hypot(1, 1000000000) 的结果在数值上等于 1000000000(其余数字因浮点舍入而丢失)，并且因此，当输入 Heron 公式(即使计算准确)时，将给出 0。