<分区>
所以这对我来说似乎是一个反复出现的问题 - 我正在尝试在 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
解决了这个问题。所以我的问题是,有没有比磨练公差更好的方法来解决这个问题?或者,您是否应该修改算法以便它们只输出错误的值而不是崩溃?不确定如何从这里继续。
我注意到的一件事是在线段相交算法中,概述了here , 计算交点需要两个单独的函数。基本上,第一次计算与交点相关的事件点时,计算两条线段的交点;我使用以下算法:
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
中使用的相等性测试不一定是可传递的,因此这也会导致一些问题。