もう一度(これでだめな時は更新してください。) : 新しい場所で描き直します。
自動的編普通のボロノイ図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

マンハッタンボロノイ図(2000年7月22日公開、2010年06月03日22:13:32第8回の改訂)

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


マンハッタンボロノイ図は、マンハッタン島のように、道路網が碁盤の目のようになっていると仮定して作ったボロノイ図です。人々は移動するとき縦と横にしか動けません。斜めには動けません。(数学的には、2点間の距離は、「x座標の差」+「y座標の差」となります。)
境界線は垂直な線か水平な線か45度の線の折れ線になります。面白いですね。
●特徴的な配置の場合の図
母点が正方形を形成するように配置されている場合のボロノイ図
母点が放射状に配置されている場合のボロノイ図1
母点が放射状に配置されている場合のボロノイ図2
母点が正三角形を形成するようにに配置されている場合のボロノイ図2
母点が正六角形を形成するようにに配置されている場合のボロノイ図2
●応用
碁盤の目のような道路のネットワークがある地域で施設の圏域を知りたい時に使えます。

アルゴリズムの概要
こちらのボロノイ図のページで紹介している描き方を流用してマンハッタンボロノイ図を描くことができます。
以下は普通のボロノイ図の描き方の概要です。
i=1,...,N-1
    j=i+1,...,N
        p(i)とp(j)の境界線(普通のボロノイ図では垂直二等分線)を考えます。
        k=1,...,N ただし i,j以外
            p(i)とp(k)の境界線を考えます。
            (i,j)の境界線と(i,k)の境界線の交点を計算します。
        next k
        交点の配列にi,jの境界線のx=0とx=(画面の幅)の点を追加します
        x座標の小さい順に交点を並び替えます。
        k=1,...,交点の数
            cを交点と次の交点の中点とします
            dをd(c,p(i))とします。(普通のボロノイ図ではdはユークリッド距離。マンハッタンボロノイ図ではマンハッタン距離)
            h=1,...,N ただし i,j以外
                d'をd(c,p(h))とします
                If d'<d then アウトです
            next h
            If アウトでなければ, then 交点と次の交点を結びます。
         next k
    next j
next i

これを流用するのですが、ポイントはマンハッタンボロノイ図の境界は直線ではないということです。
すなわち、水平な半直線、斜め45度の線分、水平な半直線(これをタイプ1とします) or
          垂直な半直線、斜め45度の線分、垂直な半直線(タイプ2とします)
           (See Okabe et al. Soatial tessellations 2nd ed. Fig. 3.7.2)
この組み合わせのタイプは点iと点jのx座標の差とy座標の差の大小関係により決まります。
すなわち、x座標の差がy座標の差よりも大きければタイプ2で
         y座標の差がx座標の差より大きければタイプ1です。
         (なお、差が等しい場合は考慮しておりません。乱数を使って母点を作成しているので、厳密に等しくなることはないので・・・)

それから、ここでは裏技として、タイプ2で登場する垂直な半直線(x=?という直線)をy=400x+?としています。
ちょっと反則だとは思いますが、見た目的にOKなのでお許しください。
以上が概略になります。
●プログラムのダウンロード(man.java 70KB)

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


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