How do I fix this JS function so it doesn't return false positives when checking if two line segments intersect?

Question

I'm working on a mapping project (with the Google Maps SDK). Before drawing a line segment on the map I check to see if it intersects with any existing lines.

I'm experiencing a situation where the code below is reporting the line segments are intersecting, but they're not. Although, they do share an endpoint.

Perhaps this intersect() function isn't meant to be used with Geo coordinates and I need a different function. I found this intersects() function here: Test if two lines intersect - JavaScript function

In this project I have about 150 lines and about 10-15 of them are detected as intersecting, and they're not (although they share a common endpoint with the line that is reported as intersecting).

Below is a screenshot of how the lines are drawn on Google Maps for a better visual. The red line is the second one passed to the intersects() function and is detected as intersecting the first line. Interestingly, if I reverse the lines passed to intersects() it does not find them to be intersecting.

let crosses = intersects(
        39.018223, -76.75899, 39.018387, -76.758773,
        39.018387, -76.758773, 39.019813, -76.757388,
);
      
console.log('Intersects:', crosses);

// returns true if the line from (a,b)->(c,d) intersects with (p,q)->(r,s)
function intersects(a,b,c,d,p,q,r,s) {
        var det, gamma, lambda;
        det = (c - a) * (s - q) - (r - p) * (d - b);
        if (det === 0) {
                console.log('det is zero');
                return false;
        } else {
                lambda = ((s - q) * (r - a) + (p - r) * (s - b)) / det;
                gamma = ((b - d) * (r - a) + (c - a) * (s - b)) / det;
                return (0 < lambda && lambda < 1) && (0 < gamma && gamma < 1);
        }
};

It's not really an answer to my question, so I'll add it as a comment. I ended up checking the line in the opposite order. If the first order fails (such as intersects(a,b,c,d,p,q,r,s)), I try in the opposite order (such as intersects(p,q,r,s, a,b,c,d)). that seems to be working well - no false positives yet. — flyingMonkeys, Jul 02 '22 at 02:46

score 0 · Answer 1 · answered Jun 28 '22 at 01:53

You need to account for numerical precision. As mentioned in a comment of the post, you could test for endpoints but it would add a lot more computation. Another method is to account for precision in the final test by adding an epsilon to the comparison:

let epsilon = 1e-6;
return (epsilon < lambda && lambda < 1-epsilon) &&
       (epsilon <  gamma && gamma  < 1-epsilon);

How do I fix this JS function so it doesn't return false positives when checking if two line segments intersect?

1 Answers1