計算幾何簡介

本篇這學期暫不整理.

  1. 計算幾何 (computational geometry) 是演算法和解析幾何的混合體. 和一般演算法最大的不同在於 cg 必須面對浮點運算精確度有限的問題. 此外, cg 所要解決的問題, 經常是肉眼一看就知道答案, 但是純粹用數字表現出來 (這樣電腦才會算) 卻又不是那麼簡單.
  2. 範例問題: convex hull -- 給定平面上的一堆點, 求一個最小的凸多邊形把所有點包含在裡面.
  3. 觀察: 其實也就是要從這一堆點當中找出將來構成 convex hull 邊界的點有那些.
  4. Convex hull 演算法一: Jarvis's March (gift wrapping)
    1. 找出最下方的點 p0. 它一定在 convex hull 的邊界上.
    2. 找出 p1, 使 p0 與 p1 的連線與正 x 軸的夾角 (有向角) 最小.
    3. 找出 p2, 使 p2 與 p1 的連線與正 x 軸的夾角最小.
    4. ... 直到回到 p0 為止.
  5. Convex hull 演算法二: Graham's scan
    1. 找出最下方的點 p0. 它一定在 convex hull 的邊界上.
    2. 以「p0 到各點的射線與 x 軸的夾角」作為比較的依據, 對所有的點排序.
    3. 依序如下檢查 p1, p2,....
    4. 檢查 pi 時要做的事情: 看看 stack 上第二高的元素, stack 上最頂端的元素, 與 pi 三點兩射線是左轉還是右轉. 如果是右轉, 就 pop, 並重複此步驟.
    5. (現在可以確定是左轉了) push pi.
    6. 檢查下一個 pi.
  6. 許多計算幾何演算法都需要用到的基本運算:
    1. 比較兩條共同起點的射線, 誰在誰的順/逆時針方向. (本來可以呼叫 atan2 直接把各射線與 x 軸的夾角值算出來再比較, 但計算 atan2 太耗時.) 方法: 判斷 x1*y2-x2*y1 的正負.
    2. 三點兩射線是左轉還是右轉: 可化簡為上題.
    3. 兩條線段是否相交.
  7. 線段交叉問題: 輸入許多線段, 詢問是否有線段交叉.
    1. 用途: 判斷一個多邊形是否為 simple polygon (邊不交叉); 把平面分割成許多區域 (arrangement of line segments); ...
    2. 演算法: 
                  對端點按照 x 座標 (由左而右) 排序.
            for (每個端點 p) {
                if (p 是線段 s 的左端點) {
                    insert(T, s);
                    if (above(T,s) 與 s 相交 || below(T,s) 與 s 相交)
                        return true;
                } else { /* p 是線段 s 的右端點 */
                    if (above(T,s) 與 below(T,s) 相交)
                        return true;
                    remove(T,s);
                }
            }
    3. 需要使用的資料結構: T 可用任何一種 balanced tree (例如紅黑樹) 來實作.
    4. 時間複雜度: O(n lg n) (因為排序要 O(n lg n), 而 for 迴圈做 n 次, 每次 O(lg n) 的時間.)
    5. 這是一個典型的 plane-sweeping algorithm: 把 sweep-line status (掃描線目前的狀態) 存在一個資料結構當中; 按照 event-point schedule (不平凡的事件發生的順序) 的順序逐一處理不平凡的事件 (會讓 sweep-line status 改變的事件).
    6. 注意: 最先找到的未必是最左邊的交點; 若想找到所有交點, 必須修改演算法, 每次發現交點時, 還必須把交點也加入 event-point schedule 當中, 屆時要將 sweep-line status 當中的兩線順序顛倒過來...
  8. 計算幾何的困難:
    1. 退化狀況 (degenerate cases): 兩點重合, 三點共線, 三線共點, 兩線平行, 垂直線, 水平線, ...
    2. 浮點數的有效數字有限.