もう一度(これでだめな時は更新してください。) : 新しい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

高次ボロノイ図(1999年6月19日公開、2010年06月03日22:13:28第19回の改訂)

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


高次ボロノイ図(Higher Order Voronoi diagram)は、普通のボロノイ図を拡張して、"ある場所から2番目、3番目に近いのはどこか?"ということを明らかにした図です。
上のアプレットでは、白い線が1番目に近い領域の境界線で(これは、普通のボロノイ図と一致します。)、緑色が2番目に近い領域の境界線で、紫色が3番目に近い領域の境界線です。
1番目の線分を伸ばすと、2番目が描けます。
●応用
火災や事故の時に、2番目、3番目に近い消防署を知りたい時に使えます。
●プログラムのダウンロード
○Java(hivoro.java 6KB)
○Visual Basic(スクリーンセーバー用)
・スクリーンセーバー(vorohi.scr 17KB)
・Visual Basic Module(vorohi.bas 1KB)
・Visual Basic Project(vorohi.vbp 1KB)
・VBWファイル(vorohi.vbw 1KB)
・Visual Basic Form(voro1hi.frm 9KB)
・Visual Basic Form(voro2hi.frm 2KB)
○BASIC(hivorobas.bas 4KB)
●プログラムの説明
プログラムの簡単な流れは、 1、あらゆる2点の垂直二等分線をひいてください(本当はひかずに、頭の中で)。
2、1本の垂直二等分線に着目します。
その垂直二等分線は、いくつかの別の垂直二等分線とまじわっています。その交点をやはり、ソートしてください。そうすると、垂直二等分線が、いくつかの線分になります。(右端、左端も9999等と適当に与えてください。)
3、そのすべての線分について、線分内の点(ex, 中点)とすべての生成点との距離をはかり、垂直二等分線を作った点が1,2番目(厳密にはどちらも1番目)に近ければ1次(普通のボロノイ図)、2,3番目(厳密にはどちらも2番目)に近ければ2次、、、の線分となります。
4、これをすべての垂直二等分線について行います。

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とします。
            label=0
            h=1,...,Nただしi,j以外
                hとcの距離d'とします。
                d'<dなら、label=label+1
            next h
            labelが「(ひきたいボロノイ図の次数)-1」なら区間の線分をひきます。
         next k
    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とします。
            label=0
            h=1,...,Nただしi,j以外
                hとcの距離d'とします。
                d'<dなら、label=label+1
            next h
            labelが「0」なら、区間の線分をひきます。
         next k
    next j
next i
が大体の流れです。


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


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