Skip to content

Instantly share code, notes, and snippets.

@lengstrom
Created January 19, 2014 01:46
Show Gist options
  • Save lengstrom/8499382 to your computer and use it in GitHub Desktop.
Save lengstrom/8499382 to your computer and use it in GitHub Desktop.
Algorithm for checking whether two line segments intersect, written in Javascript.
function intersect(x1, y1, x2, y2, x3, y3, x4, y4){
var a1, a2, b1, b2, c1, c2;
var r1, r2 , r3, r4;
var denom, offset, num;
// Compute a1, b1, c1, where line joining points 1 and 2
// is "a1 x + b1 y + c1 = 0".
a1 = y2 - y1;
b1 = x1 - x2;
c1 = (x2 * y1) - (x1 * y2);
// Compute r3 and r4.
r3 = ((a1 * x3) + (b1 * y3) + c1);
r4 = ((a1 * x4) + (b1 * y4) + c1);
// Check signs of r3 and r4. If both point 3 and point 4 lie on
// same side of line 1, the line segments do not intersect.
if ((r3 !== 0) && (r4 !== 0) && sameSign(r3, r4)){
return 0; //return that they do not intersect
}
// Compute a2, b2, c2
a2 = y4 - y3;
b2 = x3 - x4;
c2 = (x4 * y3) - (x3 * y4);
// Compute r1 and r2
r1 = (a2 * x1) + (b2 * y1) + c2;
r2 = (a2 * x2) + (b2 * y2) + c2;
// Check signs of r1 and r2. If both point 1 and point 2 lie
// on same side of second line segment, the line segments do
// not intersect.
if ((r1 !== 0) && (r2 !== 0) && (sameSign(r1, r2))){
return 0; //return that they do not intersect
}
//Line segments intersect: compute intersection point.
denom = (a1 * b2) - (a2 * b1);
if (denom === 0) {
return 1; //collinear
}
// lines_intersect
return 1; //lines intersect, return true
}
@apilguk
Copy link

apilguk commented Nov 20, 2017

const sameSign = (a, b) => (a * b) > 0;

@kostelnik
Copy link

offset and num are unused

@bevan77
Copy link

bevan77 commented May 20, 2018

I tried this but get the message "Uncaught ReferenceError: sameSign is not defined"
Do you know what could cause this?

@sumit2201
Copy link

what is the unit of Intersection point?
denom = (a1 * b2) - (a2 * b1);

@pixelchai
Copy link

@bevan77 You can define "sameSign" like so if you really want:

function sameSign(a,b){
   return Math.sign(a)==Math.sign(b);
}

@TaIos
Copy link

TaIos commented Dec 19, 2018

"Compute r3 and r4" , what are r3 are r4 ?

@jdeboi
Copy link

jdeboi commented Nov 12, 2020

This function returned 1 for me on for the case when two lines are parallel but clearly far apart (e.g. all same x values but different, non-overlapping y ranges). I think it should return 1 if they're collinear and at least partially overlapping, but otherwise return 0. I added this line of code, which is currently working for me, although I haven't totally thought through it.

//collinear  
if (denom === 0) {  
    const xBetween = (x1 >= x3 && x1 <= x4 || x2 >= x3 && x2 <= x4 || x3 <= x1 && x3>=x2 );   
    const yBetween = (y1 >= y3 && y1 <= y4 || y2 >= y3 && y2 <= y4 || y3 <= y1 && y3>=y2 );   
    if (xBetween && yBetween ) { 
      return 1;      
    }   
    return 0;    
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment