Line Segement Intersection — Works Sometimes, Sometimes Not

I'd like to display the point of intersection of two line segments. The Segments are animated, so they start and stop to intersect, based on progress. Therefore I have this code:

Solution 1:

A simpler solution is to check if one segment ends are on different half-planes in respect to the other segment and vice-versa. This requires no divisions:

function side(a, b, p) {
    return (p.x - a.x)*(b.y - a.y) + (p.y - a.y)*(a.x - b.x);
}

function xsect(a0, b0, a1, b1) {
    return (side(a0, b0, a1) * side(a0, b0, b1) < 0 &&
            side(a1, b1, a0) * side(a1, b1, b0) < 0)
}

Things are more annoying if you need to include boundary points and/or collinear segments intersection (note also that the intersection point of two segments even with integer coordinates may be impossible to represent exactly with floating point numbers without approximation - e.g. (0, 0)-(1, 10) with (0, 1)-(10, 1)).

Solution 2:

The dot variable is in reality the determinant (or the 2D cross product). The problem is that the determinant can be negative. Thus you need to test the absolute value of the determinant. Moreover, Number.EPSILON is the smallest non-zero number, which is not useful is case of numerical inaccuracy. You should instead use a more reasonable value:

Math.abs(dot) <= 1e-8

Moreover, the determinant should be calculated using the segment point, not the bounding box min/max:

dot = ((x - this.x1) * (this.y2 - this.y1)) - ((y - this.y1) * (this.x2 - this.x1))

Solution 3:

Line intercepts

The following functions finds the intercept, if any, as a point {x, y} of two lines defined by two points {p1:{x,y}, p2{x,y}} on each line.

The first two function are for line segments (each has a fixed length) and the last two functions are infinitely long lines.

Line segment intercept

As 4 points p1 = {x,y}, p2 = {x,y}, p3 = {x,y}, p4 = {x,y} defining end points of two line segments. Returns point only if there is an intercept, else return undefined.

functioninterceptSegs(p1, p2, p3, p4, p = {}) {
    const x1 = p2.x - p1.x, y1 = p2.y - p1.y;
    const x2 = p4.x - p3.x, y2 = p4.y - p3.y;
    const c = x1 * y2 - y1 * x2;
    if (c) {
        const x3 = p1.x - p3.x, y3 = p1.y - p3.y;
        const u = (x1 * y3 - y1 * x3) / c;
        if (u >= 0 && u <= 1) {
            const u = (x2 * y3 - y2 * x3) / c;
            if (u >= 0 && u <= 1) {
                p.x = p1.x + x1 * u;
                p.y = p1.y + y1 * u;    
                return p;
            }
        }
    }
}

OR As two lines l1 = {p1:{x,y}, p2{x,y}}, l2 = {p1:{x,y}, p2{x,y}} returns point only if there is an intercept.

functioninterceptSegs(l1, l2) {
    const a = {x: l1.p2.x - l1.p1.x, y: l1.p2.y - l1.p1.y};
    const b = {x: l2.p2.x - l2.p1.x, y: l2.p2.y - l2.p1.y};
    const c = a.x * b.y - a.y * b.x;
    if (c) {
        const e = {x: l1.p1.x - l2.p1.x, y: l1.p1.y - l2.p1.y};
        const u = (a.x * e.y - a.y * e.x) / c;
        if (u >= 0 && u <= 1) {
            const u = (b.x * e.y - b.y * e.x) / c;
            if (u >= 0 && u <= 1) {
                return {x: l1.p1.x + a.x * u, y: l1.p1.y + a.y * u};
            }
        }
    }
}

Intercept lines

Similar to above functions but assumes lines are infinitely long. Will return a point or undefined if lines are parallel.

functionintercept(p1, p2, p3, p4, p = {}) {
    const x1 = p2.x - p1.x, y1 = p2.y - p1.y;
    const x2 = p4.x - p3.x, y2 = p4.y - p3.y;
    const c = x1 * y2 - y1 * x2;
    if (c) {
        let u = (x1 * (p1.y - p3.y) - y1 * (p1.x - p3.x)) / c;
        p.x = p3.x + x2 * u;
        p.y = p3.y + y2 * u;    
        return p;
    }
}

OR As lines l1, l2 returns point only if there is an intercept. Returns undefined if line are parallel.

functioninterceptLines(l1, l2) {
    const a = {x: l1.p2.x - l1.p1.x, y: l1.p2.y - l1.p1.y};
    const b = {x: l2.p2.x - l2.p1.x, y: l2.p2.y - l2.p1.y};
    const c = a.x * b.y - a.y * b.x;
    if (c) {
        const u = (a.x * (l1.p1.y - l2.p1.y) - a.y * (l1.p1.x - l2.p1.x)) / c;
        return {x: l2.p1.x + b.x * u, y: l2.p1.y + b.y * u};
    }
}