javascriptmathgeometrylineintersection

How to efficiently check if two line segments intersect?

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:

The problem with < is:

Solution 

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