Voronoi Diagram 2：程式設計

 肆、程式設計

一、資料結構

（一）Point

  1. int x：x值
  2. int y：y值

Point儲存(x, y)座標，可用來表示點或起點為(0, 0)的向量。

（二）Edge

  1. Point startPoint：邊的起點
  2. Point endPoint：邊的終點
  3. Point normStartPoint：邊的法向量起點
  4. Point normEndPoint：邊的法向量終點
  5. Point slope：斜率座標
  6. Point normal：法向量座標
  7. int type：邊的型態，1表示為斜線、2表示為垂直線、3表示為水平線、4表示為點。

Edge為具有方向的線段，可用來表線段或向量。如果為中垂線，則Edge會紀錄中垂線的法向量起點與終點，即此中垂線是由哪兩個點做出來的。

（三）Line：繼承Edge

  1. float a：x係數
  2. float b：y係數
  3. float c：常數

Line繼承Edge且為一組方程式 (ax + by + c = 0)，可用來表線段或向量。

（四）Polygon

  1. vector<Line> lines：多邊形的邊

Polygon為有序的多邊形，預設邊的順序為逆時針，可用來表示Convex hull。

（五）Record

  1. Polygon convexHull：儲存Convex hull
  2. vector<Line> hyperPlane：儲存Hyperplane
  3. vector<Line> voronoiLines：儲存Voronoi線段

Record為紀錄一次遞迴的結果，主要用來記錄一步一步執行的所有結果。

（六）Trend

  1. int trend：Hyperplane趨勢，0: None、1: Counterclockwise、2: Clockwise。
  2. int dir：Hyperplane選擇左邊或右邊Voronoi，0: None、1: Left、2: Right。
  3. int index：Voronoi的索引，-1: None。

Trend為紀錄Hyperplane建構的趨勢，用於協助消線步驟。

二、演算法

（一）整體架構

（圖六）Voronoi分治法架構

Voronoi Diagram演算法是使用分而治之法 (divide and conquer method)，有三個邊界條件，分別為點數為1, 2, 3的狀況，而當點數>4時，會將之分割與合併。

（二）2點狀況

（圖七）2點的程式碼

2點狀況，直接求2點的中垂線 (line 94)與hyperplane (line 95)。

（三）3點狀況

（圖八）3點的程式碼

（圖九）3點外心在界線內的示意圖

3點狀況有2步驟，步驟1先檢查3點是否共線 (line 106)與外心是否超出界線 (line 108)？如果不共線且外心在界線內，則以外心為起點，往外畫出三條中垂線 (line 110~111)。

（圖十）3點外心超界的示意圖

步驟2則是處理3點共線或外心超出界線的狀況，先找出最長的那個線段 (line 119~121)，其餘兩條線段畫出中垂線(line 122~123)。

（四）4點以上狀況

4點以上的狀況主要有3個步驟：1. 合併、2. 找出hyperplane、3. 消線。

1. 合併：合併左右convex hull與找上下切線

（圖十一）合併左右convex hull程式碼

（圖十二）分治法找上切線示意圖
來源：opengenus

使用分治法合併左右convex hull與找上下切線 (line 136)，主要有3個步驟。步驟1先找到左convex hull (C1)的最右點與右convex hull (C2)的最左點，即上圖的L1連線。

（圖十三）步驟1：找上切線的程式碼

步驟2則是找上/下切線，以找上切線為例：

  1. 檢查L1是否穿過C2 (line 487~489)？L1有穿過C2，故L1右端點往上移 (line 490)，即L1變成L2。
  2. 檢查L2是否穿過C2？L2沒有穿過C2。
  3. 檢查L2是否穿過C1 (line 493~495)？L2有穿過C1，故L2左端點往上移 (line 496)，即L2變成L3。
  4. 檢查L3是否穿過C1？L3有穿過C1，故L3左端點往上移，即L3變成L4。

以此類推一直檢查下去，直到此線都沒有穿過C1和C2為止，則此線必為上切線。

（圖十四）步驟2：判斷線段是否穿越多邊形的程式碼

如何知道線段 (a1b1)是否有穿過多邊形 (B)？只要給予三點(a1, b1, b2) ，b2為b1上/下一點，即可利用外積得知此線段是否有穿過多邊形。先求b1b2 (B)和a1b1 (A)，再將B X A，最後透過外積值判斷B到A是順時針還是逆時針。

（圖十五）步驟3：合併左右convex hull程式碼

步驟3則將左convex hull (A)與右convex hull (B)依照所找到的上/下切線依照逆時針方向合併起來。

  1. (line 530) 收集A上切點 (upperA)
  2. (line 532~535) 依照逆時針，收集A上切點→A下切點 (lowerA)的所有A點
  3. (line 536) 收集B下切點 (lowerB)
  4. (line 538~541) 依照逆時針，收集B下切點→B上切點 (upperB)的所有B點

更多分治法合併convex hull和找上切線的方法，請參考opengenus。

2. 找出hyperplane

（圖十六）找hyperplane的程式碼

找hyperplane主要有5個步驟：

  1. 步驟0為初始化參數
  2. 步驟1為找掃描線的中垂線 (scanPB)
  3. 步驟2為找掃描線最先撞到的點
  4. 步驟3為添加新hyperplane
  5. 步驟4為移動掃描線
  6. 步驟5為紀錄hyperplane的趨勢

（圖十七）找hyperplane的示意圖：粗綠線為掃描線，粗藍線為hyperplane，細淡藍線為左Voronoi，細桃紅線為右Voronoi。

Hyperplane是由多條掃描線的中垂線組合而成的，而掃描線左端點為左convex hull其中一點，右端點為右convex hull其中一點，因此可以把hyperplane視為左右convex hull的中垂線。Hyperplane實作的原則為『當hyperplane撞到Voronoi時就轉彎』，第一條掃描線為上切線，最後一條掃描線為下切線，故第一條hyperplane是上切線的中垂線，最後一條hyperplane是下切線的中垂線。

（圖十七）其上切線為L3,4，下切線為L1,6，第一條掃描線為上切線(L3,4)，而第一條hyperplane也為上切線的中垂線。

  1. 第1條hyperplane (上切線中垂線)會先撞到L3,2的中垂線（淡藍色），因此掃描線的左端點會由3->2，故第2條掃描線為L2,4。
  2. 第2條hyperplane (L2,4中垂線)會先撞到L4,5的中垂線（桃紅色），因此掃描線的右端點會由4->5，故第3條掃描線為L2,5。
  3. 第3條hyperplane (L2,5中垂線)會先撞到L5,6的中垂線（桃紅色），因此掃描線的右端點會由5->6，故第4條掃描線為L2,6。
  4. 第4條hyperplane (L2,6中垂線)會先撞到L2,1的中垂線（淡藍色），因此掃描線的右端點會由2->1，故第5條掃描線為L1,6。
  5. 第5條hyperplane 即為下切線 (L1,6)中垂線，故掃描結束。

3. 消線

（圖十八）消線的程式碼

（圖十九）消線的示意圖：粗藍線為hyperplane，粗淡藍線為順時針（向右）趨勢，粗桃紅線為逆時（向左）針趨勢。

（圖十七）會有5條掃描線和5條hyperplane，當找出完整的hyperplane後，要把多餘的Voronoi線段截短或是刪除。截短的原則為『hyperplane趨勢向左，就截短左邊；hyperplane趨勢向右，就截短右邊』先做截短的部分：

  1. 第1-2條hyperplane的趨勢為向右，且第1條hyperplane線撞到L3,2中垂線，則將L3,2中垂線右邊截短。
  2. 第2-3條hyperplane的趨勢為向左，且第2條hyperplane線撞到L4,5中垂線，則將L4,5中垂線左邊截短。
  3. 第3-4條hyperplane的趨勢為向左，且第3條hyperplane線撞到L5,6中垂線，則將L5,6中垂線左邊截短。
  4. 第4-5條hyperplane的趨勢為向右，且第4條hyperplane線撞到L2,1中垂線，則將L2,1中垂線右邊截短。

除了截短之後，還要檢查是否有懸空的Voronoi線段？如果有懸空的Voronoi線段，則要刪除。懸空的定義為『非邊界的端點沒有與其他線段相連』，在（圖十七）中有兩條懸空的Voronoi線段：

  1. 1第1條懸空Voronoi線段為L4,6中垂線，因為L4,6中垂線右端點沒有任何Voronoi線段與之相連。
  2. 2第2條懸空Voronoi線段為L3,1中垂線，因為L3,1中垂線右端點沒有任何Voronoi線段與之相連。

（五）一步一步執行

（表一）一步一步執行的8步驟

 

說明

細節

Step 1

畫Left convex hull

LCH

Step 2

畫Left voronoi

LV

Step 3

畫Right convex hull

RCH

Step 4

畫Right voronoi

RV

Step 5

畫merged convex hull

Reset + LV + RV + MCH

Step 6

畫hyperplane

HP

Step 7

消線

Reset + MCH + MV + HP

Step 8

完成

Reset + MCH + MV


（圖二十）一步一步執行的遞迴示意圖

雖然字面上是一步一步執行，但實際上只是把每一步結果存起來，然後一步一步回放而已。由於Voronoi diagram我是使用遞迴函式，故回放每一步也是使用遞迴的方式。

（圖二十）為一個點數為5的例子，5會先被切成3和2。點數為3的部分是節點0，點數為2的部分是節點1，而點數為5的部分是節點2，節點值也對應到陣列的索引值，故可以利用節點值當作陣列的索引值。同時1個小三角形固定會執行8步驟，2個小三角形會執行16步，3個小三角形會執行24步，以此類推，故可以利用步驟數來控制執行的深度。最後還要能夠判斷是左是右，所以還會有一個左右值，因此整個遞迴會用到4個參數，分別為點數 (size)、結點數 (node)、步驟數 (step)與左右值 (isLeft)。

三、演算法可改進之處

（一）找Hyperplane

（圖二十一）找hyperplane錯誤的案例，上切線為L2,3，下切線為L1,4：綠線為正確的掃描線、藍線為正確的hyperplane。

找Hyperplane的方法需要改進，（圖二十一）能夠展示我方法的問題，掃描線正確的移動過程為：

  1. 第1條hyperplane (上切線中垂線)會先撞到L2,5的中垂線（淡藍色），因此掃描線的左端點會由2->1，故第2條掃描線為L1,3。
  2. 第2條hyperplane (L2,1中垂線)會先撞到L3,4的中垂線（桃紅色），因此掃描線的右端點會由3->4，故第2條掃描線為L1,4。
  3. 第3條hyperplane 即為下切線 (L1,4)中垂線，故掃描結束。

但依照我的方法，在第1條移動到第2條時會出錯，因為是撞到L2,5的中垂線，故我的掃描線的左端點會2->5，故第2條掃描線為L5,3，但顯然這是錯誤的移動方式，這也是需要修正的部分。

（二）一步一步執行

依照我的步驟圖中，雖然每個小三角形都是執行8步驟，但當點數變多時，何時Reset？以及要補畫什麼線？這個控制就必須更精細。在我的步驟規劃圖中，只有規劃1個小三角形的情境，當有多個小三角形時，第1步驟應該要加入Reset和補畫的動作。補畫多少東西的動作，應該要再多使用一些控制變數，去調控的更精細。不過整體遞迴的概念是沒錯的，只是控制必須再設計更精細。


相關文章

  1. Voronoi Diagram 1：軟體使用說明
  2. Voronoi Diagram 2：程式設計
  3. Voronoi Diagram 3：實驗結果
  4. Voronoi Diagram 4：結論與心得
  5. VoronoiDiagram source code
  6. 演算法設計與分析｜系統性的思維｜楊昌彪


附錄

  1. Window10執行檔
  2. macOS執行檔
  3. 程式原始碼
  4. 程式原始碼合併檔
  5. 測試資料（含輸入檔與輸出檔）


參考資料

  1. 楊昌彪。2021。演算法 Term Project 實施要點。PPLab [Accessed by Dec. 2021]
  2. 蘇王奕翔。2018。以C#實作Voronoi Diagram演算法。GitHub [Accessed by Dec. 2021] 
  3. opengenus。2021。Divide and Conquer algorithm to find Convex Hull [Accessed by Dec. 2021] 
  4. 呂宗霖。2021。NSYSU_VoronoiDiagram。GitHub [Accessed by Dec. 2021] 

留言

張貼留言