もう一度(これでだめな時は更新してください。) : 新しいNと場所で描き直します。
自動的編普通のボロノイ図MW(乗法的重みつき)
MWの面積
AW(加法的重みつき)
AWの面積
PW(2乗距離加法的重み)CW(重み複合)LW(L_{重み}ノルム)
高次高次MW高次AW高次PW高次CW高次LW
楕円距離マンハッタン最大値カールスルーエ最遠点ボロノイ図
高次楕円距離高次マンハッタン
最遠点マンハッタン
高次最大値高次カールスルーエ高次遠点ボロノイ図
線分
(交わらない線分)
交わる場合もある線分必ず交わる線分多角形の最大空円
高次線分
(交わらない線分)
交わる場合もある線分の
高次線分
必ず交わる線分の
高次線分
ボロノイ領域の面積
MWの面積
AWの面積
ドローネ三角形図2次ドローネ図3次ドローネ図最遠点ドローネ図
ドローネ三角形図の辺を適当に削除したときにできる図ボロノイ辺を伸ばした図
陣取りゲーム(2人用)3人用4人用5人用6人用
クリック編普通のボロノイ図-最大空円
高次
-マンハッタン最大値カールスルーエ最遠点ボロノイ図
高次マンハッタン
最遠点マンハッタン
高次最大値高次カールスルーエ
ボロノイ領域の面積ドローネ三角形図2次ドローネ図3次ドローネ図最遠点ドローネ図
陣取りゲーム(2人用)3人用4人用5人用6人用
注:CW、LW、カールスルーエは重いです。
スクリーンセーバー for Win 95,98

MWボロノイ図(1999年5月7日公開、2010年06月30日22:50:31第20回の改訂)

上はJAVAで作られています。メモリを大量に使ったり、重くなるかもしれません。その時は、ごめんなさい。
実行後に画面をスクロールしたり、アプレット全体が画面に入ってないと、間違った画面になるかもしれないので、気をつけてください。画面の大きさを決めてから”もう一度”をクリックするか、更新(reload)してください。


MWボロノイ図(Multiplicatively weighted Voronoi diagram,乗法的重み付きボロノイ図)はp(i)の重さをw(i)とし、d(x,p(i))を、
d(x,p(i))=(普通の距離)/w(i)
として、描いたボロノイ図です。
境界線は円(アポロニウスの円)の一部になります。
重さが小さい方が円の内側になります。
●応用
各点を消防署と見なし、各消防署の消防車の速度が重みの数字として、管轄を決めることができます。
●アルゴリズム
MWボロノイ図の場合、
重みが一番大きい点が最大の領域をとりますので、
点の順番を重みの小さい順に並び替えます
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)

ご意見、ご感想、お問い合わせ、お願い等がございましたら、お気軽に、
メール送信フォームからメールを送るか、
●掲示板に書き込むか、
どちらかお好きな方法で、ご連絡お願いいたします。


●大山崇のホームページの利用について
●大山崇のホームページ