calculating the point of intersection of two lines
For line segment-line segment intersections, use Paul Bourke's solution:
// line intercept math by Paul Bourke http://paulbourke.net/geometry/pointlineplane/
// Determine the intersection point of two line segments
// Return FALSE if the lines don't intersect
function intersect(x1, y1, x2, y2, x3, y3, x4, y4) {
// Check if none of the lines are of length 0
if ((x1 === x2 && y1 === y2) || (x3 === x4 && y3 === y4)) {
return false
}
denominator = ((y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1))
// Lines are parallel
if (denominator === 0) {
return false
}
let ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denominator
let ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denominator
// is the intersection along the segments
if (ua < 0 || ua > 1 || ub < 0 || ub > 1) {
return false
}
// Return a object with the x and y coordinates of the intersection
let x = x1 + ua * (x2 - x1)
let y = y1 + ua * (y2 - y1)
return {x, y}
}
For infinite line intersections, use Justin C. Round's algorithm:
function checkLineIntersection(line1StartX, line1StartY, line1EndX, line1EndY, line2StartX, line2StartY, line2EndX, line2EndY) {
// if the lines intersect, the result contains the x and y of the intersection (treating the lines as infinite) and booleans for whether line segment 1 or line segment 2 contain the point
var denominator, a, b, numerator1, numerator2, result = {
x: null,
y: null,
onLine1: false,
onLine2: false
};
denominator = ((line2EndY - line2StartY) * (line1EndX - line1StartX)) - ((line2EndX - line2StartX) * (line1EndY - line1StartY));
if (denominator == 0) {
return result;
}
a = line1StartY - line2StartY;
b = line1StartX - line2StartX;
numerator1 = ((line2EndX - line2StartX) * a) - ((line2EndY - line2StartY) * b);
numerator2 = ((line1EndX - line1StartX) * a) - ((line1EndY - line1StartY) * b);
a = numerator1 / denominator;
b = numerator2 / denominator;
// if we cast these lines infinitely in both directions, they intersect here:
result.x = line1StartX + (a * (line1EndX - line1StartX));
result.y = line1StartY + (a * (line1EndY - line1StartY));
// if line1 is a segment and line2 is infinite, they intersect if:
if (a > 0 && a < 1) {
result.onLine1 = true;
}
// if line2 is a segment and line1 is infinite, they intersect if:
if (b > 0 && b < 1) {
result.onLine2 = true;
}
// if line1 and line2 are segments, they intersect if both of the above are true
return result;
};
I found a great solution by Paul Bourke. Here it is, implemented in JavaScript:
function line_intersect(x1, y1, x2, y2, x3, y3, x4, y4)
{
var ua, ub, denom = (y4 - y3)*(x2 - x1) - (x4 - x3)*(y2 - y1);
if (denom == 0) {
return null;
}
ua = ((x4 - x3)*(y1 - y3) - (y4 - y3)*(x1 - x3))/denom;
ub = ((x2 - x1)*(y1 - y3) - (y2 - y1)*(x1 - x3))/denom;
return {
x: x1 + ua * (x2 - x1),
y: y1 + ua * (y2 - y1),
seg1: ua >= 0 && ua <= 1,
seg2: ub >= 0 && ub <= 1
};
}