整個主題仰賴一個問題
歡迎來到演算法設計階梯上的幾何篇。這一階接下來你會建造凸包、學習掃描線範式，並認識數論演算法——但幾乎所有的幾何工作都仰賴一個小到近乎可笑的操作。給定平面上三個點 A、B、C，當你從 A 走到 B、再朝 C 轉時，你是左轉、右轉，還是繼續直走？這就是方向測試，它是幾何上等同於「比較兩個數」的角色：微小、精確、無所不在。葛立恆掃描法、線段相交、點是否在多邊形內、以及禮品包裝凸包，全都歸結為一遍又一遍地問這個問題。
為什麼非要一個「左／右／直」的基元，而不乾脆算出 AB 與 AC 的斜率再比較？因為斜率對垂直線會爆掉（除以零）、會隱藏正負號資訊，而且偏偏在你最不想要的地方引入浮點除法。方向測試只用加法與乘法構成的單一帶號量來回答「轉向」的問題——沒有除法、沒有開根號、沒有角度。保持這份簡單不是偷懶；如我們將看到的，正是它讓我們在輸入座標為整數時能以精確的整數運算跑完整件事，而這份精確性，正是「能正常運作的凸包演算法」與「一遇到平手就崩潰的演算法」之間的分水嶺。
外積，以及為何它的正負號就是答案
公式來了，接著是讓它變得顯而易見的那張圖。構造從 A 出發的兩個向量：向量 AB = (B - A) 與向量 AC = (C - A)。它們的二維外積是這個單一數字：cross = (Bx - Ax)(Cy - Ay) - (By - Ay)(Cx - Ax)。它的正負號就是方向：正表示 A -> B -> C 形成左轉（逆時針），負表示右轉（順時針），恰好為零則表示三點共線——你直走了。一個充滿減法的算式、一次正負號檢查，「轉向」的問題就回答完畢。
為什麼那個特定的乘積組合能編碼出轉向？因為外積等於三角形 ABC 的帶號面積的兩倍。帶號面積在頂點以逆時針列出時為正、順時針時為負——這就是它的定義——所以它的正負號與轉向方向，是同一個事實穿著兩套衣服。而當三點落在同一條直線上時，三角形退化、面積為零，這恰好就是共線情況給出 cross = 0。所以方向測試不是什麼魔術；它讀的就是一個你高中就能算出的面積的正負號。明白這一點，才讓這個測試是可信賴的，而非死背的。
orient(A, B, C):
cross = (Bx - Ax)*(Cy - Ay) - (By - Ay)*(Cx - Ax)
if cross > 0: return LEFT # counterclockwise, signed area > 0
if cross < 0: return RIGHT # clockwise, signed area < 0
return COLLINEAR # signed area = 0一個小小的追蹤，以及那個毀掉職業生涯的陷阱
我們跑一次看看。取 A = (0,0)、B = (4,0)、C = (2,3)。則 cross = (4 - 0)(3 - 0) - (0 - 0)(2 - 0) = 12 - 0 = 12 > 0，所以從 AB 朝 C 的轉向是「左」——C 位於通過 A 與 B 的直線上方，與圖相符。把 C 下移到 (2,-3)，同樣的算術給出 -12，是「右」轉。把 C 放到直線上的 (2,0)，cross = 0，「共線」。三次計算、三個答案，全來自同一條公式——而且請注意我們從未做除法或取角度，所以在RAM 模型下，整數輸入時這每一次都是精確的整數比較。
還有第二個、更安靜的陷阱：溢位。座標的整數值很大時，cross 內部的乘積可能超出 32 位元整數，即使輸入本身綽綽有餘地放得下。若座標可達約 10^9，兩個座標差的乘積可達約 10^18，這會讓 32 位元溢位，但仍放得進 64 位元帶號整數。修法既無趣又必要——用 64 位元（或更寬）的整數來做這個運算。這是一個具體的提醒：漸進成本隱藏了常數，但它也隱藏了對機器字長的假設；抽象的「O(1) 方向測試」唯有在你的數字真的放得進一個機器字時，才真是 O(1)。
從方向測試到「這兩條線段相交嗎？」
現在來收成。我們想要一個線段相交測試：給定線段 P1-P2 與 P3-P4，它們是否至少共享一個點？一個誘人的做法是求出兩條無限長的直線、解出它們的交點、再檢查交點落在兩線段上——但那條路要做除法、要碰浮點、還得為平行線設特例。方向測試給出一個更乾淨、無除法的想法。兩線段相交若且唯若各自跨越通過對方的直線：P1 與 P2 分別位於直線 P3-P4 的兩側，且同時 P3 與 P4 分別位於直線 P1-P2 的兩側。「位於兩側」恰恰就是兩個正負號相異的方向測試。
- 計算四個方向：d1 = orient(P3, P4, P1)、d2 = orient(P3, P4, P2)、d3 = orient(P1, P2, P3)、d4 = orient(P1, P2, P4)。每個都告訴你「另一線段的一個端點」落在「這一線段所在直線」的哪一側。
- 正規相交情況：若 d1 與 d2 嚴格異號，且 d3 與 d4 嚴格異號，則兩線段在單一內部點相交——回傳真。兩對端點各自跨越對方，正是 X 形相交的幾何條件。
- 共線／接觸情況：若任一 di 為零，表示某端點落在對方那條直線上。此時再檢查該端點是否真的落在對方線段的邊界框（其 x 與 y 範圍）之內。若是，它們接觸或重疊——回傳真。這能捕捉到「擦過某線段的端點」以及「單靠跨越測試會漏掉的共線重疊」。
- 否則回傳假。若兩邊都不跨越、且沒有端點落在對方線段上，則兩線段彼此分離。
為什麼跨越條件是正確的？線段 P1-P2 跨越通過 P3-P4 的整條直線，恰好發生在它的兩個端點分居該直線兩側時——這就是介值定理的想法：當你從 P1 滑到 P2，到直線的帶號距離會變號，所以它必在線段上某處穿過零。對兩條線段都要求這一點，就把交點同時釘在兩條線段上，而不只是釘在兩條無限長直線上。我們之所以仍需要那個共線分支，是因為「分居兩側」是個嚴格條件；當某個方向為零時，該點是落在直線上、而非嚴格地越過它，而那些邊界上的接觸是真實的交點，嚴格測試卻悄悄地把它們丟掉了。
誠實的限制，以及這個基元的去向
把這個測試「給了什麼、沒給什麼」說清楚。它回答的是決定性問題——它們相交與否，是或否——每一對花 O(1) 時間、不做除法、在整數輸入下完全精確。它本身並不交給你交點；算出交點確實需要解直線方程式（並重新引入除法與浮點，所以只在你已確知存在交點後才做）。而對 n 條線段，暴力的「測試每一對」做法是 O(n^2) 次呼叫——n 小時無妨，但對大量線段，這一階後面的掃描線方法能在 O((n + k) log n) 時間內回報所有交點，其中 k 是找到的交點數，靠的是巧妙地避開大多數的成對測試。
關於成本的最後一次誠實檢查。我們一直把方向測試叫做「O(1)」，而在字長固定的RAM 模型上它確實是。但這假設了每次乘法是單位成本的一步——在乘積放得進一個機器字時為真，正如我們用 64 位元運算所安排的。若座標無上界地成長，數字本身就會變大、算術也就不再是常數時間，所以這個抽象像每個抽象一樣有它的邊界。對於一般問題的整數範圍，O(1) 的說法完全正確；只要記得它是關於一個模型的主張、而非自然律，而正是這個假設，讓上面整座幾何建築得以立在一個常數時間的地基上。