计算几何中检验双精度数相等性的一般策略

Question

所以这对我来说似乎是一个反复出现的问题-我正试图在de Berg等人的计算几何中实现线段相交和双连接边列表覆盖算法。现在，我正在使用以下函数来测试两个值的相等性：

private static final double absTol = 1e-14;
private static final double relTol = 1e-10;        
public static final boolean areClose(double i, double j) {
    return (Math.abs(i-j) <= absTol) || 
           (Math.abs(i-j) <= relTol*Math.max(Math.abs(i), Math.abs(j)));
}

我遇到的主要问题是我偶尔会遇到一个bug。例如，今天我意识到我的一个函数失败了，因为我最初将absTol设置为1e-16，而上面的函数在我的某个函数本应确定0.0和1.535e-15相等时失败了。我通过将absTol调整为1e-14来解决这个问题。所以我的问题是，有没有比磨练公差更好的方法来解决这个问题？或者，你应该修改算法，让它们只是输出错误的值，而不是崩溃吗？不确定如何从这里开始。

我注意到的一点是，在这里概述的线段相交算法中，计算交点需要两个单独的函数。基本上，第一次计算与交叉点相关的事件点时，计算两个线段的交叉点；我使用以下算法：

public static Point2D findIntersection(Line2D line1, Line2D line2) {
    double s1X = line1.getX2()-line1.getX1();     
    double s1Y = line1.getY2()-line1.getY1();
    double s2X = line2.getX2()-line2.getX1();     
    double s2Y = line2.getY2()-line2.getY1();
    double s = (-s1Y*(line1.getX1()-line2.getX1())+s1X*(line1.getY1()-line2.getY1()))/(-s2X*s1Y+s1X*s2Y);
    double t = ( s2X*(line1.getY1()-line2.getY1())-s2Y*(line1.getX1()-line2.getX1()))/(-s2X*s1Y+s1X*s2Y);
    if (s >= 0 && s <= 1 && t >= 0 && t <= 1) {
        return new Point2D.Double(line1.getX1()+(t*s1X), line1.getY1()+(t*s1Y));
    } else {
        return null; 
    }
}

但是，在确定状态中行的相等性时，我一直在使用：

private double getIntercept(Line2D line) {
    if (MathUtilities.areClose(line.getY1(), line.getY2())) {
        // line is horizontal. Set intersection to x value
        return this.x;
    } else {
        return line.getX1() + (line.getX2()-line.getX1())*((this.y-line.getY1())/(line.getY2()-line.getY1()));
    }   
}

测试线与事件线的相交位置（当两条或多条线具有相同的截距时，它们在相同的位置与事件线相交）。所以本质上，两种不同的算法被用来寻找交点，这意味着我得到的值略有不同。最后，我也意识到areClose中使用的等式测试不一定是传递的，所以这也会引起一些问题。

Answer 1

处理计算几何中的"精确性"是一个比你想象的更经常出现的问题。除了不动点算法（已经提出）之外，另一种方法是使用自适应精度算法——以比两倍精度更好的精度评估运算，但只有在必要时才能保持正确性。

实现自适应精度运算在很大程度上是一项不平凡的任务，但有一些库是可用的，即Shewchuck的鲁棒谓词和/或CGAL几何库使用的MPFR库。

可以通过对Shewchuk的orientation例程的几次调用来可靠地检测两条线之间的交叉点。

Answer 2

您有一个重要的问题，即存储坐标的精度（可能）高于对您有意义的精度。也就是说，如果两个值在相差小于absTol时总是被认为相等，那么存储或使用不是absTol的整数倍的值是没有意义的，并且用这样的值进行计算可能会产生异常结果。

除了使用绝对公差外，还存在与使用相对公差相关联的固有不一致性。例如，如果向上或向下缩放模型，则其某些areClose()关系可能会发生更改。

你考虑过使用定点算术吗？这将避免算术异常和一些缩放异常，此外，它还可以让您在评估等式的主题上松一口气。它不会解决所有您的问题，但可能值得一看。