Find intersection point between a line and a rectangle

Question

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?

Does this answer your question? [intersection between a line and square](https://stackoverflow.com/questions/58055629/intersection-between-a-line-and-square) — zoldxk, Jun 05 '22 at 23:58
nope, that only works with squares(where width equals height). Also is written in Java(language that I haven't learned) and I need it in JS. Thank you anyways — RusianNotRussian, Jun 06 '22 at 01:33
@RusianNotRussian the accepted answer on the linked post (1) is **not** Java-specific and (2) works for rectangles of any dimensions as the algorithm is independent of the corner coordinates `(x1,y1) (x2,y2)` — meowgoesthedog, Jun 06 '22 at 13:38

score 0 · Accepted Answer · answered Jun 06 '22 at 05:15

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

Find intersection point between a line and a rectangle

1 Answers1