How to efficiently check if two line segments intersect?

Question

I've referenced this answer (has an interactive desmos visualization) in a related question to develop this Javascript function:

function doLineSegmentsIntersect(a1X, a1Y, a2X, a2Y, b1X, b1Y, b2X, b2Y) {
  const dxA = a2X - a1X;
  const dyA = a2Y - a1Y;
  const dxB = b2X - b1X;
  const dyB = b2Y - b1Y;

  // Calculate cross product values to determine orientation
  const p0 = dyB * (b2X - a1X) - dxB * (b2Y - a1Y);
  const p1 = dyB * (b2X - a2X) - dxB * (b2Y - a2Y);
  const p2 = dyA * (a2X - b1X) - dxA * (a2Y - b1Y);
  const p3 = dyA * (a2X - b2X) - dxA * (a2Y - b2Y);

  // The segments intersect if the products of these cross products are non-positive (i.e. the segments straddle each other)
  return (p0 * p1 <= 0) && (p2 * p3 <= 0);
}

I assume this is the most efficient way to calculate this.

I desire these properties:

1. Line segments should not be considered intersecting just because they share a vertex
2. Line segments that overlap should be considered intersecting
3. Line segments shouldn't be considered intersecting just because they share the same slope

With the current solution above, lines that overlap are considered intersecting (this is good). The problem is that they are also considered intersecting if they are not touching but they are in a line (this is bad). In addition, whenever they share a vertex, they are also considered intersecting (this is also bad).

We can improve some things by changing this line:

return (p0 * p1 <= 0) && (p2 * p3 <= 0);

To this:

return (p0 * p1 < 0) && (p2 * p3 < 0);

Now, when they're in a line but otherwise not touching, they are no longer considered intersecting (this is good). In addition, they can also share a vertex and not be considered intersecting (this is also good). The problem is that now when they overlap completely, they are no longer considered intersecting (which we had with the previous solution).

Is there a way to concisely satisfy all desired properties?

The problem with <= is:

• non-touching line segments in a line are considered intersecting
• line segments that share a vertex are considered intersecting

The problem with < is:

• overlapping line segments are not considered intersecting

Answer 1

My current solution, which seems to work:

/// Finds orientation of ordered triplet (a, b, c).
/// Collinear = 0, Clockwise = 1, Counterclockwise = 2
function orientation(aX, aY, bX, bY, cX, cY) {
  const val = (bY - aY) * (cX - bX) - (bX - aX) * (cY - bY);

  if (val === 0) {
    return 0;
  }

  return val > 0 ? 1 : 2;
}

export function doLineSegmentsIntersect(a1X, a1Y, a2X, a2Y, b1X, b1Y, b2X, b2Y): boolean {
  // Check if any of the endpoints coincide; returning false if they do
  if ((a1X === b1X && a1Y === b1Y) || 
      (a1X === b2X && a1Y === b2Y) || 
      (a2X === b1X && a2Y === b1Y) || 
      (a2X === b2X && a2Y === b2Y)) {
    return false;
  }
  
  const aMaxX = Math.max(a1X, a2X);
  const aMinX = Math.min(a1X, a2X);
  const aMaxY = Math.max(a1Y, a2Y);
  const aMinY = Math.min(a1Y, a2Y);
  const bMaxX = Math.max(b1X, b2X);
  const bMinX = Math.min(b1X, b2X);
  const bMaxY = Math.max(b1Y, b2Y);
  const bMinY = Math.min(b1Y, b2Y);
  
  // Quick bounding-box reject
  if (bMaxX < aMinX || bMinX > aMaxX || bMaxY < aMinY || bMinY > aMaxY) {
    return false;
  }

  // Find the four orientations needed for the general and special cases.
  const o1 = orientation(a1X, a1Y, a2X, a2Y, b1X, b1Y);
  const o2 = orientation(a1X, a1Y, a2X, a2Y, b2X, b2Y);
  const o3 = orientation(b1X, b1Y, b2X, b2Y, a1X, a1Y);
  const o4 = orientation(b1X, b1Y, b2X, b2Y, a2X, a2Y);

  return (o1 !== o2 && o3 !== o4) ||
         (o1 === 0 && b1X <= aMaxX && b1X >= aMinX && b1Y <= aMaxY && b1Y >= aMinY) ||
         (o2 === 0 && b2X <= aMaxX && b2X >= aMinX && b2Y <= aMaxY && b2Y >= aMinY) ||
         (o3 === 0 && a1X <= bMaxX && a1X >= bMinX && a1Y <= bMaxY && a1Y >= bMinY) ||
         (o4 === 0 && a2X <= bMaxX && a2X >= bMinX && a2Y <= bMaxY && a2Y >= bMinY);
}

Answer 2

    function doLineSegmentsIntersect(a1X, a1Y, a2X, a2Y, b1X, b1Y, b2X, b2Y) {
  const dxA = a2X - a1X;
  const dyA = a2Y - a1Y;
  const dxB = b2X - b1X;
  const dyB = b2Y - b1Y;

  // Calculate cross product values to determine orientation
  const p0 = dyB * (b2X - a1X) - dxB * (b2Y - a1Y);
  const p1 = dyB * (b2X - a2X) - dxB * (b2Y - a2Y);
  const p2 = dyA * (a2X - b1X) - dxA * (a2Y - b1Y);
  const p3 = dyA * (a2X - b2X) - dxA * (a2Y - b2Y);

  // Check proper intersection case (segments straddle each other)
  if ((p0 * p1 < 0) && (p2 * p3 < 0)) {
    return true;
  }

  // Check collinear case: If they are collinear, check for overlap
  if (p0 === 0 && p1 === 0 && p2 === 0 && p3 === 0) {
    return isOverlapping(a1X, a1Y, a2X, a2Y, b1X, b1Y, b2X, b2Y);
  }

  return false;
}

// Helper function to check if collinear segments overlap
function isOverlapping(a1X, a1Y, a2X, a2Y, b1X, b1Y, b2X, b2Y) {
  function between(v, min, max) {
    return min <= v && v <= max;
  }

  // Sort endpoints to avoid checking both orders
  if (a1X > a2X || (a1X === a2X && a1Y > a2Y)) {
    [a1X, a1Y, a2X, a2Y] = [a2X, a2Y, a1X, a1Y];
  }
  if (b1X > b2X || (b1X === b2X && b1Y > b2Y)) {
    [b1X, b1Y, b2X, b2Y] = [b2X, b2Y, b1X, b1Y];
  }

  return (
    between(b1X, a1X, a2X) || between(b2X, a1X, a2X) || 
    between(a1X, b1X, b2X) || between(a2X, b1X, b2X)
  ) && (
    between(b1Y, a1Y, a2Y) || between(b2Y, a1Y, a2Y) || 
    between(a1Y, b1Y, b2Y) || between(a2Y, b1Y, b2Y)
  );
}

Answer 3

Here is a working (but not optimized) solution.

• it starts from your solution Ryan
• on unambiguous cases (those where < and <= agree), return immediately
• now remain the cases where the segments are aligned:
  we are now in 1 dimension, and this eases operations;
  choose the most significant coordinate (X or Y) to finish everything in 1D
• as usual, return in easy cases
• end with the "1 vertex in common" cases

The whole thing has not been simplified, there should be room for improvement, but this may serve as a starting point (additionally, bad optimization makes easy reading).
Performance should not be that bad though, due to:

• the "common cases" returning early
• the ability to work in 1D instead of 2D for the remaining cases

… And I test every permutation of all the typologies I could think of.

function doLineSegmentsIntersect(a1X, a1Y, a2X, a2Y, b1X, b1Y, b2X, b2Y) {
  const dxA = a2X - a1X;
  const dyA = a2Y - a1Y;
  const dxB = b2X - b1X;
  const dyB = b2Y - b1Y;

  // Calculate cross product values to determine orientation
  const p0 = dyB * (b2X - a1X) - dxB * (b2Y - a1Y);
  const p1 = dyB * (b2X - a2X) - dxB * (b2Y - a2Y);
  const p2 = dyA * (a2X - b1X) - dxA * (a2Y - b1Y);
  const p3 = dyA * (a2X - b2X) - dxA * (a2Y - b2Y);

  // The segments intersect if the products of these cross products are non-positive (i.e. the segments straddle each other)
  const p01 = p0 * p1;
  const p23 = p2 * p3;
  if(p01 < 0 && p23 < 0) return true;
  if(p01 > 0 || p23 > 0) return false;
  // Now handle the remaining cases: aligned segments.
  // We only work with the most significant coordinate (we have the same slope, so the xs and ys are proportional.
  const xory = Math.abs(dxB) > Math.abs(dyB);
  const b1a1 = xory ? b1X - a1X : b1Y - a1Y;
  const b1a2 = xory ? b1X - a2X : b1Y - a2Y;
  const b2a1 = xory ? b2X - a1X : b2Y - a1Y;
  const b2a2 = xory ? b2X - a2X : b2Y - a2Y;
  const b1a = b1a1 * b1a2;
  const b2a = b2a1 * b2a2;
  if(b1a < 0 || b2a < 0) return true; // B1 or B2 is between A1 and A2.
  const sameSide = b1a1 * b2a2; // Are B1 and B2 on the same side of [A]? To get the sign, just test one vertex of each: the previous line made sure we B1 and B2 are on the same side of each A.
  if(sameSide != 0) return sameSide < 0;
  // Here we have a 0, that is, a vertex in common.
  if(b1a == 0 && b2a == 0) return true; // Same segment!
  if(b1a1 == 0) return b2a1 * (xory ? dxA : dyA) > 0; // If B1 == A1, see if B2 is in the same or opposed direction as A2.
  if(b2a1 == 0) return b1a1 * (xory ? dxA : dyA) > 0;
  if(b1a2 == 0) return b2a2 * -(xory ? dxA : dyA) > 0;
  if(b2a2 == 0) return b1a2 * -(xory ? dxA : dyA) > 0;
}

/*--- Test framework ---*/

function _t(a1X, a1Y, a2X, a2Y, b1X, b1Y, b2X, b2Y, expect, descr) {
  let res = doLineSegmentsIntersect(a1X, a1Y, a2X, a2Y, b1X, b1Y, b2X, b2Y);
  console.log((res?1:0)+(res != expect ? ' <> ' : ' == ')+(expect?1:0)+' '+descr);
}

function t(a1X, a1Y, a2X, a2Y, b1X, b1Y, b2X, b2Y, expect, descr) {
  // Study permutations of A1 and A2, of [A] and [B].
  _t(a1X, a1Y, a2X, a2Y, b1X, b1Y, b2X, b2Y, expect, descr);
  _t(a2X, a2Y, a1X, a1Y, b1X, b1Y, b2X, b2Y, expect, descr);
  _t(b1X, b1Y, b2X, b2Y, a1X, a1Y, a2X, a2Y, expect, descr);
  _t(b1X, b1Y, b2X, b2Y, a2X, a2Y, a1X, a1Y, expect, descr);
}

/*--- Tests ---*/

t(0, 0, 1, 1, 1, 0, 2, 1,  0, "Parallel");
t(0, 1, 1, 1, 0, 0, 1, 2,  1, "Secant");
t(0, 1, 1, 1, 1, 1, 2, 1,  0, "Touching on 1 vertex");
t(0, 0, 2, 2, 1, 1, 2, 2,  1, "Overlapping");
t(0, 0, 3, 3, 1, 1, 2, 2,  1, "Subpart");
t(0, 0, 2, 2, 1, 1, 2, 2,  1, "Subpart with 1 vertex");
t(0, 0, 1, 1, 1, 1, 0, 0,  1, "Identical");
t(0, 0, 1, 1, 2, 2, 3, 3,  0, "Aligned but disjoint");

Answer 4

Ok, I think these are your conditions for checking if the lines intersect

• Lines should be touching
• Lines should not share a common vertex
• Lines can be overlapping

The below JavaScript code solves your problem. I've got the code from geeksforgeeks and modified it to check if the lines share a common vertex. It is almost same as what you have got but also accounts for the colinearity of the lines.

Points notation:

• Line1 points: p1 and q1
• Line2 points: p2 and q2

class Point {
    constructor(x, y) {
        this.x = x
        this.y = y
    }

    isSameAs(p) {
        return this.x === p.x && this.y === p.y;
    }
}

// Given three collinear points p, q, r, the function checks if 
// point q lies within line segment 'pr' 
function onSegment(p, q, r) 
{
    if (q.isSameAs(p) || q.isSameAs(r)) return false;

    if (q.x <= Math.max(p.x, r.x) && q.x >= Math.min(p.x, r.x) && 
        q.y <= Math.max(p.y, r.y) && q.y >= Math.min(p.y, r.y)) 
    return true; 
    
    return false; 
} 
  
// To find orientation of ordered triplet (p, q, r). 
// The function returns following values 
// 0 --> p, q and r are collinear 
// 1 --> Clockwise 
// 2 --> Counterclockwise 
function orientation(p, q, r) 
{ 
    let val = (q.y - p.y) * (r.x - q.x) - 
            (q.x - p.x) * (r.y - q.y); 
    
    if (val == 0) return 0; // collinear 
    
    return (val > 0) ? 1: 2; // clock or counterclock wise 
}

// Check if the lines have a common vertex
function haveCommonVertex(p1, q1, p2, q2) {
    return p1.isSameAs(p2)
            || p1.isSameAs(q2)
            || q1.isSameAs(p2)
            || q1.isSameAs(q2)
}

function doLineSegementsIntersect(p1, q1, p2, q2)
{
    // Find the four orientations needed for general and 
    // special cases 
    let o1 = orientation(p1, q1, p2);
    let o2 = orientation(p1, q1, q2);
    let o3 = orientation(p2, q2, p1);
    let o4 = orientation(p2, q2, q1);

    // General case 
    if (o1 != o2 && o3 != o4 && ! haveCommonVertex(p1, q1, p2, q2))
        return true;

    // Special Cases 
    // p1, q1 and p2 are collinear and p2 lies on segment p1q1 
    if (o1 == 0 && onSegment(p1, p2, q1)) return true;
    
    // p1, q1 and q2 are collinear and q2 lies on segment p1q1 
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;
    
    // p2, q2 and p1 are collinear and p1 lies on segment p2q2 
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;
    
    // p2, q2 and q1 are collinear and q1 lies on segment p2q2 
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;

    return false; // Doesn't fall in any of the above cases 
}

// Tests
// non-touching line segments in a line
let p1 = new Point(1, 1),
    q1 = new Point(2, 2),
    p2 = new Point(3, 3),
    q2 = new Point(4, 4);

console.log('non-touching line segments in a line: ' + doLineSegementsIntersect(p1, q1, p2, q2)); // false

// line segments with common vertex
p1 = new Point(1, 1),
q1 = new Point(2, 2),
p2 = new Point(2, 2),
q2 = new Point(1, 3);

console.log('line segments with common vertex: ' + doLineSegementsIntersect(p1, q1, p2, q2)); // false

// line segments with common vertex in a line
p1 = new Point(1, 1),
q1 = new Point(2, 2),
p2 = new Point(2, 2),
q2 = new Point(3, 3);

console.log('line segments with common vertex in a line: ' + doLineSegementsIntersect(p1, q1, p2, q2)); // false

// overlapping line segments
p1 = new Point(1, 1),
q1 = new Point(3, 3),
p2 = new Point(1, 1),
q2 = new Point(2, 2);

console.log('overlapping line segments: ' + doLineSegementsIntersect(p1, q1, p2, q2)); // true

// overlapping line segments
p1 = new Point(1, 1),
q1 = new Point(3, 3),
p2 = new Point(2, 2),
q2 = new Point(4, 4);

console.log('overlapping line segments: ' + doLineSegementsIntersect(p1, q1, p2, q2)); // true

// general condition: line segments intersecting
p1 = new Point(1, 1),
q1 = new Point(3, 3),
p2 = new Point(1, 3),
q2 = new Point(3, 1);

console.log('general condition: line segments intersecting: ' + doLineSegementsIntersect(p1, q1, p2, q2)); // true