● Voronoi Diagram
○ 為各點間中垂線(perpendicular bisector)構成的圖案，包含VD points, VD edges (多邊形的點和邊)
○ 各 p1,p2,p3 三條中垂線交叉點為 p1,p2,p3 三角形的外心(circumcenter)
1.外心到三角形三頂點等距離
2.鈍角三角形外心在三角形面積之外，為外接圓的圓心
○ 中垂線可為出某點的勢力範圍，當有外來點，可馬上看出離那些本來點最近
● VD Divide-and-Conquer
○
輸入: 點的集合
輸出:VD的描述
步驟一: 如果只有一個點則回傳，終止條件
步驟二: resursion尋找 median line,將點分為兩集合Sl,Sr
步驟三: 分別找出兩集合的VD
步驟四: merge, 找出piece-wise linear hyperplane (HP)
步驟五: 接下來使用 resursion 來完成整個 VD
○ merge
輸入: 兩個集合Sl,Sr
輸出: Sl,Sr 連集(S)的 VD
步驟一: 分別找 Sl 和 Sr 的 convex hull，hull(Sl)，hull(Sr)
步驟二: 尋找使 hull(Sl)，hull(Sr) 合成 hull(S) 的兩個線段PaPb，PcPd (PaPb 在 PcPd之上),
int x = a
int y = b
SG = PxPy
HP = 線段(由兩點定義pair point)空集合
步驟三: 尋找 SG 中垂線 , 把它叫做 BS，將 HP 與 BS 連集，若此時SG = PcPd 則跳去步驟五，
否則步驟四
步驟四: BS與VD(Sl) 或 VD(Sr) 射線(Pz射出的射線)的第一個交點，此交點必為BS與PxPz或是
PyPz的中垂線之焦點，若為與PxPz之焦點，則下一個SG = PyPz；反之，若為與PyPz之焦點，
則下一個SG = PxPz，回到步驟三
(次處藍字應該是錯誤的)比較Px與Py較高點(座標上y值較大)，
較高點與Pz形成線段(PxPz或PyPz)，多於截掉，若為 PxPz 則 SG = PxPz ,反之亦然，回到步驟三
步驟五: 截掉 VD(Sl)與 VD(Sr)中超過HP的線段，輸出最終答案
截掉Sl中掉到HP右邊的線段；截掉Sr中掉到HP左邊的線段
S = Sl聯集Sr
○ 利用VD建立convex hull (O(n)time)
步驟一: 檢查所有VD的邊找出所有無限射線
步驟二: 無限射線左邊的點為convec hull起點P
步驟三: 以點P為準順時鐘找下一個無限射線
● 由原始 n 個點畫成的 VD 特性:
○ #VD edges ne <= 3n-1
○ #VD vertices nv <= 2n-4
○ (n + 1) - ne+nv = 2
● 有一種表示所有 VD 明確資料值極端式為以下:
the list of all Vornoi vertices on its boundary,
the list of all Vornoi edges on its boundary,
the list of all contiguous Vornoi polygons on its boundary,etc
● 但此方式會耗費相當大的space,因此我們可用 winged-edge data structure ( / polygons data structure)
此資料結構為幾何模型或電腦圖像中常見的標準資料結構 (e.g. baungart, ballard and brown,hoffmann), 可傳達關於 Vornoi 的
點, 邊, polygons 的明確的在目前發生率
○ 紀錄 VD 的點 the set P = {p1,...,pn} of n generator
○ n個點可以形成 n+1 個區塊，或是 n 個無限區塊(?)
○ polygon i (i = 1,2,3,...,ne,∞)的表達為:
1. edge.around.polygon[i] : 為此 polygon 邊界的任一個 edge 編號
○ polygon 的 vertex j (j = 1,2,...,nv)的表達為:
edge.around.vertex[j]: 以此 vertex 為起始或終點(都可?)的 edge 編號
● Voronoi Diagram資料結構 -winged-edge data structure
edge k 編號(k = 1,2,3...ne , ne為edge的數量 )的紀錄方式為以下:
1. start.vertex[k]: 內容為vertex編號，線段起始點
2. end.vertex[k]: 內容為vertex編號，線段終點
3. right.polygon[k] : edge k的右邊區域，內容為一個依序增加的int area_index區域號 >> 使其為使用者輸入的點的編號
4. left.polygon[k] : edge k的右邊區域，內容為一個依序增加的 int area_index區域號>> 使其為使用者輸入的點的編號
(3,4可以判斷不同點的左右區域/勢力範圍是否重疊)
5. cw.predecessor[k] : 從起始點順時鐘(以12點鐘方向開始)遇到的第一個邊的int edge_index邊編號(k')
6. ccw.predeccessor[k] : 從起始點逆時鐘(以12點鐘方向開始)遇到的第一個邊的int edge_index邊編號(k')
7. cw.successor[k] : 從終點順時鐘(以12點鐘方向開始)遇到的第一個邊的int edge_index邊編號(k')
8. cw.successor[k] : 從終點逆時鐘(以12點鐘方向開始)遇到的第一個邊的int edge_index邊編號(k')
9. edge.around.polygon[i] : 為此 polygon 邊界的任一個 edge 編號
(polygon i 為點的勢力範圍編號(i = 1,2,3,...,n,∞))
10. edge.around.vertex[j]: 以此 vertex 為起始或終點(都可?)的 edge 編號
(polygon 的 vertex j (j = 1,2,...,nv) ，包含無限值的點)
11. vertex[j]: 紀錄 Point points_poly(x,y) = points_poly[points.Couting]
(polygon 的 vertex j (j = 1,2,...,nv) ，無限值都轉為邊界值)
12. w.vertex[j] : 記錄點為無限0還是有限1
● 得到 Voronoi Diagram資料結構 -winged-edge data structure
留言列表
