もう一度(これでだめな時は更新してください。) : 新しい場所で描き直します。
自動的編普通のボロノイ図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年8月5日公開、2010”N06ŒŽ03“ú22:14:17第7回の改訂)

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


最大値ボロノイ図(英語ではsupremum-metric Voronoi diagramというので、適当な訳かどうかはハナハダ疑問です。)は、2点間の距離を、「x座標の差」と「y座標の差」の大きい方(つまり最大値)として描いたボロノイ図です。
●特殊な例
正方形を形成する母点によるsupremum-metricボロノイ図
放射状に配置された母点によるsupremum-metricボロノイ図1
放射状に配置された母点によるsupremum-metricボロノイ図2
正三角形を形成する母点によるsupremum-metricボロノイ図
正六角形を形成する母点によるsupremum-metricボロノイ図
●応用
不明

アルゴリズムの概要
こちらのボロノイ図のページで紹介している描き方を流用してsupremum-metricボロノイ図を描くことができます。
以下は普通のボロノイ図の描き方の概要です。
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はユークリッド距離。supremum-metricボロノイ図ではsupremum-metric)
            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度の半直線、水平な線分、斜め45度の半直線(これをタイプ1とします) or
          斜め45度の半直線、垂直な線分、斜め45度の半直線(タイプ2とします)
           (See Okabe et al. Soatial tessellations 2nd ed. Fig. 3.7.4)
この組み合わせのタイプは点iと点jのx座標の差とy座標の差の大小関係により決まります。
すなわち、x座標の差がy座標の差よりも大きければタイプ2で
         y座標の差がx座標の差より大きければタイプ1です。
         (なお、差が等しい場合は考慮しておりません。乱数を使って母点を作成しているので、厳密に等しくなることはないので・・・)

それから、ここでは裏技として、タイプ2で登場する垂直な線分(x=?という線分)をy=400x+?としています。
ちょっと反則だとは思いますが、見た目的にOKなのでお許しください。
以上が概略になります。

●プログラムのダウンロード(supr.java 71KB)

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


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