# voronoi diagram
> 張恩維

## 軟體規格書
* 輸入
1. 滑鼠在畫布上任意點擊，畫布大小為603*603
2. 輸入x軸及y軸座標
3. 隨機產生數個點
4. 讀入「輸入文字檔」
5. 讀入「輸出文字檔」，直接在畫布繪出圖形
* 輸出
1. 按下Save，輸出「輸出文字檔」
2. 輸出文字檔格式如下：
3. 輸入的座標點：P x y // 每個點佔一行，兩整數 x, y 為座標。
線段：E x1 y1 x2 y2 // (x1, y1) 為起點，(x2, y2) 為終點，其中 x1≦x2 或 x1=x2, y1≦y2
4. 座標點排列在前半段，線段排列在後半段。
5. 座標點以 lexical order順序排列（即先排序第一維座標，若相同，則再排序第二維座標；線段亦以lexical order順序排列。

### 功能規格與介面規格
#### 主畫面
#### 功能介紹
* Read Data : 輸入檔案
* Run : 開始執行
* Save : 輸出檔案
* Next set : 下一筆測資
* Clean : 清除畫布
* step by step : 執行下一步

## 軟體說明
### 安裝說明
下載後直接執行exe檔即可。
### 使用說明
* 提供兩種方法輸入
1. 直接在畫布上利用滑鼠點擊
2. 以符合輸入規範的檔案(.txt)當作輸入
* 以兩種方式繪製
1. 按下"run"按鈕，一次畫完diagram.
2. 按下"step by step"按鈕，直到畫完diagram.

* 提供一種方式輸出
1. 按下save，輸出.txt檔
## 程式設計

### 資料結構
↑用於divide and conquer時
↑存點的結構
↑存邊的結構
↑hyperplane的結構

### 三點以下
利用重心公式，(a+b+c)/3，而重心一定在三角形的內部，在利用重心到各點的向量進行逆時針的排序，這樣一來可以確定法向量一定是朝外射出，接著再找到到三角形的外心，再由外心向法向量的方向畫出即可完成。在特別注意一下三點共線的情空即可。
### 四點

def voronoi(pointList):
    pointList.sort(key = attrgetter('x', 'y')) # 先對 x 排序在對 y 排序
    if(len(pointList) == 1 ):
        return
    elif(len(pointList) == 2):
        result = two_point(pointList)
    else:
        p_left , p_right = divide(pointList)
        v_left = voronoi(p_left) # 得到 左邊的voronoi diagram
        v_right = voronoi(p_right) # 得到 右邊的voronoi diagram
        result = merge(v_left, v_right) #合併整個 voronoi diagram  
    return result # return 整個voronoi diagram

* Divide
其實就先將座標點先依X軸再依Y軸排序後，在將一半的的點分給左邊和右邊，
之後在以遞迴的方式下去作就可以了，中止條件是到兩個點後在兩點中間畫一條線。

* Merge
第一步要做的就是找出上切線及下切線，作為下一步找Hyper Plane 的進入點及離開點。而切線的找法就是畫出整個的Convex Hull，然後逐一掃瞄Convex Hull上鄰近的兩個點，當兩個點分別屬於左右半部的點，該線段即為我們要找的切線。而找Convex Hull 的演算法，是Andrew's Monotone Chain找到上凸包以及下凸包。在分別判斷merge後的voronoi diagram的點的convex hull分別位於在還沒merge之前兩邊凸包即可。

* Hyperplane
hyperplane 就是將convex hull 左右兩邊的點找出來並一步一步的往下去找，如果以hyperplane 的中垂線撞到的的中垂線，則構成hyperplane的兩點更新為那兩點，直到所有點構成的convex hull 下切線 ＝＝ hyperplane，diagram 完成。

## 軟體測試與實驗結果
### 執行環境
* 程式語言：python
* 作業系統：windows 11
### 實驗結果

## 結論與心得
原本是想要用c++來寫的，但因為沒用過Qt4，所以改用難度教低的python完成。

## 附錄
我的github 程式碼都在這
https://github.com/wayne9756/voronoi-diagram.git