[2D Geometry] 內/外 兩圓公切線 的對應

2010-08-23 2am 更新：

1. 兩種 圓/圓公切線 (Common Tangent)，正名為
   a) 「外公切線」(Common External Tangent)， 及
   b) 「內公切線」(Common Internal Tangent)
   下面討論一律略去「公」 ("Common") 一字
   ....嗯... 外公切線... 以下簡稱為「外切線」及「內切線」
2. 兩圓切線共有 5種情況 ...
   我正在驗證本 Entry 所提供的 Implementation 能否覆蓋全部情況
   ──別被嚇到... 本人直觀地認為本 Entry 所討論的 Implementation
   已能覆蓋所有情況，只是仍有待證實

---

昨晚隨便在 Ural Timus OJ 上選了一道幾何 ── Ural 1340 Cucaracha
想出了某 case 的算法後
發現自己不懂怎樣計算某一角度
只懂得 BSearch... 然後又發現 BSearch 不行...

再細心一想
才發現這個問題其實可以 reduce 至「點到圓切線」...

---

那我就想起... 原來我還沒有一份「點到圓切線」的 Code Template...

在這次之前不知道推導過這公式多少次...
雖然每次都能推出，但推導過程會花費相當長的時間
所以實在太有必要寫一份武器（要不，就把公式推導到爐火純青的熟練程度）

上回在 這篇Entry 談過
「點到圓切線」是「圓到圓切線」的特例 ── 其中一圓半徑=0

而「圓到圓切線」在一般情況下共有 4條

 

分 「外切線」(External Tangent) 及 「內切線」(Internal Tangent) 兩種

──註：上行此兩項述語這是本文的定義，自行定義的原因一是為方便以下的說明
二是因為在 Google 暫時搜不出相關的述語...

而每種切線各有 2條

那 code template... 就是寫！

寫呀寫的...
突然有一個驚喜的新發現（潮左勿 WoW）：

「內切線」原來是「外切線」的特例！

PKU 2416 Return of the Jedi

題意：

在平面上，給定 N (≤ 10) 個圓（任何兩圓不相交／觸碰）
及 A、B 兩點

求最短 A 到 B 路徑（不得進入任何圓形內，但可以觸碰）的長度

---

應用知識：

此題基本上是一道 2D Geometry Exercise
只是在 公式推導 及 處理 Boundary Cases 時要比較小心...

1. 圓到圓切線（全４種）
2. 點到圓切線
   
3. 判斷 線段／圓 交點
   
4. 最短路算法

2. 的計算可透過 1. 完成
── 把 點 看為 半徑 = 0 的圓

---

PKU 3703 Intuition of Escape

題意：
二維場景內
給定一個 半徑 = R，位置 = (0,0) 的圓
及 N 個多邊形障礙物
問，是否在存一個移動方向，使得當圓形以直線前進時
不會觸碰這些障礙物

分析：
算法大約都是枚舉（離散的）移動方向/角度 - angle[M]
然後逐一判斷是否可行

有關「觸碰」的限制
雖然可以 ± Epsilon 處理
但這會令代碼變得噁心