Created
January 2, 2013 00:17
-
-
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 …
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // 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