How can I efficiently check segment intersections in JavaScript with custom endpoint and overlap rules?

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

JAVASCRIPTCopied
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  

Run code snippetHide resultsExpand snippet

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.

JAVASCRIPTCopied
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");

Run code snippetHide resultsExpand snippet