General Testing Strategies for Double Precision Equality in Computational Geometry
So this presents a recurring problem to me. I am trying to implement line segment intersection and doubly connected edge list overlay algorithms in computational geometry from Berg et al. Right now I am using the following function to test if two values are equal:
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 am facing is that I sometimes experience an error. For example, today I realized that one of my functions failed because I originally set absTol
to 1e-16
, and the above function failed when one of my functions was supposed to identify that 0.0
both 1.535e-15
were equal. I fixed the problem by installing absTol
before 1e-14
. So my question is, is there a better way to attack this problem and then hone the tolerances? Or if you change the algorithm so that they just output the wrong values instead of crashing? Not sure exactly how to proceed from here.
Note that in the line segment intersection algorithm outlined here , two separate functions are needed to calculate the intersection points. Basically, the first time you compute the intersection event point, you compute the intersection of the two segments; I am using 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 equality of strings in status, I used:
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 check where the lines cross the line of events (and when two or more lines have the same intercept, they cross the line of events at the same position). Thus, two different algorithms are used to find the intersection points, which means that the values I get are slightly different. Finally, I also realized that the equality test used in areClose
is not necessarily transitive, so this would cause some problems as well.
source to share
You have a significant problem in that you are storing coordinates (potentially) with higher precision than it makes sense. That is, if two values are always considered equal, if they differ by less than absTol
, then it makes no sense to store or use values that are not integer multiples absTol
, and performing calculations with such values may lead to abnormal results.
You also have an inherent inconsistency associated with using relative tolerance in addition to absolute tolerance. For example, if you scale the model up or down, some of its relationships areClose()
may change.
Have you considered using fixed point arithmetic? This will avoid arithmetic anomalies and some scaling anomalies, plus it will give you some relief on the topic of evaluating equality. This won't fix all of your problems, but it might be worth a look.
source to share
Working with "precision" in computational geometry is a problem that occurs more often than you might think. Apart from fixed-point arithmetic (which has already been proposed), another approach is to use adaptive-precision arithmetic-evaluating operations rather than double precision, but only when necessary to preserve correctness.
Implementing adaptive operations on precision points is a very simple task, but there are several libraries available, i.e. Shewchuck robust predicates and / or MPFR library that is used by the CGAL geometry library. In the meantime, there is no need to know about it. ”
Reliable detection of the intersection between two lines can be done with a few calls to the Shewchuk procedure orientation
.
source to share