[2D Geomtry] 二維線段交點

在本篇 entry 我們談一談二維線段交點求解方法
本人認為，最後討論的 "三角形面積方法" 的解相當優美

---

直線方程組方法

中學時期，我們都學過用聯立方程組求 線 / 線交點：

A x + B y = C
D x + E y = F

可這個方法缺點是
用代入法 (substitution) 或消元法  (elimination) 求出的一般解
在 x系數 = 0 或 y系數 = 0 的情況需要特別分開處理

我們亦不能單從 solution
簡單判斷交點 Q 是否在線段 AB 或 CD 之內

---

向量方法

這是在 year 1 暑假 ACM training 時學會的
感覺相當強大、漂亮

將兩條線段表示成：

P₁ = A + s AB -------- (1)
P₂ = C + t CD -------- (2)

其中 s, t 分別是 線段AB,CD 的參數


要解 線/線 (或線段/線段) 交點，將 式(1)、(2) 取等就好了：

A + s AB = C + t CD -------- (3)

讓式(3) 對 AB 取叉積 (cross product)：

A^AB = C^AB + t (CD^AB) -------- (4)

移項可解出 t：

t = (CA^AB) / (CD^AB) -------- (5)

類似地，我們可以解出 s：
(讓 式 (3) 對 CD 取叉積，或利用對式性)

s = (AC^CD) / (AB^CD) -------- (6)

---

向量方法的公式 已經在 training / contest 推過很多次了
雖然推導時間只 ~1分鐘，可是每次這樣重覆算一次也挺麻煩...
而把式子放在頁數限制=25頁 的「武器庫」又似乎有點浪費

有時候我會想，是否存在更直觀的推導過程？

終於，在近期某次 codeforces 比賽
有意無意看到 rng_58 的一段 code
我並沒有仔細閱讀
但發現其中有調用 "Area" 函數 (計算三角形面積)

後來式子突然在腦海中導出來了...

---

三角形面積方法

留意到 AQC, BQC 是等高三角形，是以我們有：

Area(AQC)：Area(BQC) = AQ：AB -------- (I)

AQD, BQD 也是：

Area(AQD)：Area(BQD) = AQ：AB -------- (II)

(I) + (II)：

Area(ACD)：Area(BCD) = AQ：AB -------- (III)

由 (III)，可以解出 s：

s = Area(ACD) / ( Area(ACD) + Area(BCD) ) -------- (IV)
其中 Q = A + s AB

類似地，我們亦可以解出 t
其中 Q = C + t CD

DONE!!

---

好了... 三角形面積方法 及 向量方法
其實在做同樣的事情 (好似係)

原因： Area(ABC) = || AB^AC || / 2

---

結語

• 向量方法跟三角形方法原理相通
  原因在於叉積的幾何意義，本身就是三角形的 signed area (的兩倍)
• 利用解出的參數，我們可以輕鬆判斷交點是否在線段之內
  (線段之間有交點 ⇔ s ∈ [0,1]   AND   t ∈ [0,1])
  從宜，我們便能因應情況求出 線段/線、線/線段、線/線 的交點
  或者判斷它們是否存在
• 用叉積計算三角形面積時
  注意計算順序會影響正負號的差異
• 在知道向量方法之前，那時候做過一兩條幾何題目
  發現對系數數值分情況考慮... 非常麻煩
  所以對向量方法感覺就是... 這方法挺厲害，可是推導公式還是有一點點麻煩
  在最近導出如此直觀的三角面積方法... 心情就更加激動
  未知讀者會否有類似感覺...  哈哈