Test if two lines intersect - JavaScript function

Question

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.

Answer 1

// returns true iff 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!

Answer 2

function lineIntersect(x1,y1,x2,y2, x3,y3,x4,y4) {
    var x=((x1*y2-y1*x2)*(x3-x4)-(x1-x2)*(x3*y4-y3*x4))/((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4));
    var y=((x1*y2-y1*x2)*(y3-y4)-(y1-y2)*(x3*y4-y3*x4))/((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4));
    if (isNaN(x)||isNaN(y)) {
        return false;
    } else {
        if (x1>=x2) {
            if (!(x2<=x&&x<=x1)) {return false;}
        } else {
            if (!(x1<=x&&x<=x2)) {return false;}
        }
        if (y1>=y2) {
            if (!(y2<=y&&y<=y1)) {return false;}
        } else {
            if (!(y1<=y&&y<=y2)) {return false;}
        }
        if (x3>=x4) {
            if (!(x4<=x&&x<=x3)) {return false;}
        } else {
            if (!(x3<=x&&x<=x4)) {return false;}
        }
        if (y3>=y4) {
            if (!(y4<=y&&y<=y3)) {return false;}
        } else {
            if (!(y3<=y&&y<=y4)) {return false;}
        }
    }
    return true;
}

The wiki page I found the answer from.

Answer 3

Here's a version based on this gist with some more concise variable names, and some Coffee.

JavaScript version

var lineSegmentsIntersect = (x1, y1, x2, y2, x3, y3, x4, y4)=> {
    var a_dx = x2 - x1;
    var a_dy = y2 - y1;
    var b_dx = x4 - x3;
    var b_dy = y4 - y3;
    var s = (-a_dy * (x1 - x3) + a_dx * (y1 - y3)) / (-b_dx * a_dy + a_dx * b_dy);
    var t = (+b_dx * (y1 - y3) - b_dy * (x1 - x3)) / (-b_dx * a_dy + a_dx * b_dy);
    return (s >= 0 && s <= 1 && t >= 0 && t <= 1);
}

CoffeeScript version

lineSegmentsIntersect = (x1, y1, x2, y2, x3, y3, x4, y4)->
    a_dx = x2 - x1
    a_dy = y2 - y1
    b_dx = x4 - x3
    b_dy = y4 - y3
    s = (-a_dy * (x1 - x3) + a_dx * (y1 - y3)) / (-b_dx * a_dy + a_dx * b_dy)
    t = (+b_dx * (y1 - y3) - b_dy * (x1 - x3)) / (-b_dx * a_dy + a_dx * b_dy)
    (0 <= s <= 1 and 0 <= t <= 1)

Answer 4

Although it is useful to be able to find the intersection point, testing for whether line segments intersect is most often used for polygon hit-testing, and given the usual applications of that, you need to do it fast. Therefore I suggest you do it like this, using only subtraction, multiplication, comparison and AND. Turn computes the direction of the change in slope between the two edges described by the three points: 1 means counter-clockwise, 0 means no turn and -1 means clockwise.

This code expects points expressed as GLatLng objects but can be trivially rewritten to other systems of representation. The slope comparison has been normalised to epsilon tolerance to damp floating point errors.

function Turn(p1, p2, p3) {
  a = p1.lng(); b = p1.lat(); 
  c = p2.lng(); d = p2.lat();
  e = p3.lng(); f = p3.lat();
  A = (f - b) * (c - a);
  B = (d - b) * (e - a);
  return (A > B + Number.EPSILON) ? 1 : (A + Number.EPSILON < B) ? -1 : 0;
}

function isIntersect(p1, p2, p3, p4) {
  return (Turn(p1, p3, p4) != Turn(p2, p3, p4)) && (Turn(p1, p2, p3) != Turn(p1, p2, p4));
}

Answer 5

I've rewritten Peter Wone's answer to a single function using x/y instead of lat()/long()

function isIntersecting(p1, p2, p3, p4) {
    function CCW(p1, p2, p3) {
        return (p3.y - p1.y) * (p2.x - p1.x) > (p2.y - p1.y) * (p3.x - p1.x);
    }
    return (CCW(p1, p3, p4) != CCW(p2, p3, p4)) && (CCW(p1, p2, p3) != CCW(p1, p2, p4));
}

Answer 6

Peter Wone's answer is a great solution, but it lacks an explanation. I spent the last hour or so understanding how it works and think I understand enough to explain it as well. See his answer for details: https://stackoverflow.com/a/16725715/697477

I've also included a solution for the co-linear lines in the code below.

Using Rotational Directions to check for intersection

To explain the answer, let's look at something common about every intersection of two lines. Given the picture below, we can see that P₁ to IP to P₄ rotates counter clockwise. We can see that it's complimentary sides rotate clockwise. Now, we don't know if it intersects, so we don't know the intersection point. But we can also see that P₁ to P₂ to P₄ also rotates counter clockwise. Additionally, P₁ to P₂ to P₃ rotates clock wise. We can use this knowledge to determine whether two lines intersect or not.

Intersection Example

You'll notice that intersecting lines create four faces that point opposite directions. Since they face opposite directions, we know that the direction of P₁ to P₂ to P₃ rotates a direction different than P₁ to P₂ to P₄. We also know that P₁ to P₃ to P₄ rotates a different direction than P₂ to P₃ to P₄.

Non-Intersection Example

In this example, you should notice that following the same pattern for the intersection test, the two faces rotate the same direction. Since they face the same direction, we know that they do not intersect.

Code Sample

So, we can implement this into the original code supplied by Peter Wone.

// Check the direction these three points rotate
function RotationDirection(p1x, p1y, p2x, p2y, p3x, p3y) {
  if (((p3y - p1y) * (p2x - p1x)) > ((p2y - p1y) * (p3x - p1x)))
    return 1;
  else if (((p3y - p1y) * (p2x - p1x)) == ((p2y - p1y) * (p3x - p1x)))
    return 0;
  
  return -1;
}

function containsSegment(x1, y1, x2, y2, sx, sy) {
  if (x1 < x2 && x1 < sx && sx < x2) return true;
  else if (x2 < x1 && x2 < sx && sx < x1) return true;
  else if (y1 < y2 && y1 < sy && sy < y2) return true;
  else if (y2 < y1 && y2 < sy && sy < y1) return true;
  else if (x1 == sx && y1 == sy || x2 == sx && y2 == sy) return true;
  return false;
}

function hasIntersection(x1, y1, x2, y2, x3, y3, x4, y4) {
  var f1 = RotationDirection(x1, y1, x2, y2, x4, y4);
  var f2 = RotationDirection(x1, y1, x2, y2, x3, y3);
  var f3 = RotationDirection(x1, y1, x3, y3, x4, y4);
  var f4 = RotationDirection(x2, y2, x3, y3, x4, y4);
  
  // If the faces rotate opposite directions, they intersect.
  var intersect = f1 != f2 && f3 != f4;
  
  // If the segments are on the same line, we have to check for overlap.
  if (f1 == 0 && f2 == 0 && f3 == 0 && f4 == 0) {
    intersect = containsSegment(x1, y1, x2, y2, x3, y3) || containsSegment(x1, y1, x2, y2, x4, y4) ||
    containsSegment(x3, y3, x4, y4, x1, y1) || containsSegment(x3, y3, x4, y4, x2, y2);
  }
  
  return intersect;
}

// Main call for checking intersection. Particularly verbose for explanation purposes.
function checkIntersection() {
  // Grab the values
  var x1 = parseInt($('#p1x').val());
  var y1 = parseInt($('#p1y').val());
  var x2 = parseInt($('#p2x').val());
  var y2 = parseInt($('#p2y').val());
  var x3 = parseInt($('#p3x').val());
  var y3 = parseInt($('#p3y').val());
  var x4 = parseInt($('#p4x').val());
  var y4 = parseInt($('#p4y').val());

  // Determine the direction they rotate. (You can combine this all into one step.)
  var face1CounterClockwise = RotationDirection(x1, y1, x2, y2, x4, y4);
  var face2CounterClockwise = RotationDirection(x1, y1, x2, y2, x3, y3);
  var face3CounterClockwise = RotationDirection(x1, y1, x3, y3, x4, y4);
  var face4CounterClockwise = RotationDirection(x2, y2, x3, y3, x4, y4);

  // If face 1 and face 2 rotate different directions and face 3 and face 4 rotate different directions, 
  // then the lines intersect.
  var intersect = hasIntersection(x1, y1, x2, y2, x3, y3, x4, y4);

  // Output the results.
  var output = "Face 1 (P1, P2, P4) Rotates: " + ((face1CounterClockwise > 0) ? "counterClockWise" : ((face1CounterClockwise == 0) ? "Linear" : "clockwise")) + "<br />";
  var output = output + "Face 2 (P1, P2, P3) Rotates: " + ((face2CounterClockwise > 0) ? "counterClockWise" : ((face2CounterClockwise == 0) ? "Linear" : "clockwise")) + "<br />";
  var output = output + "Face 3 (P1, P3, P4) Rotates: " + ((face3CounterClockwise > 0) ? "counterClockWise" : ((face3CounterClockwise == 0) ? "Linear" : "clockwise")) + "<br />";
  var output = output + "Face 4 (P2, P3, P4) Rotates: " + ((face4CounterClockwise > 0) ? "counterClockWise" : ((face4CounterClockwise == 0) ? "Linear" : "clockwise")) + "<br />";
  var output = output + "Intersection: " + ((intersect) ? "Yes" : "No") + "<br />";
  $('#result').html(output);


  // Draw the lines.
  var canvas = $("#canvas");
  var context = canvas.get(0).getContext('2d');
  context.clearRect(0, 0, canvas.get(0).width, canvas.get(0).height);
  context.beginPath();
  context.moveTo(x1, y1);
  context.lineTo(x2, y2);
  context.moveTo(x3, y3);
  context.lineTo(x4, y4);
  context.stroke();
}

checkIntersection();

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

<canvas id="canvas" width="200" height="200" style="border: 2px solid #000000; float: right;"></canvas>
<div style="float: left;">
  <div style="float: left;">
    <b>Line 1:</b>
    <br />P1 x:
    <input type="number" min="0" max="200" id="p1x" style="width: 40px;" onChange="checkIntersection();" value="0">y:
    <input type="number" min="0" max="200" id="p1y" style="width: 40px;" onChange="checkIntersection();" value="20">
    <br />P2 x:
    <input type="number" min="0" max="200" id="p2x" style="width: 40px;" onChange="checkIntersection();" value="100">y:
    <input type="number" min="0" max="200" id="p2y" style="width: 40px;" onChange="checkIntersection();" value="20">
    <br />
  </div>
  <div style="float: left;">
    <b>Line 2:</b>
    <br />P3 x:
    <input type="number" min="0" max="200" id="p3x" style="width: 40px;" onChange="checkIntersection();" value="150">y:
    <input type="number" min="0" max="200" id="p3y" style="width: 40px;" onChange="checkIntersection();" value="100">
    <br />P4 x:
    <input type="number" min="0" max="200" id="p4x" style="width: 40px;" onChange="checkIntersection();" value="0">y:
    <input type="number" min="0" max="200" id="p4y" style="width: 40px;" onChange="checkIntersection();" value="0">
    <br />
  </div>
  <br style="clear: both;" />
  <br />
  <div style="float: left; border: 1px solid #EEEEEE; padding: 2px;" id="result"></div>
</div>