Test if two lines intersect - JavaScript function

StackOverflow https://stackoverflow.com/questions/9043992

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.

Was it helpful?

Solution 

// 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!

OTHER TIPS

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 P1 to IP to P4 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 P1 to P2 to P4 also rotates counter clockwise. Additionally, P1 to P2 to P3 rotates clock wise. We can use this knowledge to determine whether two lines intersect or not.

Stretching the face

Intersection Example

Line intersection Line Intersection

You'll notice that intersecting lines create four faces that point opposite directions. Since they face opposite directions, we know that the direction of P1 to P2 to P3 rotates a direction different than P1 to P2 to P4. We also know that P1 to P3 to P4 rotates a different direction than P2 to P3 to P4.

Non-Intersection Example

Line No Intersection Line No Intersection

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>

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.

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));
}

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));
}

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)

Here comes a TypeScript implementation, heavily inspired by Dan Fox's solution. This implementation will give you the intersection point, if there is one. Otherwise (parallel or no intersection), undefined will be returned.

interface Point2D {
  x: number;
  y: number;
}

function intersection(from1: Point2D, to1: Point2D, from2: Point2D, to2: Point2D): Point2D {
  const dX: number = to1.x - from1.x;
  const dY: number = to1.y - from1.y;

  const determinant: number = dX * (to2.y - from2.y) - (to2.x - from2.x) * dY;
  if (determinant === 0) return undefined; // parallel lines

  const lambda: number = ((to2.y - from2.y) * (to2.x - from1.x) + (from2.x - to2.x) * (to2.y - from1.y)) / determinant;
  const gamma: number = ((from1.y - to1.y) * (to2.x - from1.x) + dX * (to2.y - from1.y)) / determinant;

  // check if there is an intersection
  if (!(0 <= lambda && lambda <= 1) || !(0 <= gamma && gamma <= 1)) return undefined;

  return {
    x: from1.x + lambda * dX,
    y: from1.y + lambda * dY,
  };
}

First, find intersection coordinates - here it's described in detail: http://www.mathopenref.com/coordintersection.html

Then check if the x-coordinate for intersection falls within the x ranges for one of the lines (or do the same with y-coordinate, if you prefer), i.e. if xIntersection is between lineAp1x and lineAp2x, then they intersect.

For all folks who would like to have a solutions ready for coldfusion, here is what I adapted from http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/awt/geom/Line2D.java#Line2D.linesIntersect%28double%2Cdouble%2Cdouble%2Cdouble%2Cdouble%2Cdouble%2Cdouble%2Cdouble%29

the imporants functions are ccw and linesIntersect from java.awt.geom.Line2D and I wrote them into coldfusion, so here we go:

<cffunction name="relativeCCW" description="schnittpunkt der vier punkte (2 geraden) berechnen">
<!---
Returns an indicator of where the specified point (px,py) lies with respect to this line segment. See the method comments of relativeCCW(double,double,double,double,double,double) to interpret the return value.
Parameters:
px the X coordinate of the specified point to be compared with this Line2D
py the Y coordinate of the specified point to be compared with this Line2D
Returns:
an integer that indicates the position of the specified coordinates with respect to this Line2D
--->
<cfargument name="x1" type="numeric" required="yes" >
<cfargument name="y1" type="numeric" required="yes">
<cfargument name="x2" type="numeric" required="yes" >
<cfargument name="y2" type="numeric" required="yes">
<cfargument name="px" type="numeric" required="yes" >
<cfargument name="py" type="numeric" required="yes">
    <cfscript>
    x2 = x2 - x1;
    y2 = y2 - y1;
    px = px - x1;
    py = py - y1;
    ccw = (px * y2) - (py * x2);
    if (ccw EQ 0) {
        // The point is colinear, classify based on which side of
        // the segment the point falls on.  We can calculate a
        // relative value using the projection of px,py onto the
        // segment - a negative value indicates the point projects
        // outside of the segment in the direction of the particular
        // endpoint used as the origin for the projection.
        ccw = (px * x2) + (py * y2);
        if (ccw GT 0) {
            // Reverse the projection to be relative to the original x2,y2
            // x2 and y2 are simply negated.
            // px and py need to have (x2 - x1) or (y2 - y1) subtracted
            //    from them (based on the original values)
            // Since we really want to get a positive answer when the
             //    point is "beyond (x2,y2)", then we want to calculate
            //    the inverse anyway - thus we leave x2 & y2 negated.       
            px = px - x2;
            py = py - y2;
            ccw = (px * x2) + (py * y2);
            if (ccw LT 0) {
                ccw = 0;
                }
        }
    }
    if (ccw LT 0) {
        ret = -1;
    }
    else if (ccw GT 0) {
        ret = 1;
    }
    else {
        ret = 0;
    }   
    </cfscript> 
    <cfreturn ret>
</cffunction>


<cffunction name="linesIntersect" description="schnittpunkt der vier punkte (2 geraden) berechnen">
<cfargument name="x1" type="numeric" required="yes" >
<cfargument name="y1" type="numeric" required="yes">
<cfargument name="x2" type="numeric" required="yes" >
<cfargument name="y2" type="numeric" required="yes">
<cfargument name="x3" type="numeric" required="yes" >
<cfargument name="y3" type="numeric" required="yes">
<cfargument name="x4" type="numeric" required="yes" >
<cfargument name="y4" type="numeric" required="yes">
    <cfscript>
    a1 = relativeCCW(x1, y1, x2, y2, x3, y3);
    a2 = relativeCCW(x1, y1, x2, y2, x4, y4);
    a3 = relativeCCW(x3, y3, x4, y4, x1, y1);
    a4 = relativeCCW(x3, y3, x4, y4, x2, y2);
    aa = ((relativeCCW(x1, y1, x2, y2, x3, y3) * relativeCCW(x1, y1, x2, y2, x4, y4) LTE 0)
            && (relativeCCW(x3, y3, x4, y4, x1, y1) * relativeCCW(x3, y3, x4, y4, x2, y2) LTE 0));
    </cfscript>
 <cfreturn aa>
</cffunction>

I hope this can help for adapting to other laguages?

Use the pythageorum theorum to find the distance between the 2 objects and add the radius Pythageorum Theorum Distance Formula

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top