因此​​，这似乎是我 - 一个反复出现的问题，我想实现的线段相交，并在双连边列表覆盖算法的计算几何的由德伯格等人。现在，我使用下面的函数来测试两个值平等：

 私有静态最后双absTol = 1E-14;
私有静态最后双RELTOL = 1E-10;
公共静态最终布尔areClose（双I，双J）{
    返程（Math.abs（I-J）＆LT; = absTol）||
           （Math.abs（九）其中; = RELTOL * Math.max（Math.abs（i）中，Math.abs（j）条））;
}
 

主要的问题我有是，我会遇到一个错误。比如，今天我才意识到，我的职能之一是失败的，因为我原本设置 absTol 到 1E-16 和上述功能失败的时候我的功能之一应该已经确定了 0.0 和 1.535e-15 都是平等的。我通过调整解决了这一问题 absTol 至 1E-14 。所以我的问题是，有没有更好的方式来攻击这个问题呢磨炼公差？或者，您应该修改算法，让他们简单地输出了错误的价值观，而不是崩溃？不知道究竟是如何从这里出发。

有一件事我注意到的是，在该线段相交算法，概述here,两个单独的功能是必需的，用于计算相交点。基本上，在第一时间的交点相关的事件点被计算，则计算两个段的交点;我用下面的算法：

 公共静态的Point2D findIntersection（Line2D中一号线，2号线的Line2D）{
    双S1X = line1.getX2（） -  line1.getX1（）;
    双s1Y = line1.getY2（） -  line1.getY1（）;
    双S2X = line2.getX2（） -  line2.getX1（）;
    双s2Y = line2.getY2（） -  line2.getY1（）;

    双S =（-s1Y *（line1.getX1（） -  line2.getX1（））+ S1X *（line1.getY1（） -  line2.getY1（）））/（ -  S2X * s1Y + S1X * s2Y）;
    双吨=（S2X *（line1.getY1（） -  line2.getY1（）） -  s2Y *（line1.getX1（） -  line2.getX1（）））/（ -  S2X * s1Y + S1X * s2Y）;

    如果（S＆GT; = 0＆功放;＆功放; S＆LT; = 1＆安培;＆amp; T公司＆GT; = 0＆功放;＆amp; T公司＆LT; = 1）{
        返回新Point2D.Double（line1.getX1（）+（T * S1X），line1.getY1（）+（T * s1Y））;
    } 其他 {
        返回null;
    }
}
 

不过，确定线路的平等地位的时候，我一直在使用：

 专用双getIntercept（的Line2D线）{
    如果（MathUtilities.areClose（line.getY1（），line.getY2（）））{
        //线是水平的。交集为x值
        返回this.x;
    } 其他 {
        返回line.getX1（）+（line.getX2（） -  line.getX1（））*（（this.y-line.getY1（））/（line.getY2（） -  line.getY1（）））;
    }
}
 

测试，其中线相交的事件行（和当两个或更多的行具有相同的截距，它们相交于相同位置的事件行）。所以基本上，两种不同的算法用于找到交点，这意味着我得到的值稍有不同。最后，我也认识到，在 areClose 所使用的测试平等不一定传递，因此这也将导致一些问题。

与计算几何精确处理的是，来了往往比你想象的一个问题。除了定点算术运算（它已经被建议），另一种方法是使用自适应precision算术 - 在比双precision更好评估操作，但仅在必要时以preserve正确性

实现自适应precision操作在很大程度上是一个不平凡的任务，但也有一些库可用，即Shewchuck的的稳健predicates 的和/或 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.