Skip to content

Instantly share code, notes, and snippets.

@sunmockyang
Created January 2, 2013 00:17
Show Gist options
  • Select an option

  • Save sunmockyang/4431210 to your computer and use it in GitHub Desktop.

Select an option

Save sunmockyang/4431210 to your computer and use it in GitHub Desktop.
This set of functions has been developed as a thought of detecting intersection between bounding boxes based on whether a line segment between two corners has been intersected by another line segment. It will take two line segments, and return the point of intersection or return null if the line segments do not intersect. This code has not been …
// Two lines defined by entering 2 points
var line1 = new line([1, 1], [5, 5]); // Positive slope
var line2 = new line([1, 5], [5, 1]); // Negative slope
var line3 = new line([2, 6], [6, 2]); // Parallel to line 2 but line3 != line2
var line4 = new line([3.5, 0], [3.5, 5]); // Vertical line
console.log(line1);
console.log(line2);
console.log("Calculate: ")
console.log(calcIntersection(line1, line2)); // returns (3,3)
console.log(calcIntersection(line2, line3)); // returns null due to parallel lines
console.log(calcIntersection(line1, line4)); // returns (3.5, 3.5)
// Generate a line object containing two points
function line(_p1, _p2) {
if (_p1.x > _p2.x) { // make sure that the line points are from left to right
var temp = _p2;
_p2 = _p1;
_p1 = temp;
}
return {
p1: { x: _p1[0], y: _p1[1] },
p2: { x: _p2[0], y: _p2[1] }
};
}
// Calculate slope based on two points
function calcSlope(p1, p2) {
if (p1.x === p2.x) // If the x of both points are equal, slope is infinite
return null;
return (p1.y - p2.y) / (p1.x - p2.x);
}
// Calculate y-intercept of a line based on a point and slope of a line
function calcYIntercept(m, p1) {
return p1.y - m * p1.x;
}
// Calculate if point is in the domain and range of a line segment
function isBetween(point, line) {
if (point.x >= line.p1.x && point.x <= line.p2.x) { // Point is in domain of the line segment
// Check if point is within range of the line segment (ternary statements are present because of the possibility that of a negative slope)
if (point.y >= ((line.p1.y < line.p2.y) ? line.p1.y : line.p2.y) && point.y <= ((line.p1.y > line.p2.y) ? line.p1.y : line.p2.y)) {
return true;
}
}
return false;
}
// Calculate the intercept point based on two lines. Returns null if there is no intersection
function calcIntersection(line1, line2) {
// Slope and y-intercept of lines
var m1, b1, m2, b2;
// Container for return point
var point = {
x: null,
y: null
}
// Calculate the slope of both lines
m1 = calcSlope(line1.p1, line1.p2);
m2 = calcSlope(line2.p1, line2.p2);
// If a slope is infinite
if (m1 === null || m2 === null) {
point.x = (m1 === null) ? line1.p1.x : line2.p1.x; // x is equal to the x of whichever line segment has infinite slope
// y is calculated by using x, slope, and y-intercept
point.y = (m1 !== null) ? m1 * point.x + calcYIntercept(m1, line1.p1) : m2 * point.x + calcYIntercept(m2, line2.p1);
}
else {
// Calculate y-intercept based on the slope and a point on the line
b1 = calcYIntercept(m1, line1.p1);
b2 = calcYIntercept(m2, line2.p1);
// If the slope of the line segments equal and the y-intercepts are the same, they will never intersect
if (m1 === m2 && b1 !== b2) {
return null;
}
// Calculate intersection point based on slopes and y-intercepts
point.x = (b2 - b1) / (m1 - m2);
point.y = m1 * point.x + b1;
}
// Make sure that the intersection point is within the line segments
if (isBetween(point, line1) && isBetween(point, line2))
return point;
else
return null;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment