在〈Delaunay 三角分割(一)〉談到了 Bowyer–Watson 演算,乍看演算的虛擬碼有點嚇人,先不管它了。
就先來看看只有三個點的情況,這沒什麼好說明的,只能連成一個三角形,因為沒有其他點,也就沒有外接圓中還有點的可能性存在。
接著增加一個點,以紅色表示如下:
增加的點在三角形內,顯然就是在其外接圓內,這個三角形不合格了,拆掉這個三角形,然後紅點與各邊的兩端點連接,形成新的一組三角形:
這就構成了新的 Delaunay 三角分割,現在問題來了,若增加的點不在三角形內,但是在其外接圓內呢?
這個三角形當然也是不合格,只不過拆掉它後,你「不能」單純地連接每個邊成為新的三角形:
因為邊交叉了,顯然不是我們要的 Delaunay 三角分割,若其中一個邊不連成三角形,才會是 Delaunay 三角分割:
問題是,怎麼知道哪個邊不連成三角形?上圖被我們去掉的那個三角形,其外接圓包含了被拆掉的三角形對角的頂點,對於這種邊構成的三角形,就是不合格的三角形。
接下來的問題就是,如果你有一堆隨機的點,一開始要選哪三個點作為初始三角形,你不能任意選取,因為選出來的第一個三角形,可能極為瘦長,附近可能有個更合適的點。
Bowyer–Watson 演算的方法是,構造一個可涵蓋全部點的超級三角形,然後一次加入一個點,進行三角分割,直到全部的點都加入為止。
例如,以下有個超級三角形,本來是個 Delaunay 三角分割,現在加入了一個新點:
現在超級三角形不合格了,根據方才的說明,拆掉超級三角形,然後紅點與各邊的兩端點連接,形成新的一組三角形:
現在有了新的 Delaunay 三角分割了,再加入一個新點:
左邊的不合格三角形被拆掉,紅點與它各邊的兩端點連接,形成新的一組三角形:
現在又加入一個新點,可以看到有兩個三角形不合格了(為了不令畫面太複雜,其他外接圓就不畫了):
這兩個三角形都要拆掉,而共用的那個邊不會用來連接成新的三角形(如方才的說明,那個邊連起來的話,構成的三角形之外接圓,將會包含其中一個頂點),得到新的三角分割如下:
新的點可以依以上方式加入,建立新的三角分割,直到全部的點加入為止,不過別忘了,一開始的超級三角形那三個頂點,是我們額外增加的,必須刪除,而連到這三個頂點的邊也要刪除,假設我們就只加入以上三個點,那麼最後得到的三角分割就是下圖的綠色部份:
只有三個點,當然就是一個三角形沒錯,要試著加入更多點是沒問題的,只不過畫圖很累啊!…XD
現在,你可以對照 Bowyer–Watson 演算 中的虛擬碼,看看能不能看懂,然後將之化為程式實作,這就留待下篇文件再來探討了。