java - Java 中的精确几何

Question

我正在用 Java 编写一个需要大量几何图形的应用程序。我大量使用了现有的类，并且到目前为止我的计算都是 double 的(因此我使用例如 Point2D.Double、Line2D.Double 并使用后者编码了凸多边形类...)。

我遇到了与 double 计算相关的几个问题，这些问题使我的应用程序有时不稳定，我考虑切换到 BigDecimal，但这意味着使用 BigDecimal 等创建我自己的 Point2D、Line2D 类，并重写几个函数。另一种解决方案是接受不精确性并加以处理。即，点实际上是一个小正方形，一条线是一个无限带，如果正方形和带相交，则点位于线上，等等。虽然这个解决方案可以快速实现，但我的代码会被像 (Math.abs(x) < precision) (表示 x == 0)这样分散的语句破坏。

有人知道在 Java 中进行精确几何图形的好干净的方法吗？

Answer 1

_{我试图将其(部分)压缩到评论中，但它不适合。您不应该将其视为“THE”答案，但我想在此列出一些要点。}

每当有人提到 BigDecimal 或 float 的精度问题时，使用 double 的建议就很常见，令人恼火，但在这种情况下同样不合适。除了极少数情况外，在所有情况下，double 的有限精度根本不相关。

^{除非，也许您正在编写应该计算即将发送到火星的载人航天器的轨迹的软件，或者进行其他高度科学的计算。}

此外，用 double 替换 BigDecimal 往往只会用几个大问题替换一个小问题。例如，您必须考虑 RoundingMode 和“scale”，这可能很棘手。最终，您会注意到像 1.0/3.0 这样的简单值也不能用 BigDecimal 表示。

对于您的特定应用案例，还有更多注意事项:

即使使用基于 BigDecimal 的 Point2D 实现，数据仍然会通过 double/getX() 方法公开为 getY() 。例如，像 Line2D#ptLineDistSq 这样的方法仍将使用 double 值。只有当您从头开始编写与计算相关的所有内容，真正到处使用BigDecimal时，才能避免这种情况。

但即使你这样做了:你也无法计算从点 (-1,0) 到点 (2,1) 的直线的斜率，也无法说出这条直线与 y 轴相交的位置。您可以在这里尝试一些有理数表示，但是单位正方形的对角线长度仍然存在这个问题 - 这是一个无理数。

double 的不精确性很烦人。您可以计算一个点是在线的左侧还是在线的右侧。由于精度问题，很可能两者都是。使用“数学上”应该相等但因一些小的浮点误差而不同的点进行计算可能会导致虚假结果(我也在 one of my libraries 中偶然发现了这一点)。

正如您在问题中已经提到的:一些在纯数学中起作用的概念在以有限的精度实现时必须重新考虑。任何 == 比较都是不允许的，其他比较应该仔细验证，考虑到可能的舍入误差。

但是使用一些基于“epsilon”的比较是处理这个问题的常用方法。当然，它们使代码变得更加笨拙。但将其与 BigDecimal 的一些“任意精度”代码进行比较:

BigDecimal computeArea(BigDecimal radius) {
    // Let's be very precise here....
    BigDecimal pi = new BigDecimal("3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118548074462379962749567351885752724891227938183011949129833673362440656643086021394946395224737190702179860943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901224953430146549585371050792279689258923542019956112129021960864034418159813629774771309960518707211349999998372978049951059731732816096318595024459455346908302642522308253344685035261931188171010003137838752886587533208381420617177669147303598253490428755468731159562863882353787593751957781857780532171226806613001927876611195909216420198938095257201065485863278865936153381827968230301952035301852968995773622599413891249721775283479131515574857242454150695950829533116861727855889075098381754637464939319");
    BigDecimal radiusSquared = radius.multiply(radius);
    BigDecimal area = radiusSquared.multiply(pi);
    return area;
}

对比。

double computeArea(double radius) {
    return Math.PI * radius * radius;
}

此外，基于 epsilon 的比较仍然容易出错并引发一些问题。最突出的是:这个“epsilon”应该有多大？基于 epsilon 的比较应该在哪里进行？然而，现有的实现，比如 http://www.geometrictools.com/ 中的几何算法，可能会给出一些如何做到这一点的想法(尽管它们是用 C++ 实现的，并且在最新版本中可读性稍差)。它们经过了时间的考验，并且已经展示了如何应对许多与精度相关的问题。