もう一度(これでだめな時は更新してください。) : 新しいNと場所で描き直します。
注：ＣＷ、ＬＷ、カールスルーエは重いです。
線分ボロノイ図(2009年6月8日公開、2011年01月23日13:29:58第13回の改訂)
●注意
上はＪＡＶＡで作られています。メモリを大量に使ったり、重くなるかもしれません。その時は、ごめんなさい。
実行後に画面をスクロールしたり、アプレット全体が画面に入ってないと、間違った画面になるかもしれないので、気をつけてください。画面の大きさを決めてから”もう一度”をクリックするか、更新(reload)してください。
線分ボロノイ図は母点が点ではなく線分のボロノイ図です。時には、線分ではない点がまざっている場合もあるようです。
母点が点の場合、境界線は２つの点の垂直二等分線になりますが、母点が線分の場合、複雑になります。
ボロノイ図は、最も近い母点はどこか調べるのに有用なツールですので、「近い」という言葉の意味を定義しないといけません。「近い」とは線分までの距離が小さいことと定義します。じゃぁ、線分までの距離が近いとはどういうことか決めなくてはいけません。ここでは、ある点から線分までの距離をある点から線分の中で一番近い点までの距離と定義します。すなわち、任意の点xから線分Lの距離d(x,L)を
d(x,L)＝min_{yはL上の点}d(x,y)
と定義します。これは、xとLの端点のどちらかまたはxからLへの垂線がぶつかる点の3つの点の距離の最小値ということになります。
さて、２つの線分の位置関係によってもかわりますが、境界線はどうなるでしょうか。２つの線分にはさまれているようなエリアでは、境界線は２つの線分の角の二等分線になります。片方の線分と片方の線分の端点に挟まれたエリアでは、放物線（ある線とある点からの距離が等しい点の軌跡）になります。また、２つの線分の端点が一番近いような場所では普通の（点の）ボロノイ図と同様に垂直二等分線になります。
●アルゴリズム
線分がN本あるとします。
i=1,...,N-1
j=i+1,...,N
i,jで境界線を考えます。
1) 最初に端点同士で垂直二等分線を考えます。
1-1) iの左側の端点とjの左側の端点で端点同士の垂直二等分線を計算します。
1-2) iの右側の端点とjの右側の端点で端点同士の垂直二等分線を計算します。
1-3) iの左側の端点とjの右側の端点で端点同士の垂直二等分線を計算します。
1-4) iの右側の端点とjの左側の端点で端点同士の垂直二等分線を計算します。
これらの4つのケースに対して、端点同士の垂直二等分線の式y=ax+bのaとbを計算します
for x=画面の左端 to 画面の右端 step 画面のキメの細かさ
y=ax+bを計算
(x,y)とi,jの端点との距離dを計算します。(iへの距離とjへの距離は垂直二等分線なので同じであり、片方のみ計算すればOKです。)
d_epsiとして(x,y)とi*0.999+j*0.001となる点への距離を計算します。これはiからほんの少しだけjより移動した線分上の点を意味します。
d_epsjとして(x,y)とj*0.999+i*0.001となる点への距離を計算します。これはjからほんの少しだけiより移動した線分上の点を意味します。
if d_epsj<d or d_epsi<d then next x
for k=1,...,N but not i,j
d_kとして(x,y)とkへの距離を計算します。ｋの端点への距離と垂線が交わる点の距離を計算します。（もし垂線が交わる点が線分の外であれば、この距離は不要になります。）
if d_k<d then next x
next k
(x,y)は境界になりうるので、(x,y)にプロットします。
next x
2) 次にiとjの線分に挟まれた場所の境界線を考えます。すなわち、角の二等分線のイメージになります。
iとjに対して角の二等分線は２つあるので、これらを(gux1,guy1)-(gux2,guy2)と(gux3,guy3)-(gux4,guy4)の形で計算します
2-1) (gux1,guy1)-(gux2,guy2)について計算する
(gux1,guy1)-(gux2,guy2)の線分をy=ax+bの形であらわすようにa, bを計算
for x=gux1 to gux2
y=ax+bを計算
線分iと(x,y)からiにおろした垂線の交点を計算
この交点が線分iの外側ならnext x
線分jと(x,y)からjにおろした垂線の交点を計算
この交点が線分jの外側ならnext x
dとして(x,y)とiの距離を計算（(x,y)とjの距離と同じ）
for k=1,...,N ただしi,j以外
d_k=線分kと(x,y)の距離を計算
d_kがdより小さければnext x
next k
(x,y)は境界になるのでプロットする
next x
2-2) (gux3,guy3)-(gux4,guy4)について計算する。これはi,jのもう一方の角の二等分線なので、
2-1)と同じロジックで計算、描画を行います。
3) 最後に線分ともう一方の線分の端点の境界を考えます。この場合、線と点からの距離が等しい軌跡ということで境界線は放物線になります。
3-1) 線分iと線分jの左端
3-2) 線分iと線分jの右端
3-3) 線分jと線分iの左端
3-4) 線分jと線分iの右端
これらの４つのケースに対して、以下の考え方を適用します。
もし準線をx=-lp、焦点を(lp,0)とすると、放物線の式はy^2=4lpxとなります。
まずlpを線分iとjの端点までの距離の半分とします。
線分iとjの端点を線分iの角度だけ回転させます。それから、jの端点と、そこからiにおろした垂線の交わる点の中点が原点になるように平行移動させます。そうすることにより線分iとjの端点を使って、y^2=4lpxの式を作ることができます。
あとで、y^2=4lpxの各点に対して、逆の回転と逆の平行移動をすれば、もとの線分と点の位置に対して放物線を書くことができます。
(gpboriginx,gpboriginy)を計算します。これは線分iとjの端点で放物線を描くときの原点。y^2=4lpxの式で表す際に平行移動させるｘ方向、ｙ方向の座標をあらわします。
gpbijepを計算します。こえｒは線分iとjの端点の境界線放物線をy^2=4lpxであらわすときのlp
gpbijethetaを計算します。これは線分iとjの端点の境界放物線をy^2=4lpxであらわすときに回転させる角度
for(y=-画面の高さ to 画面の高さ
x=y^2/(4lp)を計算
(x,y)を回転した分だけもとに逆回転させ、平行移動した分ももとに戻します。
dを(x,y)とjの端点の距離とします
daを(x,y)ともう一方の端点との距離にします。
if da<d then next y
depsを(x,y)と端点*0.999+もう一方の端点*0.001の距離とします。すなわち、微妙に内側に入った点を意味します
if deps<d then next y
for k=1,...,N but not i,j
d_kをkと(x,y)の距離とします。
if d_k<d then next y
next k
Plot (x,y)
next y
next j
next i
●プログラムのダウンロード
○Java(segvoro.java)
○VB版ファイルおよびexeファイル(svoro.lzh)
ご意見、ご感想、お問い合わせ、お願い等がございましたら、お気軽に、
メール送信フォームからメールを送るか、
●掲示板に書き込むか、
どちらかお好きな方法で、ご連絡お願いいたします。
●大山崇のホームページの利用について
●大山崇のホームページ