[ Delaunay Triangulation ] Delaunay 三角剖分

我高中的時候在morris的網站第一次看到這個東西，那個時候就很想試著寫出來看看，但那時候英文很不好所以不會找資料就沒有成功。直到今年的NPSC，聽說台大出了一題找Voronoi Diagram的題目沒有人寫出來，於是我就想挑戰看看，寒假開始之後就認真研讀相關資料，終於在前幾天完成了隨機增量法以及分治法的模板。

先來說說甚麼是三角剖分 Triangulation 吧！假設平面上散布很多不重複的點，現在用一些線段將這些點連成許多的三角形，滿足所有三角形的內部不會有其他點，而且三角形的數量越多越好，這就是一個三角剖分。

Delaunay Triangulation是一種特殊的三角剖分，滿足所有的三角形其外接圓中不會出現其他的點，這樣的性質會使得所有三角形中最小的角盡量大，而且最重要的是它是 Voronoi Diagram 的對偶圖，Voronoi Diagram 直接求的話很容易有浮點誤差而且程式也不好寫，因此從Delaunay Triangulation直接轉換過去會更加方便。

還有一個很重要的點，透過Delaunay Triangulation 的邊集合可以找出平面歐幾里得距離最小生成樹。

這裡我先給出點的資料結構，方便接下來的講解：

一般來說找出 Delaunay Triangulation 的其中一個操作是要判斷一個點是不是在一個三角形的外接圓內，但直接去求外接圓圓心會有浮點誤差，因此有一個作法是將所有點投影到三維的拋物線曲面中，也就是下圖的碗狀曲面，會發現把一個圓投影上去之後，該圓會落在一個平面上，圓內的點會在平面下面，圓外的點會在平面上面，這樣就可以利用一些處理三維幾何的技術就可以避免浮點誤差的判斷點是否在外接圓內了。

範例程式碼中點在圓內輸出1，圓外輸出-1，圓上輸出0：

當然實作時並不會真正的寫一個三維點的資料結構，這樣程式碼會比較長。

Delaunay Triangulation 我所知道的有兩種，分別是隨機增量法以及分治法。隨機增量法再點隨機加入的時候複雜度是$\ord{n\log n}$，分治法則是穩定$\ord{n\log n}$，但我的實作分治法的效能是隨機增量法的三倍快。由於兩種做法都已經有詳細教學了這裡就不用文字敘述。

1. 隨機增量法教學在《Computational Geometry - Algorithms and Applications》書中有提到，該書有中文版
2. 分治法教學請點該網站連結

這裡附上程式碼，順帶一提morris的分治法好像在某些測資會因為三點共線爛掉

隨機增量法：

分治法：