Voronoi Diagram

網路上論Voronoi Diagram的文章不多(中文), 但國外倒是很多這樣子的文章在討論, 這問題是由Voronoi解掉的, 其實用於細胞及一些最近群組的問題是非常有用的..

 

問題的定義如下:
平面上有一群點S集合, 分別找出兩兩最近的點並找出其兩點的中垂線, 此圖型為Voronoi Diagram.

問題在於找線, 所以解法也算簡單…先把平面上所有的點都sort過(依距離), 這樣就可以直接找下個點做中垂線。
Ans:
Let Point = (x, y), Let Line = (Point₁, Point₂)
For all point in S, pick nearest 2 point a and b,
Find the mid-point Point_c = Point_a + Point_b / 2; => Point_c = ((x_a + x_b) / 2, (y_a + y_b) / 2);
Find the normal vector Point_n = (-(x_b – x_a), y_b - y_a);
Find the line Line = (Point_c, Point_c + Point_n);
之後就請自己展開吧。 全部都只有用到高中數學, 一點一法向量可形成一線的概念而已。
高中對於平面(空間中也是)直線的定義, 其中一個就是, 一點(x, y), 一向量n, 那麼一線就可以表示為 (x, y) + tn; 其中t屬於任意實數。這好似叫做直線參數式。

解完之後要畫在平面上, 那麼就要有更多的算法, 不過這些算法都不是Voronoi Diagram的精神, 都是求解兩線交點, 還有平面中最近區域, 以及包凸演算法了。

PS: 為何會忽然想到這個演算法呢? 那是因為前幾天, 同事忽然show了blow up的放大, 就想到這個演算法了。
http://www.alienskin.com/blowup/index.aspx