※ 引述《Jerry (告別十九歲)》之銘言：
: 天哪!
: 如果只花一天, 要我"多麼勉強"地"打"好我都心甘情願....
嗯... 說說那個 "鄰居" 要怎麼找吧... :)
我是先把哪個是哪個的鄰居找到, 然後再把圖給畫出來,
其實, Voronoi diagram 和 Delaunay triangle 是 dual,
只要找出一個就相當於找到了另一個~~~ ^__^
暴力法也很簡單打, 只要任找相異三點, 在那三點所構成的圓內如果
沒有其他的 vertex 在圓內就表示它們是一個 Delaunay triangle,
也就是說那三個點互為鄰居. ^.^
所以如果用 "Divide & Conquer" 的方法, 原理大概也差不多,
除了 Supporting Lines 屬於 "Convex Hull", 它的 edge 只有對應
到一個 Delaunay triangle 外, 其他的都有對應到"兩"個 D triangle.
即 1(Supporting Line) -> 2 -> 2 -> ... -> 2 -> 1
所以我們只要從 Supporting Line 找下去就好了~ :D
要找下一個 D triangle, 只要先固定兩個點, 在對它們的鄰居分別
找"構成圓半徑最小的", 如果把找過的點拿掉(也就是上一個
D triangle 的那個點), 那就是下一個 D triangle 啦~
它的外心也就是 Separation Chain 的下一個交點囉~~~ ^_^
我覺得在打這個程式, 應該是"不知道要怎麼做"所花的時間會比較多,
真的想清楚了, 也就不會覺得難啦... 呵... Good Luck~~~
--
※ 發信站: 批踢踢實業坊(ptt.m8.ntu.edu.tw)
◆ From: Action.m8.ntu.e