Voronoi Diagram 1：軟體使用說明

壹、 軟體資訊

  1. 題目：Voronoi Diagram
  2. 作者：呂宗霖 (Tsung-Lin Lu)
  3. 系級：中山資工所碩一
  4. 學號：M093040114
  5. 程式語言：C++
  6. 開發框架：Qt 6.1.3

貳、軟體規格書

一、輸入與輸出方式

（一）輸入方式

  1. 滑鼠：使用滑鼠點擊畫布。
  2. 座標：在添加介面中，輸入(x, y)值。
  3. 隨機：在添加介面中，指定點數，以隨機產生數點。
  4. 輸入檔 (.txt)：在檔案介面中，點擊『讀取輸入檔』。#字號為註解；一個數字為點數，當一個數字為0時，代表結束；兩個數字為(x, y)值，細節請看pplab連結。
  5. 輸出檔 (.txt)：在檔案介面中，點擊讀取輸出檔。
（圖一）輸入檔格式

（二）輸出方式

  1. 在檔案介面中，點擊『輸出文字檔』，即會輸出txt文字檔。
  2. 點格式：以P開頭，後面接(x, y)。
  3. 邊格式：以E開頭，後面接(x1, y1, x2, y2)。
  4. 座標以字典序 (lexical order)排序，即x1 ≤ x2或x1 = x2 & y1 ≤ y2。
（圖二）輸出檔格式

二、介面與功能

（一）主介面

（圖三）主介面圖示

  1. 軟體名稱：Voronoi Diagram
  2. 畫面：600 x 600
  3. 添加點：滑鼠位置、(x, y)輸入、點數量
  4. 執行：執行、下一組資料、一步一步執行、清空畫面
  5. 檔案：讀取輸入檔、讀取輸出檔、輸出文字檔
  6. 點資料：點數、點座標
  7. 邊資料：邊數、邊座標
  8. 狀態列

（二）功能

  1. 添加點→滑鼠位置：顯示滑鼠在畫面中的座標位置。
  2. 添加點→(x, y)輸入：指定(x, y)座標的方式添加點。
  3. 添加點→點數量：指定點數的方式隨機添加點。
  4. 執行→執行：一次執行完畢。
  5. 執行→下一組資料：如果使用『讀取輸入檔』功能，顯示輸入檔中下一組點資料。
  6. 執行→一步一步執行：一步一步執行，主要分成八步驟。(1)畫left convex hull、(2)畫left Voronoi、(3)畫right convex hull、(4)畫right Voronoi、(5)畫merged convex hull、(6)畫hyperplane、(7)消線、(8)完成。
  7. 執行→清空畫面：清除畫面上的邊和點。
  8. 檔案→讀取輸入檔：使用輸入檔 (.txt)的方式添加點。
  9. 檔案→讀取輸出檔：使用輸出檔 (.txt)的方式添加點或邊。
  10. 檔案→輸出文字檔：將Voronoi Diagram存成txt文字檔。

三、測試規劃

  1. 1點：不做任何動作。
  2. 2點：找出2點中垂線。
  3. 3點：找出3點外心，並以外心為起點，往外畫出三條中垂線。
  4. 4~6點：分割 (divide)與合併 (merge)一次，有機會出錯或進入無限迴圈。
  5. 7點以上：很大機率會進入無限無圈，請小心服用。


參、軟體說明

一、軟體安裝

  1. Windows：不需安裝，直接在VoronoiDiagram資料夾中，點擊VoronoiDiagram.exe，切勿將exe檔和資料夾分離，因為資料夾中還有其他執行必要的檔案。
  2. MacOS：不需安裝，直接點擊VoronoiDiagram.app，此應用程式為intel CPU架構。

二、軟體使用

1. 添加點：可以使用五種方式，在畫面中添加點。

（圖四）添加六個點

2. 執行Voronoi：可以用執行或一步一步執行。

（圖五）一步一步執行，現在為第7步：消線。
綠線為merged convex hull、藍線為hyperplane。 

3. 輸出文字檔：使用檔案→輸出文字檔，來保存Voronoi Diagram結果，文字檔格式如介面中點資料與邊資料所示。


相關文章

  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] 

留言

張貼留言