Точка пересечения 2D-линии с ограничительной рамкой

Question

Каким был бы эффективный алгоритм для вычисления точки пересечения линии, начинающейся с (x, y), с углом θ, и ограничивающего прямоугольника с ко-ординатами (от 0,0 до w, h)?Предполагая, что начало строки находится внутри рамки.

В базовом искусстве ascii (для линии, начинающейся с 2,6 и θ приблизительно 9π / 8):

 h---------------...h,w
 .               ...
 .               ... 
 .               ...
 7               ...
 6   x           ...
 5  /            ...
 4 /             ...
 3/              ...
 2               ...
/1               ...
 0 1 2 3 4 5 6 7 ... w

Все переменные, кроме θ, являются целыми числами.

Answer 1

Предположим, что мы параметризовали линию переменной t, т.е. каждая точка на линии может быть записана как

[x(t),y(t)] = [x,y] + t * [dx,dy]

с константами

dx = cos(theta)
dy = sin(theta)

Затем вы можете сначала рассчитать разрез по вертикальным границам:

if dx<0 then        // line going to the left -> intersect with x==0
  t1 = -x/dx
  x1 = 0
  y1 = y + t1*dy
else if dx>0 then   // line going to the right -> intersect with x==w
  t1 = (w-x)/dx
  x1 = w
  y1 = y + t1*dy
else                // line going straight up or down -> no intersection possible
  t1 = infinity
end

, где t1 - расстояние до точки пересечения, а [x1,y1] - сама точка. Во-вторых, вы делаете то же самое для верхней и нижней границ:

if dy<0 then        // line going downwards -> intersect with y==0
  t2 = -y/dy
  x2 = x + t2*dx
  y2 = 0
else if dy>0 then   // line going upwards -> intersect with y==h
  t2 = (h-y)/dy
  x2 = x + t2*dx
  y2 = h
else
  t2 = infinity
end

Теперь вам просто нужно выбрать точку с меньшим расстоянием от вашего источника [x,y].

if t1 < t2 then
  xb = x1
  yb = y1
else
  xb = x2
  yb = y2
end

Обратите внимание, что этот алгоритм работает, только если начальная точка находится внутри ограничительной рамки, то есть 0 <= x <= w и 0 <= y <= h.