d(x,p(i))=(普通の距離)/w(i)
として、描いたボロノイ図です。
境界線は円（アポロニウスの円）の一部になります。
重さが小さい方が円の内側になります。
●応用
各点を消防署と見なし、各消防署の消防車の速度が重みの数字として、管轄を決めることができます。
●アルゴリズム
ＭＷボロノイ図の場合、
重みが一番大きい点が最大の領域をとりますので、
点の順番を重みの小さい順に並び替えます
i=1,...,N-1
j=i+1,...,N
i,jでアポロニウスの円を考えます。
円の方程式、iからの距離とjからの距離の比が一定となる円の方程式を求めます。
for x=円の左端,...,円の右端
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)
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
普通のボロノイ図の場合、
i=1,...,N-1
j=i+1,...,N
i,jで垂直二等分線を考えます。
k=1,...,Nただしi,j以外
i,kの垂直二等分線を考えます。
i,jとi,kの線の交点を求めておきます。
next k
i,jの垂直二等分線のx=0の点とx=(画面の幅)の点を交点の配列に追加します。
交点をx座標の小さい順に並べ替えます。
k=1,...,交点の区間数
区間の中点をcとしますが、
cとiの距離をdとします。
h=1,...,Nただしi,j以外
hとcの距離d'とします。
d'<dなら、”駄目”というラベルを与えます。
next h
駄目でなければ、区間の線分をひきます。
next k
next j
next i
●JAVAプログラムのダウンロード(mwvoro.java 8KB)
●VBプログラムのダウンロード(voromwexe.lzh)
ご意見、ご感想、お問い合わせ、お願い等がございましたら、お気軽に、
メール送信フォームからメールを送るか、●掲示板に書き込むか、
どちらかお好きな方法で、ご連絡お願いいたします。
●大山崇のホームページの利用について
●大山崇のホームページ