三角學/愛好者/德洛內三角剖分

平面上的德洛內三角剖分，顯示外接圓

德洛內三角剖分是一種連線一組點以形成三角形網格的特殊方法。德洛內三角剖分傾向於避免細長三角形。該三角剖分由 鮑里斯·德洛內 在 1934 年發明。

應用

檔案：Bush-Arnie-morph.jpg
喬治·W·布什到阿諾德·施瓦辛格的變形	流體流動問題的有限元分析解決方案

• 對於變形影像，德洛內三角剖分提供了一種“良好”的方法，可以從將要移動的點建立三角形網格。每個三角形都可以以簡單的方式進行扭曲，從而導致整體影像的複雜“變形”扭曲。在顯示的變形示例中，三角形形狀從一個影像扭曲到另一個影像，例如，第一個影像中的頭髮被扭曲以適應第二個影像中的頭髮。同時，顏色從一種顏色“交叉淡入”到另一種顏色，因此灰色交叉淡入棕色。

內華達山脈地形圖	二維三角形網格	從網格計算得出的二維解決方案

• 對於給定一組樣本點來建模地形或其他物體，德洛內三角剖分提供了一組不錯的三角形，可以作為模型中的多邊形使用。特別是，德洛內三角剖分避免了狹窄的三角形（因為它們與它們的面積相比具有較大的外接圓）。

• 德洛內三角剖分用於許多其他應用中，在這些應用中，形狀必須被分割成三角形。結構應力和應變的分析通常使用三角形網格進行。在上面的分析中，在最感興趣的區域放置更多點，以在該區域獲得更精細的更詳細的分析。這也是我們在變形影像時所做的事情 - 我們在最需要控制變形細微之處的地方放置更多點。如果你想把皺眉變成微笑，在嘴周圍放更多點，這樣你就可以更容易地改變形狀。

形式化定義

對於平面上的一組點P，德洛內三角剖分是三角剖分 DT(P)，使得P 中的任何點都不在 DT(P) 中任何三角形的外接圓內。外接圓。德洛內三角剖分最大化三角剖分中所有三角形角度的最小角度；它們傾向於避免細長三角形。

對於同一線上的一組點，不存在德洛內三角剖分（實際上，三角剖分的概念對於這種情況是未定義的）。對於同一個圓上的四個點（例如，矩形的頂點），德洛內三角剖分不是唯一的：將四邊形分成兩個三角形的兩種可能的三角剖分都滿足“德洛內條件”，即所有三角形的外接圓具有空內部的要求。

與沃羅諾伊圖的關係

平面上 離散 點集 P 的德洛內三角剖分 對應於 對偶圖 的 沃羅諾伊鑲嵌 P。特殊情況包括線上存在三個點和圓上存在四個點。

• 
  德洛內三角剖分，顯示所有外接圓及其圓心（紅色）。
• 
  連線外接圓的圓心會產生 沃羅諾伊圖（紅色）。

特性

設 n 為點數（頂點）。

• 在平面上，每個頂點平均有六個周圍的三角形。
• 在平面上，德洛內三角剖分最大化最小角。與點的任何其他三角剖分相比，德洛內三角剖分中的最小角度至少與任何其他三角剖分中的最小角度一樣大。但是，德洛內三角剖分不一定最小化最大角度。
• 外接任何德洛內三角形的圓在其內部不包含三角剖分的任何其他頂點。
• 如果經過兩個頂點的圓在其內部不包含任何其他頂點，則連線這兩個點的線段是給定點德洛內三角剖分的邊。
• 任何點 p 的最近鄰 b 是德洛內三角剖分中的邊 bp。 最近鄰圖 是德洛內三角剖分的子圖，最小生成樹也是如此。

凸包

• 三角剖分中所有三角形的並集是點的凸包。
• 在平面上，如果有 b 個頂點在凸包上，那麼點的任何三角剖分最多有 2n − 2 − b 個三角形，加上一個外部面（參見 尤拉特徵）。

視覺化德洛內定義：翻轉

從上面的屬性中，一個重要的特徵出現了：觀察兩個三角形 ABD 和 BCD，它們有公共邊 BD（見圖），如果角 α 和 γ 的和小於或等於 180°，則三角形滿足德洛內條件。

這是一個重要的屬性，因為它允許使用翻轉技術。如果兩個三角形不滿足德洛內條件，則將公共邊 BD 切換為公共邊 AC 會產生兩個滿足德洛內條件的三角形

• 
  這種三角剖分不滿足德洛內條件（α 和 γ 的和大於 180°）。
• 
  這種三角剖分不滿足德洛內條件（外接圓包含超過 3 個點）。
• 
  翻轉公共邊會為這四個點產生德洛內三角剖分。

演算法

許多計算德洛內三角剖分的演算法依賴於快速操作來檢測點是否在三角形的外接圓內，以及用於儲存三角形和邊的有效資料結構。在二維中，檢測點 D 是否位於 A、B、C 的外接圓內的一種方法是計算 行列式:

${\begin{vmatrix}A_{x}&A_{y}&A_{x}^{2}+A_{y}^{2}&1\\B_{x}&B_{y}&B_{x}^{2}+B_{y}^{2}&1\\C_{x}&C_{y}&C_{x}^{2}+C_{y}^{2}&1\\D_{x}&D_{y}&D_{x}^{2}+D_{y}^{2}&1\end{vmatrix}}={\begin{vmatrix}A_{x}-D_{x}&A_{y}-D_{y}&(A_{x}^{2}-D_{x}^{2})+(A_{y}^{2}-D_{y}^{2})\\B_{x}-D_{x}&B_{y}-D_{y}&(B_{x}^{2}-D_{x}^{2})+(B_{y}^{2}-D_{y}^{2})\\C_{x}-D_{x}&C_{y}-D_{y}&(C_{x}^{2}-D_{x}^{2})+(C_{y}^{2}-D_{y}^{2})\\\end{vmatrix}}>0$

假設A、B 和 C 逆時針排列，當且僅當D位於外接圓內時，該值大於零。

翻轉演算法

如上所述，如果一個三角形是非 Delaunay 三角形，我們可以翻轉其一條邊。這導致了一種簡單的演算法：構建點的任意三角剖分，然後不斷翻轉邊直到沒有非 Delaunay 三角形。不幸的是，這可能需要 O(n²) 次邊翻轉，並且不能擴充套件到三維或更高維度。

增量法

最直接有效地計算 Delaunay 三角剖分的方法是每次新增一個頂點，並重新剖分受影響的圖形部分。當新增一個頂點v 時，我們將包含v 的三角形分成三個三角形，然後應用翻轉演算法。如果直接執行，這將需要 O(n) 的時間：我們遍歷所有三角形以找到包含v 的一個三角形，然後可能需要翻轉所有三角形。因此，總的執行時間為 O(n²)。

如果我們以隨機順序插入頂點，事實證明（透過一個相當複雜的證明），每次插入平均只會翻轉 O(1) 個三角形——儘管有時會翻轉更多三角形。這仍然留下了需要改進的點定位時間。我們可以儲存執行的分割和翻轉的歷史記錄：每個三角形儲存指向替換它的兩個或三個三角形的指標。要找到包含v 的三角形，我們從一個根三角形開始，並沿著指向包含v 的三角形的指標，直到找到一個尚未替換的三角形。平均而言，這將需要 O(log n) 的時間。因此，對於所有頂點，這將需要 O(n log n) 的時間。雖然該技術可以擴充套件到更高維度（如 Edelsbrunner 和 Shah 證明的那樣），但即使最終的 Delaunay 三角剖分很小，執行時間也可能隨維度呈指數增長。

Bowyer-Watson 演算法為增量構建提供了另一種方法。它為計算包含新插入頂點的 Delaunay 三角形提供了邊翻轉的替代方法。

分治法

二維三角剖分的分治演算法由 Lee 和 Schachter 提出，後來由 Guibas 和 Stolfi，以及後來的 Dwyer 進行改進。在這個演算法中，我們遞迴地畫一條線將頂點分成兩個集合。我們為每個集合計算 Delaunay 三角剖分，然後沿著分割線將兩個集合合併。使用一些巧妙的技巧，合併操作可以在 O(n) 時間內完成，因此總的執行時間為 O(n log n)。

對於某些型別的點集，例如均勻隨機分佈，透過明智地選擇分割線，可以將預期時間降低到 O(n log log n)，同時仍然保持最壞情況下的效能。

P. Cignoni、C. Montani 和 R. Scopigno 在 "DeWall：E^d 中快速的分治 Delaunay 三角剖分演算法" 一文中介紹了一種在d 維中執行三角剖分的分治正規化。

分治法已被證明是最快的 DT 生成技術。

掃描線法

Fortune 演算法 使用掃描線技術在平面情況下實現 O(n log n) 的執行時間。

Sweephull

Sweephull 是一種快速混合技術，用於二維德勞內三角剖分，它使用徑向傳播的掃描包絡（從徑向排序的二維點集中依次建立，得到一個不重疊的三角剖分），並配以最終的迭代三角形翻轉步驟。 經驗結果表明，該演算法的執行時間大約是 Qhull 的一半。 GPL 程式碼可從 獲得

致謝

• 此頁面最初是根據維基百科上的德勞內三角剖分建立的。