Test if two lines intersect – JavaScript function

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

More Related Contents:

  1. Simplest code for array intersection in javascript
  2. jQuery/JavaScript collision detection
  3. JavaScript: Collision detection
  4. Improving performance of click detection on a staggered column isometric grid
  5. How to detect collision in three.js?
  6. Detecting collision of rectangle with circle
  7. calculating the point of intersection of two lines
  8. javascript show intro animation, then website
  9. Choosing and activating the right controls on an AJAX-driven site
  10. Get cookie by name
  11. How to pass parameters using ui-sref in ui-router to controller
  12. Callback after all asynchronous forEach callbacks are completed
  13. Why does a while loop block the event loop?
  14. How can I custom-format the Autocomplete plug-in results?
  15. (HTML) Download a PDF file instead of opening them in browser when clicked
  16. Merging or Combining two onEdit trigger functions
  17. Relation between CommonJS, AMD and RequireJS?
  18. Intercepting call to the back button in my AJAX application
  19. Why do I need to copy an array to use a method on it?
  20. JavaScript string with new line – but not using \n
  21. Why do I have to .bind(this) for methods defined in React component class, but not in regular ES6 class
  22. How can I hide or encrypt JavaScript code? [duplicate]
  23. Why should use “apply”?
  24. How to disable editing for some cells in row editing of JQGrid?
  25. myDiv.style.display returns blank when set in master stylesheet
  26. Can I use additional parameters in recursion problems?
  27. How to remove part of a string before a “:” in javascript?
  28. How can I convert a date to GMT?
  29. JavaScript Multidimensional Arrays [duplicate]
  30. Refresh iFrame (Cache Issue)

Leave a Comment