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

Question

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

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

很容易看出这个三角形的面积应该是 1,000,000,000，但是当我尝试使用 Heron 公式或 Shoelace 公式计算 Java 中的面积时，我得到的面积为 0。

我很确定这是由于使用 doubles 时的舍入错误造成的，但我不确定如何继续。有什么指点吗？

节目：

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

Heron 公式不适用于极锐角或钝角三角形，因为 p 或 (p-x) 项中至少有一项会遭受灾难性抵消。

更稳健的方法是计算三角形相对于最长边的高度，然后使用公式A=0.5*b*h。通过找到距离第三个顶点最近的底部位置并测量它到该顶点的距离来计算高度，而不是使用传统的叉积（它本身会遭受灾难性的抵消）。

Answer 2

避免 java 中舍入错误的一种方法是使用 java.math.BigDecimal 而不是原始双精度数或浮点数。

Answer 3

这里实际上有 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.

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

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

java

floating-point

precision

area