2013-01-10 73 views
3

可能重複:
How do you detect where two line segments intersect?給定兩個點和兩個向量,找到交點

考慮兩點ab加上兩個向量vu我想找到第三點c,這是以下列方式的交點:

vector2 intersection(vector2 a, vector2 v, vector2 b, vector2 u) 
{ 
    float r, s; 

    a + r * v = b + s * u; 
    r * v - s * u = b - a 

    r * v.x - s * u.x = b.x - a.x 
    r * v.y - s * u.y = b.y - a.y 
} 

除了使用高斯消元來解決這個系統還有別的方法嗎?或者,這是最好的(或至少是可以接受的)方式來處理這個問題?

EDIT: 定義的vector2

typedef union vector2 
{ 
    float v[2]; 
    struct { float x, y; }; 
} vector2; 

abvector2類型的,因爲一個點和向量之間的唯一區別是在它是由仿射變換變換的方式。

+1

'vector2'是如何定義的?爲什麼* points * a和b也是'vector2'類型? –

+0

我的解釋如下。但不管。爲什麼vector不僅僅是一個結構?爲什麼你需要工會和「陣列」? –

+0

這個問題已被Gareth Rees,Paul R,Mark Dickinson和0xbadf00d標記爲重複,因爲「此問題已被詢問並且已經有答案。」。 **但是**這個問題在撰寫本文時沒有被接受的答案。我不認爲應該將問題標記爲重複,除非所引用的問題具有可接受的答案。 – user316117

回答

1

對我來說看起來像一個任務問題。這是可以幫助你編寫代碼的邏輯。

讓我們稱第一個雷爲R0。上R0一個點的
軌跡定義爲P

P = P0 + alpha x V0 

對於第二射線R1

P = P1 + beta x V1 

由於它們應該相交:

P0 + alpha x V0 = P1 + beta x V1 

alphabeta是未知我們有兩個方程x任何y

解決未知問題並找回交點。

P0.x + alpha * V0.x = P1.x + beta * V1.x 
P0.y + alpha * V0.y = P1.y + beta * V1.y 

解決alphabeta

如果對alphabeta都有真正的正解,則射線會相交。
如果alphabeta存在真實的但至少有一個負面解決方案,則擴展光線會相交。

1

這是簡單的數學。

但是,首先,檢查你是否有交集。如果兩個向量是平行的,你將無法解決:

// Edit this line to protect from division by 0 
if (Vy == 0 && Uy == 0) || ((Vy != 0 && Uy != 0 && (Vx/Vy == Ux/Uy)) // => Fail. 

然後(我想表明的計算因爲他們長,但):

R = (AxUy - AyUx + ByUx - BxUy)/(VyUx - VxUy) 
S = (Ax - Bx + RVx)/Ux 

希望有所幫助你。

+0

如果將[(a.x -b.x + r * v.x)/ u')分開,結果如何?假設'u'是一個向量,'(a.x-b.x + r * v.x)'是一個標量? – 0xbadf00d

+0

@ 0xbadf00d你更正了,這是一個錯字。我的意思是Ux ... –

+0

如果* Ux = 0 *會怎麼樣?例如:* v1 =(0,1)*,* v2 =(2,0)*和* p1 =( - 4,2)*,* p2 =(3,5)*? –