I have a line with a point A(starting point) and a point B(finishing point):
a = {x: x, y: y}
b = {x: x, y: y}
line = (a[y] - b[y]) / (a[x] - b[x])
and a rectangle with the center(x,y), width and height:
rectangle = {x: x, y: y, w: w, h: h}
how can I find the intersection between both?
Writing line equation in parametric form:
x = ax + t * (bx - ax)
y = ay + t * (by - ay)
we can to solve some equation systems for line coordinates and rectangle edges like this
rectangle.left = ax + t * (bx - ax)
y_at_left_edge = ay + t * (by - ay)
and check whether y_at_left_edge lies in valid range (top..bottom).
One of the fastest algoritms exploiting such calculation of intersections is Liang-Barsky algorithm, (Wiki page).
JS implementation from here, (another implementation)
/**
*Liang-Barsky function by Daniel White
*
* @link http://www.skytopia.com/project/articles/compsci/clipping.html
*
* @param {number} x0
* @param {number} y0
* @param {number} x1
* @param {number} y1
* @param {array<number>} bbox
* @return {array<array<number>>|null}
*/
function liangBarsky (x0, y0, x1, y1, bbox) {
var [xmin, xmax, ymin, ymax] = bbox;
var t0 = 0, t1 = 1;
var dx = x1 - x0, dy = y1 - y0;
var p, q, r;
for(var edge = 0; edge < 4; edge++) { // Traverse through left, right, bottom, top edges.
if (edge === 0) { p = -dx; q = -(xmin - x0); }
if (edge === 1) { p = dx; q = (xmax - x0); }
if (edge === 2) { p = -dy; q = -(ymin - y0); }
if (edge === 3) { p = dy; q = (ymax - y0); }
r = q / p;
if (p === 0 && q < 0) return null; // Don't draw line at all. (parallel line outside)
if(p < 0) {
if (r > t1) return null; // Don't draw line at all.
else if (r > t0) t0 = r; // Line is clipped!
} else if (p > 0) {
if(r < t0) return null; // Don't draw line at all.
else if (r < t1) t1 = r; // Line is clipped!
}
}
return [
[x0 + t0 * dx, y0 + t0 * dy],
[x0 + t1 * dx, y0 + t1 * dy]
];
}