軟體規格書
輸出與輸入（資料）規格
- 滑鼠點擊畫布
- 使用者可以點擊畫布的任意位置，並會將點即時新增在畫布上，程式也會記錄點的座標。
- Open File
- 使用者可以使用程式介面上的Open File進行讀檔動作，可以開啟測試的座標資料，也可以開啟程式輸出的檔案。
- Save File
- 使用者可以使用程式介面上的Save File進行存檔動作，可以將繪畫出來的點及線段座標排序後輸出，輸出檔案為『output.txt』。
功能規格與介面規格
程式介面圖中，可以分為以下幾種功能：
- Open File 可以開啟測試的座標資料，也可以開啟程式輸出的檔案。
- Save File 可以將繪畫出來的點及線段座標排序後輸出，輸出檔案為『output.txt』。
- Run 依照目前的點直接輸出Voronoi圖形。
- StepByStep 依照目前的點以步驟的方式顯示圖形，每按一下會顯示下一步驟的圖形，直到輸出完整的Voronoi圖形。
- Clean 清除畫布上所有的點及線段。
- NextSet 可以使用此按鈕切換到下一組測試資料。
- 單純分治法 依照目前的點以步驟的方式顯示DivideAndConquer和ConvexHull的圖形，每按一下會顯示下一步驟的圖形。
軟體測試規劃書
- 1~2點 兩點以下會直接劃出中垂線，不必考慮HyperPlane問題，除了特殊狀況需要額外判斷，如水平、垂直等問題。
- 3點 三點會直接解出Voronoi圖形，不必考慮HyperPlane問題，因三角形會比較麻煩，可以分成三種三角形鈍角、銳角、直角三角形，三種三角形的外心分別在三角型外部、三角形內部、三角形斜邊上，所以會先需要找出外心位置來判斷是哪種三角形再畫出任兩點之間的中垂線。
- 4~6點 三點以上六點以下會進行Divide和一次Merge，會使用到HyperPlane，在Divide後即可套用先前寫好的兩點或三點副程式，並進行合併後，再將HyperPlane寫好。
- 7點以上 七點以上會進行多次Divide和Merge，先將6點以下製作好後，邊測試邊進行偵錯，再將其完成。
軟體說明
安裝說明
將主程式下載並解壓縮後，執行M113040021.exe即可，或是使用python對M113040021.py編譯並執行。
使用時須注意要點
在使用此程式時，請勿點選Run後點選StepByStep或是在StepByStep過程中點選儲存檔案皆會造成程式崩潰。
使用說明
- 繪製點
- 繪製Voronoi Diagram
- 繪製左圖形Voronoi，藍色
- 繪製右圖形Voronoi，綠色
- 繪製左圖形ConvexHull，藍色
- 繪製右圖形ConvexHull，綠色
- 繪製上下切線，黑色
- 繪製合併的ConvexHull，黑色
- 繪製HyperPlane，紅色
- 只留下HyperPlane線段其餘前面步驟線段消失
紅色範圍中為畫布區，可在上面任意點擊，並會將點即時新增在畫布上，程式也會記錄點的座標。
繪製方式可以分為Run模式及StepByStep模式，按下Run按鈕可直接繪製最終結果，按下StepByStep按鈕可一步一步繪製結果。
StepByStep-8步驟介紹
程式設計
資料結構
- self.run_data：字典型態 會記錄所有點的座標，儲存方式舉例{‘size’: 5, ‘x’: [109, 150, 249, 329, 401], ‘y’: [110, 338, 551, 321, 71]}， 其中size是紀錄總共有幾個點，x是紀錄每個點的x座標，y是紀錄每個點的y座標，每個點的座標即為(self.run_data[‘x’][i],self.run_data[‘y’][i])， 在儲存前，點會依據x由小到大做排序。
- self.StepByStep_Point：list型態 會記錄每個步驟線段，儲存方式舉例{‘x’: [0, 8397.59090909091], ‘y’: [208.58686440677965, 600], ‘step’: 1}， 其中step是紀錄這是第幾步驟，當程式在執行時會根據不同的動作給予不同的step，x是紀錄每個點的x座標，y是紀錄每個點的y座標， 步驟1含有1線段，即為從頭開始依序兩座標相連。此list存放大量步驟的字典，直到程式結束。
- self.find_line_x、self.find_line_y：list型態 會記錄任意兩點的中垂線，當儲存兩條線段後，會儲存進self.StepByStep_Point中。
- self.Voronoi_3_x、self.Voronoi_3_y：list型態 會記錄任意三點的中垂線，當儲存三條線段後，會儲存進self.StepByStep_Point中。
- self.Ans_Line_x、self.Ans_Line_y：list型態 會記錄Hyper_Plane線段，當Hyper_Plane結束時，會儲存進self.StepByStep_Point中。
- self.StepLR 判斷正在做的方向，1左邊 2右邊。
- self.color_flag 判斷要使用哪種顏色畫圖，每種數字代表著不同的顏色，並在副程式DrawLine()會判斷。
- self.mode 判斷現在是開測資檔還是開輸出檔，0測資檔 1輸出檔。
撰寫程式中須注意的細節
- 三點以下的Voronoi Diagram 要特別講解此部分的原因為，因為這部分是整個程式的『核心』，因為在使用DivideAndConquer副程式時，會將所有點以遞迴方式， 將所有的點分成一半直到每個部分都只剩下2或3個點。 兩點，大致上會遇到的問題為當兩個座標點x相同時，會需要額外做處理，畫線的時候也要特別注意到邊界的問題。 三點共線，此問題其實很簡單，只需把他看成兩點與兩點，因我在處理這些問題之前會先將所有的點依據x大小進行排序， 所以只需將第一個點與第二個點進行兩點垂直線，再將第二個點與第三個點進行兩點垂直線。 三點共點，不做處理。 三點，除了上面兩種情況外，剩下皆為三角形。三角形可分為三種，直角三角形、鈍角三角形、銳角三角形， 以上三種三角形皆是使用外心與三邊中點進行連線，但不同的三角形處理的方式也有所不同。
- 銳角三角形(即外心在三角行內部) 此三角形最為簡單，只需將三個邊中點與外心判斷位置來決定畫線方線及使用方程式ax+by+c=0，來求出邊界的座標。
- 鈍角三角形(即外心在三角形外部) 需判斷外心的對面點是哪一點，其餘兩邊可直接使用中點與上面銳角三角形的外心與點連線方法相同，至於對面點的部分要先判斷， 對面點與外心的位置，以位置來決定畫線方向，並透過方程式ax+by+c=0求出邊界座標。
- 直角三角形(即外心在斜邊上) 需判斷外心的對面點是哪一點，其餘兩邊可直接使用中點與上面銳角三角形的外心與點連線方法相同， 至於斜邊上的點可直接使用斜邊兩點算方程式，再以此方程式求出垂直方程式，並利用對面點位置來決定畫線方向， 並透過方程式求出邊界座標。
- 判斷方式
- DivideAndConquer 此部分是程式當中算是簡單的部分，在進行此步驟前會先將所有的點依據x做排序， 利用遞迴的方式將所有的點進行分解，每次分解都是由中間切出左半邊及右半邊，如分割後點數數量大於3則繼續分割， 直到每部分的點數量都小於等於3為止。再呼叫前述的副程式，將兩點跟三點的voronoi圖形繪製出來，繪製完成後會依序進行Merge的動作。
- Merge 此部分主要的目的有3個，第一將左右的圖形分別進行ConvexHull，會回傳圖形的ConvexHull及點繞一圈的順序， 第二將左右圖形丟入Find_UP_LOW並尋找上下切線，當尋找完成後會回傳上下切線及點繞一圈的順序， 第三將上下切線及合併的的圖形丟入Hyper_Plane_new副程式找Hyper Plane的動作。
- ConvexHull 我使用的ConvexHull方法是使用外積的方式尋找圖形上下的凸包，先從起點開始依序掃描，如果前面兩個點與下一個點作外積的方向與下一個點外積的方向相同， 則會繼續掃描下一個點直到沒有下一個點為止即為下凸包。再從終點開始依序掃描，直到沒有點為止即為上凸包，上下凸包合起來即為完整的凸包。
- Find UP LOW 尋找上下切線的方式為先找出左圖形x最大的點及右圖形x最小的點作為兩圖形的起點，我的作法是左邊的點先不動右邊的點依序往上， 在此先稱為左點為A右點為B右邊上面一個點為C，如果AB與AC外積為逆時針則會尋找下一個C點直到遇到AB與AC外積為順時針則停止， 右邊的點固定，在此先稱為右點為A左點為B左邊上面一個點為C，如果AB與AC外積為順時針則會尋找下一個C點直到遇到AB與AC外積為逆時針則停止， 此時會再嘗試轉動右邊的點，如果有轉動則左邊的點也要重新判斷，直到兩邊都無法轉動則找到『上切線』，反之下切線的判斷方式也是如此，利用外積與轉動方向來決定。
- Hyper Plane Hyper Plane是整個程式當中最困難的部分，因為意外狀況很多，需要實際遇到才會知道問題點，下面我會介紹Hyper Plane正確的走法。
下列我會列出主要2個儲存結構
下列為次要結構
下列為程式主要判定變數
直角三角形：任意兩邊長平方相加等於第三邊邊長平方。
銳角三角形：先求外心，判斷外心是否在三個點之間。
鈍角三角形：先求外心，判斷外心是否在三個點之外。
上面五張圖從左至右分別為一般情況的Hyper Plane步驟，第一張圖為上下切線，第二張圖為上切線下來與左右圖形中垂線的交點，第三張圖行為因為與右邊圖形有交點，
所以掃描線右邊的點跑到下一個點，那下一個點就是那條中垂線的另一個點，第四張圖為下一個交點，第五張圖為掃描線與下切線重疊。
結束條件為掃描線的中垂線已經不會與兩邊圖形任何的中垂線有交點即可結束，否則掃描線將會持續往下。
當Hyper Plane畫下來時會遇到的問題是不知道要消哪一邊的線段，那此部分的判斷方式，我先假設前述兩交點分別為A與B，那B交點的掃描線左邊稱作H1，
右邊稱作H2，下一個交點稱為C，若AB與AC外積，若為逆時針旋轉，則將該方向的Voronoi線段消除(AB與AH1也為逆時針)，依此類推，其餘特殊判斷狀況為，
AB與AC外積、AB與AH1外積和AB與AH2外積皆為順/逆時針，則整段Voronoi線段留著，如果AB與AC外積與AB與AH1外積和AB與AH2外積為順逆逆或是逆順順，
則整段Voronoi線段刪除，經過所有消除動作後，最後剩餘的線段即為Hyper Plane。
軟體測試與實驗結果
- 程式語言：Python
- 編譯版本：Python 3.9.1
- 作業系統：Windows 10
- 編譯器名稱：Visual Studio Code
- CPU：AMD Ryzen 5 3600 6-Core Processor
- RAM：32GB
- 顯示卡：NVIDIA GeForce RTX 3060 Ti
- 三點以下：
- 四點以上六點以下：
環境設備
執行環境
硬體設備
執行結果
結論與心得
程式語言選擇
在作此project之前，我就對Python這語言很熟悉，因之前有使用過Python製作過很多圖形介面的程式，所以我就直接選擇Python這個語言，
使用Python搭配Qt來製作project的主要介面。
期中進度
期中的進度相對於期末的進度來說是很簡單的，因為只需要針對介面製作以及三點以下的Voronoi圖形製作，在寫三點的狀況時，
我有想到可以依照不同的狀況來做判斷，其中分別有三點共線、三點共點、銳角三角形、直角三角形、頓角三角形，此幾種方向去思考，
先把有可能的大方向想出來在去做節省了不少的時間，該注意的點有三角形的外心在三角形的裡面、外面或是斜邊上這三種分別會有不同的處理方式。
期中進度所做的事情，我都有根據不同的功能寫成function，如畫線、畫點、兩點、三點圖形，以便期末進度能夠減少許多撰寫的時間。
期末進度
剛開始我是以四點為目標，覺得四點做出來就很厲害了，在排除例外狀況後想到要製作ConvexHull找上下切線及Hyper Plane是一件很困難的事情，
但經過詳細了解與規劃，實際花最多時間的部分是Hyper Plane，因為需要對左右兩邊的Voronoi進行消線，還須要判斷轉彎的方向及下一條掃描線的位置。
當四點都能順利進行後，我開始對五點及六點的特殊狀況進行處理，有一個部分比較要注意，因為三角形會有三個中垂線，那在畫Hyper Plane線段時，
會有一個中垂線不會碰到，此線斷必須消線，其餘部分大致上都能正常處理。
心得
剛開始在上課時聽到要做Voronoi Diagram，心中是害怕的，但也覺得很具有挑戰性，想嘗試看看把它完成，在剛開始的目標設定為四點然後五點六點及以上，
再將所有步驟及狀況一一列出後，其實就沒有想像中的困難了，畢竟程式也是要一步一步最小的function開始，才有現在這樣的成品，
雖然途中有遇到很多的例外狀況，但在一一解決後，很有成就感。實作此project，學到了很多，也給自己很多的挑戰，也讓自己在研究所階段中有一個難忘的回憶。