# 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.

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

<!DOCTYPE html>
<html lang="en">
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,height=device-height,initial-scale=1">
<title>untitled document</title>
<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>

No problem, you’re very welcome.

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.