How can I find out if two lines overlap - or don't overlap?

How would a function look likes that takes two objects that represent lines and returns whether they overlap or not? E.g.

 function Overlap (line1, line2) {
     // code here
 }

I’ve been trying for hours to figure this out, but I can’t get it right.

Perhaps this line intersection article will help, from which we can derive the code.

Hi there deekeilholz,

and a warm welcome to these forums. :sunglasses:

Using the formula from the link that
@Paul_Wilkins gave, does this help…

<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,height=device-height,initial-scale=1">
<title>untitled document</title>
<!--<link rel="stylesheet" href="screen.css" media="screen">-->
</head>
<body> 
<script>
(function() {
   'use strict';
/* line one */
   var x1=1;
   var x2=6;
   var y1=4;
   var y2=12;
/* line two */
   var x3=-7;
   var x4=18;
   var y3=5;
   var y4=25;
   var intersectX=
   (((x1*y2-y1*x2)*(x3-x4)-(x1-x2)*(x3*y4-y3*x4))/
   ((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4)));
   var intersectY=
   (((x1*y2-y1*x2)*(y3-y4)-(y1-y2)*(x3*y4-y3*x4))/
   ((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4)));

if((x1-x2)*(y3-y4)-(y1-y2)*(x3-x4)===0) {
   console.log('the lines are parallel');
 }
else {
   console.log('x='+intersectX);
   console.log('y='+intersectY);
 }
}());
</script>
</body>
</html>

coothead

Awesome. That’s really helpful. Thanks.

 
 
    No problem, you’re very welcome. :sunglasses:

coothead

I expanded this code to where matrix manipulation is used, helping us to better understand what is going on there.

<div id="result"></div>
function lineIntersect(line1, line2) {
    // Based on intersection formula from https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection
    function determinant(arr) {
        return arr[0] * arr[3] - arr[1] * arr[2];
    }
    function intersect(rows) {
        var numerator = determinant([
            determinant([rows[0][0], rows[0][1], rows[1][0], rows[1][1]]),
            determinant([rows[0][2], rows[0][3], rows[1][2], rows[1][3]]),
            determinant([rows[2][0], rows[2][1], rows[3][0], rows[3][1]]),
            determinant([rows[2][2], rows[2][3], rows[3][2], rows[3][3]])
        ]);
        var denominator = determinant([
            determinant([rows[0][0], 1, rows[1][0], 1]),
            determinant([rows[0][1], 1, rows[1][1], 1]),
            determinant([rows[2][0], 1, rows[3][0], 1]),
            determinant([rows[2][1], 1, rows[3][1], 1])
        ]);
        return numerator / denominator;
    }
    function colCloneAppend(index) {
        return function (row) {
            var arr = row.slice(0);
            arr.splice(arr.length, undefined, row[index]);
            return arr;
        };
    }
    function colAppendValue(value) {
        return function (row) {
            var arr = row.slice(0);
            arr.splice(arr.length, undefined, value);
            return arr;
        };
    }
    var rows = [
        [line1.start.x, line1.start.y],
        [line1.end.x, line1.end.y],
        [line2.start.x, line2.start.y],
        [line2.end.x, line2.end.y]
    ];
    var px = intersect(
        rows.map(colCloneAppend(0)).map(colAppendValue(1)) // [3, 5] becomes [3, 5, 3, 1]
    );
    var py = intersect(
        rows.map(colCloneAppend(1)).map(colAppendValue(1)) // [3, 5] becomes [3, 5, 5, 1]
    );
    var intersectInfo = {
        intersect: false,
        point: undefined,
        error: []
    };
    function boundsCheck(p1, middle, p2) {
        if (p1 <= p2) {
            return p1 <= middle && middle <= p2;
        } else {
            return p2 <= middle && middle <= p1;
        }
    }
    if (isNaN(px) || isNaN(py)) {
        intersectInfo.error.push("is not a number");
    }
    if (!boundsCheck(rows[0][0], px, rows[1][0])) {
        intersectInfo.error.push("px is not between x1 and x2");
    }
    if (!boundsCheck(rows[0][1], py, rows[1][1])) {
        intersectInfo.error.push("py is not between y1 and y2");
    }
    if (!boundsCheck(rows[2][0], px, rows[3][0])) {
        intersectInfo.error.push("py is not between y1 and y2");
    }
    if (!boundsCheck(rows[2][1], py, rows[3][1])) {
        intersectInfo.error.push("py is not between y3 and y4");
    }
    intersectInfo.intersect = true;
    intersectInfo.point = {x: px, y: py};
    return intersectInfo;
}

var line1 = {start: {x: 1, y: 6}, end: {x: 4, y: 2}};
var line2 = {start: {x: -7, y: 18}, end: {x: 5, y: -25}};
var intersection = lineIntersect(line1, line2);

var result = document.querySelector("#result");
var output = "The lines " +
        "(" + line1.start.x + "," + line1.start.y + ")-(" + line1.end.x + "," + line1.end.y + ") and " +
        "(" + line2.start.x + "," + line2.start.y + ")-(" + line2.end.x + "," + line2.end.y + ")";
if (intersection.intersect) {
    output += " at (" + intersection.point.x + "," + intersection.point.y + ")";
} else {
    output += " do not intersect";
}
result.innerHTML = output;

This topic was automatically closed 91 days after the last reply. New replies are no longer allowed.