javascriptcollision-detectionintersectionline-intersection

Test if two lines intersect - JavaScript function


I've tried searching for a javascript function that will detect if two lines intersect each other.

The function will take the x,y values of both the start end points for each line (we'll call them line A and line B).

Is to return true if they intersect, otherwise false.

Example of the function. I'm happy if the answer uses a vector object instead.

Function isIntersect (lineAp1x, lineAp1y, lineAp2x, lineAp2y, lineBp1x, lineBp1y, lineBp2x, lineBp2y) 
{

    // JavaScript line intersecting test here. 

}

Some background info: this code is for a game I'm trying to make in html5 canvas, and is part of my collision detection.


Solution

  • // 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) {
        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);
      }
    };
    

    Explanation: (vectors, a matrix and a cheeky determinant)

    Lines can be described by some initial vector, v, and a direction vector, d:

    r = v + lambda*d 
    

    We use one point (a,b) as the initial vector and the difference between them (c-a,d-b) as the direction vector. Likewise for our second line.

    If our two lines intersect, then there must be a point, X, that is reachable by travelling some distance, lambda, along our first line and also reachable by travelling gamma units along our second line. This gives us two simultaneous equations for the coordinates of X:

    X = v1 + lambda*d1 
    X = v2 + gamma *d2
    

    These equations can be represented in matrix form. We check that the determinant is non-zero to see if the intersection X even exists.

    If there is an intersection, then we must check that the intersection actually lies between both sets of points. If lambda is greater than 1, the intersection is beyond the second point. If lambda is less than 0, the intersection is before the first point.

    Hence, 0<lambda<1 && 0<gamma<1 indicates that the two lines intersect!