Delaunay三角化實作原理

• 一，概述
• 二，圖形化解釋
  • 1. 超級三角形插入第一個點
  • 2. 插入第二個點
  • 3. 插入第三個點
  • 4. 插入第四個點
  • 5. 插入第五個邊
  • 6. 在超級三角形中移除具有極值的邊
• 三，性質：
• 四，代碼：
  • 1. 僞代碼：
  • 2. C++實作：
  • 3. C#實作：
• 參考：

一，概述

本人還有一些細節沒理清，是以希望大家多多交流

了解定義什麼是Delaunay三角大家可以看其他部落格，或者看紙異獸大佬做的示範網站寫的很清楚了，這裡一張圖帶過(實際上這個方法的點可以是任意次元的點，這裡隻是以二維舉一個例子)：

這裡主要說一下怎麼實作的

判斷方法

三角形是不是Delaunay三角形很簡單，

這個三角形做外接圓，外接圓内或者圓上沒有其他點

實作方法很多：

這裡說的Bowyer–Watson algorithm

二，圖形化解釋

主要看的維基百科，對于wiki的圖示有些地方我不是太看懂他的顔色圖示，是以以下所有的圖都不是wiki的原圖，為了友善說明我對其做了修改，也許我了解的不對，忘請糾正

1. 超級三角形插入第一個點

我們一共有

五個點

做Delaunay三角化,首先需要注意一點，以下圖中的正方形方框，假設就是圖檔大小，所有的點都必須在這個方框内，而超級三角形隻是為了算法的實作，有外接矩形所構造的一個虛拟的三角形

2. 插入第二個點

* 給圖中所有紅邊三角形(除去超級三角形，下文同樣), 做外接圓

* 新插入的點P2在 S1S2P1 S 1 S 2 P 1 ， S0P2S2 S 0 P 2 S 2 的外接圓内，是以删除線 S2P1 S 2 P 1 ，

* 并同時把綠色線變成紅色線(綠色線其實在判斷完新插入點的條件後，要連接配接的線，為下一個點的插入做準備)，變成下圖：

3. 插入第三個點

對所有紅線構成的三角形做外接圓，判斷點P3是不是在外接圓内。顯然 S1P2S2 S 1 P 2 S 2 外接圓不符合條件，是以要删除這個三角形，問題是删除哪條邊。我覺得有兩種解釋:

* 超級三角形的邊是不會删除的，而 S1P2S2 S 1 P 2 S 2 外接圓符合判定條件，是以 S2P2 S 2 P 2 不删除

* 三角形 S1P1P2 S 1 P 1 P 2 的外接圓不符合判定條件，與 S1P2S2 S 1 P 2 S 2 外接圓公共邊是 S1P2 S 1 P 2 ，是以删除 S1P2 S 1 P 2

個人傾向于第一種，因為wiki給的圖沒有 S1P1P2 S 1 P 1 P 2 的外接圓，後期還要看一下代碼，這裡才清楚

根據僞代碼，是删除不符合判定條件的三角形共享的邊

for each edge in triangle do
   if edge is not shared by any other triangles in badTriangles
      add edge to polygon
           

依舊删除 S1P2 S 1 P 2 ，綠線變成紅線

4. 插入第四個點

這次很nice，紅線的三角形都滿足判定條件。直接紅線變成綠線

5. 插入第五個邊

方法同上,兩個黃色的外接圓,去掉 P3S2 P 3 S 2 ，綠線變紅線

6. 在超級三角形中移除具有極值的邊

最後藍色的邊就是我們所求得

三，性質：

1. 不喜歡瘦的三角形

   所謂的瘦，就是一個鈍角很大的鈍角三角形

   

四，代碼：

1. 僞代碼：

首先說明一下，下面說的周遊三角形不包括超級三角形，壞三角形就是不符合文章開頭判定條件的三角形.。polygan是多邊形，是我們删掉一些邊後中間過程的圖形。好邊就是我們要留下的邊。

triangulation就是我們現在的有效圖形的。

兩個主要的for循環，第二個for循環就是從左完成以後去掉多餘的邊。就是對應

圖示6

主要看第一個for循環周遊點集中的所有的點:

• 周遊所有三角形。不符合判定條件的，添加到壞三角形
• 周遊所有壞三角形的所有邊。找出好邊。
• 周遊所有壞三角形。删掉壞邊。
• 周遊好邊。加到有效圖形當中

  

2. C++實作：

1. 實作的庫
   • C++
   • Python

2. opencv實作

   網上的基本都是看着<學習opencv>這本書寫的，我這裡隻是記錄一下自己的過程。

   一個不錯的連結而且有三個能跑的代碼，點這裡

3. C#實作：

https://blog.csdn.net/k346k346/article/details/52244123

參考：

1. wiki Bowyer–Watson algorithm
2. https://www.cnblogs.com/zhiyishou/p/4430017.html
3. https://blog.csdn.net/NewThinker_wei/article/details/45598769
4. https://blog.csdn.net/k346k346/article/details/52244123