CODEWITHSUNDEEP
floating-pointprecisioncomputational-geometry
leonidasarch
leonidasarch

Reputation: 97

How to handle floating point error in line segment contains point algorithm

I am working on some geometric algorithms and I've been struggling for a while with floating point error mitigation.

More specifically, I have written a method for checking whether a line segment contains a point by comparing the sum of the distance of this point to the two endpoints of the segment with the length of the line segment.

I am currently using a fixed epsilon value, but it seems to be returning invalid outputs when the point is too close to the endpoints or when the line segment is too long.

Sample code in Java below:

public boolean lineSegmentContainsPoint(Vec3D line, Vec3D point) {
        final float eps = 0.001f;
        final float lineLength = line.startPt.distanceTo(line.endPt);
        final float distanceToStart = point.distanceTo(line.startPt);
        final float distanceToEnd = point.distanceTo(line.endPt);
        return Math.abs(lineLength - (distanceToStart + distanceToEnd)) < eps;
    }

I understand that the issue is caused due to accumulative floating point errors, but it's not really clear how I could tackle it. I tried using double instead of float, but it didn't really help in the above mentioned edge cases. Any suggestions or help would be really appreciated!

Upvotes: 1

Views: 159

Answers (1)

user1196549
user1196549

Reputation:

The locus of the points such that

D0 + D1 - L < ε

(by the triangular inequality, no need to take the absolute value) is the inside of an ellipse with long axis 

L + ε/2

and short axis

√(2Lε + ε²).

It may contain points that you don't expect. I wouldn't rate this test as a good for "line segment insideness". I doubt that your problem has anything to do with floating-point inaccuracy.

Upvotes: 1

Related Questions