用于在计算几何学中测试双精度数字的平等的一般策略 [英] General strategies for testing for equality of double precision numbers in computational geometry

问题描述

所以这似乎是一个重现的问题，我正在尝试在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）））; 
} 
  

我遇到的主要问题是我偶尔会遇到一个错误。例如，今天我意识到我的一个功能是失败的，因为我最初将 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 ）; 
 
如果（s> = 0&&< = 1&&&> = 0&<< = 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（）））{
 //行是水平的。将交集设置为x值
 return this.x; 
} else {
 return line.getX1（）+（line.getX2（） -  line.getX1（））*（（this.y-line.getY1（））/（line.getY2 ）-line.getY1（）））; 
} 
} 
  

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

解决方案

处理计算几何中的准确性是一个比您想象的更多的问题。除了定点算术（已经被提出）之外，另一种方法是使用自适应精度算术 - 以双精度来评估操作，但只有在必要时才能保持正确性。

实施自适应精度操作是非常不寻常的任务，但是有几个可用的库，即Shewchuck的强大的谓词和/或使用的 MPFR库通过CGAL几何图书馆。

可以通过几次调用Shewchuk的方向来实现两条线之间的交叉点。例行。

So this seems to be a reoccurring problem for me- I'm trying to implement the line segment intersection and doubly connected edge list overlay algorithms in Computational Geometry by de Berg et al. Right now, I'm using the following function to test for equality of two values:

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)));
}

The main problem I'm having is that I'll occasionally experience a bug. For example, today I realized that one of my functions was failing because I had originally set absTol to 1e-16 and the above function failed when one of my functions should have identified that 0.0 and 1.535e-15 were equal. I fixed the problem by adjusting absTol up to 1e-14. So my question is, is there a better way to attack this problem then honing the tolerances? Or, should you modify the algorithm so that they simply output the wrong values instead of crashing? Not sure exactly how to proceed from here.

One thing I note is that in the line segment intersection algorithm, outlined here, two separate functions are necessary for calculating intersection points. Basically, the first time an intersection related event point is calculated, you calculate the intersection of two segments; I use the following algorithm:

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; 
    }
}

But, when determining the equality of lines in the status, I've been using:

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()));
    }   
}

to test where lines intersect the event line (and when two or more lines have the same intercept, they intersect the event line at the same position). So essentially, two different algorithms are used to find intersection points, which means the values I get differ slightly. Lastly, I've also come to realize that the test for equality used in areClose is not necessarily transitive, so that will also cause some problems.

解决方案

Dealing with "exactness" in computational geometry is an issue that comes up more often than you might think. Other than fixed point arithmetic (which has already been suggested), another approach is to use adaptive precision arithmetic -- evaluating operations in better than double precision, but only when necessary to preserve correctness.

Implementing adaptive precision operations is very much a non-trivial task, but there are a few libraries that are available, i.e. Shewchuck's robust predicates and/or the MPFR library that is used by the CGAL geometry library.

Robustly detecting the intersection between two lines could be done via a few calls to Shewchuk's orientation routine.

这篇关于用于在计算几何学中测试双精度数字的平等的一般策略的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！