帶邊界框的二維直線交點

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。