如何避免在计算三角形面积时产生舍入误差？

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

- jimpudar

---

你看过这个问题吗："Java中的float和double的包容范围是什么？" 它可能会为你的问题提供一些线索。 https://dev59.com/QnI-5IYBdhLWcg3w1sTi - Alos

你的 areaShoelace() 即使使用更小的数字仍然返回 0。 - Daniel Widdis

Answer 1

Heron公式不适用于极锐角或极钝角的三角形，因为至少有一个 p 或 (p-x) 项会受到灾难性的取消影响。

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

- Sneftel

Answer 2

这里实际上有两个不同的错误。

在您的 鞋带公式 实现中，一些符号是不正确的（一半应该是负数）。一旦您修复了这个问题，在这种情况下您应该会得到正确的答案，但是请注意，乘法和加法是使用整数算术执行的，对于大数字有可能会溢出。

如果您将它们更改为浮点操作，也许将它们分组以减少操作数量和破坏性抵消的潜力也是有意义的，我建议这样做。

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。

- Simon Byrne

---

@Sneftel的回答也很有信息量，但是你的回答指出了代码中的缺陷。眼力真好！ - jimpudar

Answer 3

避免在Java中出现舍入误差的一种方法是使用 java.math.BigDecimal，而不是原始的double或float。

- Nikem