Bowyer-Watson算法

原文連結：Bowyer-Watson算法

不規則三角網（Triangulated Irregular Network，TIN）在表示地形的形态方面具有較好的表現，其生成算法一直備受關注。Delaunay三角剖分生成的網格正則性好，是以在實際工程計算中應用很廣。生成 Delaunay 三角網格的方法中，目前大都基于 Bowyer-Watson法，它是一種逐點插入法，基本思路是 ：先由給定的點集生成一初始網格，再根據 Delaunay 剖分原理，逐次向網格内加點 ,并重新連接配接生成新網格，直到所有點添加完畢。

下面我們就該算法的思路、步驟進行解析。

基本思想：

1. 假定已生成了連接配接若幹個頂點的 Delaunay 三角網格
2. 加入一個新的節點，找出所有外接圓包含新加入節點的三角形，并将這些三角形删除，形成一個空腔
3. 空腔的節點與新加入的節點連接配接，形成新的 Delaunay 三角形網格
4. 不斷循環直到周遊完所有點

示意圖如下：

通過上述思路我們總結出算法需要解決的幾大問題：

1. 初始格網的生成
2. 新增點所影響三角形的查找
3. 空腔的生成

下面我們就這些問題提出解決方法。

我們可以通過顯示視窗的四個頂點來生成包含所有離散點的兩個三角形，算法結束後删除就好，如圖

而外接圓包含新增點的三角形，這裡我們稱為壞三角形，壞三角形的查找是本算法的核心。

一般來說，如果采用暴力周遊的方法，随着算法後面三角格網的複雜度不斷增加，壞三角形的查找也會變得越來越困難。是以我們希望可以有方法加速這一程序，但這裡我們不做讨論，因為我沒有實際運用。沒錯我的算法很暴力。

那麼問題來了，新增點的壞三角形可能不止一個，如果要一直周遊出所有壞三角，就算是我也沒暴力到這種程度。

這裡我們發現，如果一個三角形是壞三角，那麼它鄰接的三角肯定有兩個也是壞三角。那麼我們可以通過建構一個三角形鄰接表，找到一個壞三角就等于找到了一圈壞三角。

self.coords.append(p)

        # 計算外接圓包括p點的三角（壞三角形）
        bad_triangles = []
        for T in self.triangles:
            # 距離跟半徑的比較
            if self.inCircle(T, p):
                bad_triangles.append(T)

        # 空腔邊緣。
        boundary = []
        T = bad_triangles[0]
        edge = 0
        while True:
            # 檢查三角形T的邊緣是否在boundary裡...
            tri_op = self.triangles[T][edge]
            if tri_op not in bad_triangles:
                boundary.append((T[(edge+1) % 3], T[(edge-1) % 3], tri_op))
                edge = (edge + 1) % 3
                # 是否找完一圈
                if boundary[0][0] == boundary[-1][1]:
                    break
            else:
                # 下一條邊
                edge = (self.triangles[tri_op].index(T) + 1) % 3
                T = tri_op

        # delete删除，删出一個空洞
        for T in bad_triangles:
            del self.triangles[T]
            del self.circles[T]
           

代碼中boundary即是圖中綠色空腔邊緣。删掉所有壞三角形成空腔，再通過空腔邊緣與新增點形成新的三角格網完成更新，當然不要忘了更新各種附加資料。

最終效果圖如下，右方的括号内是三角形頂點點号