我是使用C#原本就有的PointF型態來儲存點座標，自己額外再建了以下三種結構：

1. Edge：儲存線段的結構

   PointF A;   // 線端點A座標
   PointF B;   // 線端點B座標
   PointF a;   // 做中垂線的點a座標
   PointF b;   // 做中垂線的點b座標
   

2. Voronoi：儲存Voronoi Diagram的結構

   List<PointF> pList;   // 座標點集合
   List<Edge> hpList;    // Hyper Plane 集合
   List<Edge> vList;     // Voronoi 集合
   

3. Record：儲存紀錄的結構，用於Step By Step功能

   List<PointF> pList;   // 點集合
   List<Edge> eList;     // 線段集合
   int type;             // 類型
   bool clear;           // 是否需要清除之前的步驟
   bool enable;          // 是否顯示
   

三角形解法

C#的畫線函數中，必須輸入兩點座標，才能輸出一線段，一開始在考慮三個點所有可能的組合，不是圍成三角形就是三點共線，而三角形又分直角三角形、鈍角三角形和銳角三角形，一開始想到的做法是用外心及每邊的中點，由兩點得到斜率，進而推出直線方程式，最後再求直線碰到畫布邊界的交點，外心與畫布邊界交點的連線即為所求線段。但此種作法會遇到幾個問題：

1. 若是以外心到每邊中點的方向連線，在頓角三角形中，會有一邊產生例外。
2. 直角三角形的外心會落在最長邊的中點上，意思就是只求得出一點，無法以計算斜率來求得直線方程式。

當時在這裡卡了很久，因為只要有一邊求不出除了外心的另一點，就無法畫出線段。

向量解法

後來突然想到高中所學到的「法向量」這個詞，但由於記憶久遠，於是就上網找了很多高中數學來看，整理出可以把三角形的每條邊當作向量來看，那帶公式求出法向量後，就可以由邊的中點加上法向量，求得中垂線上的另一點，就有辦法畫出線了。但另一個問題，畫線的方向還沒解決，但當時想說「向量」顧名思義就是有方向性，點A-點B 與 點B-點A 代表的就是兩個相反的方向，那麼算出來的法向量，也就必然會有兩種方向，於是就試著找出每種三角形求出法向量後的共同點，發現只要一開始在計算三角形的各邊向量時，都以逆時針方向來計算，所求得的法向量就會往三角形外射出，而且不管任何三角形都一樣！那麼很明顯的，要求出逆時針方向的向量，一開始的三個點座標就必須經過排序，而且是依照逆時針來排序點。

但其實在這之前完全沒想過點也有逆時針和順時針排序的問題，所以後來又上網查了高中數學，很不巧的看到「右手定則」這個詞，突然想到這好像跟順時針和逆時針有關係，仔細閱讀下發現，可以用兩向量的外積來求得其旋轉的方向，以右手來說，四指為逆時針方向時，大拇指往上指，代表外積為正，相對的若為順時針，外積則為負。所以後來就以三角形的重心為基準點，來求出個點的方向作排序，不過這邊要特別注意，因為程式的座標軸系統，與平常用的不太一樣，所以其實是適用「左手定則」，外積為負才是逆時針旋轉。

無窮遠邊

所以，有了外心以外的另一點後，便可計算直線方程式，再帶入畫布邊界的四種 Case：(0, ?), (?, 0), (?, y_max), (x_max, ?) 求出的 x 或 y 若在 0 ~ max 之間，代表與該邊界有交點，就能畫出Voronoi的線段了。

後來在同學的提醒下，發現評分規則有寫到要允許輸出的邊能超出畫布邊界，當時一直沒辦法理解這句話是甚麼意思，後來才想到三點的 Voronoi Diagram 的邊是向外無窮延伸的，其實我在前面用中點加法向量求得另一點時，就可以先將法向量乘以數倍，再加到中點，即求得也是在中垂線上無窮遠的一點座標，就不用再解方程式來求交點那麼麻煩了，於是最後就改成後面這種方法，來畫出三個點的Voronoi Diagram。

外心

後來在輸入各種測資的時候，發現帶外心公式有時候還是會算不出來，不過這很明顯就是斜率的問題，所以就想到解聯立還可以用克拉馬公式來解，並且也不會有分母無窮大或為零的問題。

兩點

寫到這裡就大概想得出兩點該如何做了，就是將中點分別加上正和負的數倍法向量，即可求出中垂線上兩點座標。

三點共線

而三點共線的情況，我是用三點座標求三角形面積必為零的式子來判斷，把各點排序過後，其畫線的做法其實就與兩點畫線是一樣的。

在寫多點的Case前，雖然看得懂投影片中求 Voronoi Diagram 的演算法，但要轉換成程式實在沒有一點頭緒，於是就先整理整個流程，並寫寫看虛擬碼來釐清思緒：

演算法

1. 切割：將座標點排序後，把所有座標點分割成左右兩半
2. 求 Voronoi Diagram：將左右兩部分，分別求出Voronoi Diagram
3. 求上下切線：求出全部點的Convex Hull，找出橫跨左右兩部分的邊，即為上下切線
4. 求 Hyper Plane：由一切線做中垂當進入點，撞到VD則轉彎，轉彎的方向如圖所示，最後由另一切線離開
5. 消線：看HP往哪個方向轉，就往哪個方向的VD消掉

虛擬碼

edgeList Voronoi(PointList)
{
	If(PointList.Count == 1)
		return;
	else if(PointList.Count == 2)
		result = Voronoi_two(PointList);
	else if(PointList.Count == 3)
		result = Voronoi_three(PointList);
	else if(PointList.Count > 3)
    {
	    Divide(PointList, Point_Left, Point_Right);
	    vl = Voronoi(Point_Left);
	    vr = Voronoi(Point_Right);
	    result = Merge(vl, vr);
    }
    return result;
}

寫完後發現對整個流程有比較清楚，如果之前三個點以下的Case有寫好，就可以直接拿來用，於是就開始著手第一個Divide的功能。

Divide

其實就先將座標點先依X軸再依Y軸排序後，再將索引小於座標點總數除以2的點，分配到Point_Left，其餘分配到Point_Right就完成了。

之後分別對左右兩部分的點求Voronoi Diagram，進入遞迴的部分，最後一步就是將左右兩半部的圖Merge起來。

Merge

第一步要做的就是找出上切線及下切線，作為下一步找Hyper Plane 的進入點及離開點。而切線的找法就是畫出整個的Convex Hull，然後逐一掃瞄Convex Hull上鄰近的兩個點，當兩個點分別屬於左右半部的點，該線段即為我們要找的切線。找Convex Hull 的演算法，我是參考演算法筆記的Jarvis' March演算法去做修改，因為在有共線的情況下，共線上的點並不屬於Convex Hull的點，但這樣最後找出來的上下切線就會有誤，所以就必須修改Convex Hull的演算法，想辦法讓共線上的點也能一併加入。Jarvis' March演算法是先從凸包上一點開始做起，然後掃描每個點，找旋轉角度最大或是共線時距離最遠的點，作為下個要連接的點。那要共線時中間的點也要連接，第一個想法就是把共線時找最遠的點改成找最近的點，但如果是一列漸遠的點，這樣搜尋時找最近點時，就有可能會往回找，所以第二個想法就是要標記走過的點。但還有一種情況是當所有的點都是共線時，必須讓Convex Hull再原路折回來，才能找到對的切線，所以走訪過所有點後，如果判定全部點共線，就清空走訪的紀錄，往回搜尋，但我在這邊使用偷懶的作法，只要判定全部共線，就直接複製一份已經找出的Convex Hull點，倒著加入Convex Hull，然後起始點不加即可得到相同結果。

Hyper Plane

可以想成Hyper Plane是由很多線段的中垂線連接而成，那第一條Hyper Plane其實就是一切線的中垂線，將中垂線由圖形外的無窮遠處往圖形方向畫，撞到Voronoi Diagram就要轉彎，「撞到」的意思就是判斷兩線段有沒有交點，可以參考演算法筆記的做法，「轉彎」就是必須找下一個線段的中垂線，那麼就可以想像成有一條掃描線，掃描線一開始等於切線，撞到Voronoi Diagram後就要移動掃描線，那麼要如何移動掃描線？我是依照投影片的做法，一次只會移動掃描線段的其中一點，而移動的點就是每次撞到的Voronoi Diagram所平分的兩點。因為在作三點Case時還沒考慮到這個，所以就去Edge的資料結構新增這兩點的資訊，並在求Voronoi Diagram時順便加入這兩點資訊，其實比我想像中的還快，沒有動到太多原本寫的程式。能移動掃描線後，就直接從上一條Hyper Plane的轉彎點繼續畫，再去尋找下個撞到的Voronoi Diagram，這種接著畫Hyper Plane做法，最後就不用再另外消Hyper Plane，我是覺得比較方便也比較直覺。最後Hyper Plane就會由另一切線離開圖形。

消線

我是以Hyper Plane撞到Voronoi Diagram後，轉彎的方向來判斷，以轉彎前的線段(H1H2)和轉彎後的線段(H1H3)求外積，若為逆時針旋轉，則將該方向的Voronoi Diagram線消掉(H1H2與H1P作外積也為逆時針)，消掉的意思就是將該側線段的座標，更新為轉彎的那點座標，即可達到消線的目的。在求Hyper Plane時就可以先將有撞到的線段記錄下來，在消線時就可以只掃描這幾條線段即可。

以上作法應該就可以解決所有四個點的Case，但如果針對多點，由這個網站前面的範例就可以看到，左右半部超出Hyper Plane的線段不僅限於一條無限延伸的線，有可能左半部Voronoi Diagram的交點位於右半部，如此每次要消的線段就不只一條，還要繼續搜尋消掉的線有沒有延伸下去的線段，有的話就都要刪除，但後來因為時間關係，加上還沒想出把所有延伸線段都刪除的方法，我只能消掉原本就要消的線，和他延伸的第一條線，所以在多點時的某些Case還是可以很明顯地看到有沒消掉的線，是比較可惜的地方。

特殊情況

另外還有些比較難發現，也不一定會遇到的問題，就是「誤差」問題。如果座標是用浮點數去存，只要經過除法或乘法運算，小數點就有可能產生誤差，即使妳的浮點數存的看起來像整數（Ex: 120.00, 25.00…），所以在經過求兩線段的交點公式後，就有機率產生誤差，造成有時候求出兩線段的交點，但該交點卻不在兩線段上。若以我上面的作法來解四個點的Case，會遇到誤差的地方只有四個點圍成正方形的時候，我目前遇到誤差的解法都是再想其他方法，盡量避免出現「計算出來的點和另一點是否重疊」，或是「計算出來的點是否在某線段上」等判斷，網路上大部分的做法就是去允許誤差，但允許誤差的範圍就很重要，如果範圍太大，那原本輸入的點座標若有兩個很靠近的點，程式就會視為同一點，造成結果不如預期。

我Step By Step的作法是有點像PhotoShop圖層的概念，一層一層疊上去，也可以把特定的步驟隱藏起來。我使用自定義的Record結構，當程式執行到有需要畫出來的圖形的步驟，就將該圖形存入Record List中，最後在一步一步印出即可。但在某些時候就必須清除之前步驟的圖形，畫面才不會全都重疊再一起而顯得雜亂，像是左右兩個Convex Hull 合併為一個的時候，就要刪除左右兩個小的Convex Hull，以及消線時要把原本左右兩半部的Voronoi Diagram清掉，才看得出消線的結果，所以每次按下Step By Step所要印出的圖形，就可以整理出以下規律：

合併	步驟	類型	其他
I	①	Voronoi (左)
	②	Voronoi (右)
	③	Convex Hull(左)
	④	Convex Hull(右)
	⑤	Convex Hull(合併)	隱藏③ ④
	⑥	Hyper Plane
	⑦	Voronoi (消線後)左)	隱藏① ② ⑤
	⑧	Merge (合併HP和VD的結果)	隱藏⑥ ⑦，成為II的①
II	②	Voronoi (右)
	③	Convex Hull(左)
	④	Convex Hull(右)
	⑤	Convex Hull(合併)	隱藏③ ④
	⑥	Hyper Plane
	⑦	Voronoi (消線後)左)	隱藏① ② ⑤
	⑧	Merge (合併HP和VD的結果)	隱藏⑥ ⑦

若點集合總共切成兩部分，即為8個Step；若切為三個部分，則做完前八個Step產生的Merge圖形，將視為與第三部分合併的Voronoi(左)，即為8+7個Step；若切成四個部分，則第一部分與第二部份會先合併，第三和第四也會先合併，最後再全部合併，也就是8+8+6個Step。