Find intersection point between a line and a rectangle-CodePudding

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?

CodePudding user response：

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]
  ];
}