d(x,p(i))=(普通の距離)-w(i)
として、描いたボロノイ図です。
境界線は双曲線の一部になります。
重さが小さい方が双曲線の内側になります。
距離が短かったり、重さの差が大きいと、重さが小さい方の領域が消えてしまうことがあります。
●応用
・各点を細菌の発生源として、重みの数だけ時間差がある時の細菌の汚染領域を推定することができます。
●アルゴリズム
ＡＷボロノイ図の場合、
重みが一番大きい点が最大の領域をとりますので、
点の順番を重みの小さい順に並び替えます
i=1,...,N-1
j=i+1,...,N
i,jで双曲線を考えます。これはiからの距離とjからの距離の差が一定となる点の軌跡です。
i,jのx座標,y座標はばらばらでいろんな位置関係にありますが、それでは双曲線の計算が面倒なので、
i,jを回転させて、ｙ座標が同じになるようにします。そして、その中点が原点になるように
平行移動させます。
すなわち、i,jが(-a,0),(a,0)という座標になるようにします。
この座標に対して、双曲線を計算し、この座標を逆の向きに平行移動、回転させることにより、
もとの位置で双曲線を描くことができます。
for x=0から画面の端になるまで
y=xに対する双曲線を計算します
d=(x,y)とiの距離を計算します。
cnt=0とします。
k=1,...,Nただしi,j以外
d_k=(x,y)とkの距離を計算します。
d_k<dならcnt=1 and break
next k
cnt=0ならiが一番近い点なので、plot(x,y)
next x
xのループだけだときれいな双曲線にならないのでyのループを必要に応じて作ります。
やり方はxの場合と同じです。
next j
next i
●プログラムのダウンロード(awvoro.java 8KB)
この他にVisual basicとBasicのプログラムもあります。ご希望の方は大山までメールをください。もちろん無料です。
ご意見、ご感想、お問い合わせ、お願い等がございましたら、お気軽に、
メール送信フォームからメールを送るか、●掲示板に書き込むか、
どちらかお好きな方法で、ご連絡お願いいたします。
●大山崇のホームページの利用について
●大山崇のホームページ