ここでいうある点とは線の上のことで、線の上からみると、最も遠い点が２点あり、その２点は、線のまん中あたりに”,”付きで書いてある点です。３本の線が交わる点では一番遠い点が３つあります。
図の中で一部の点しか、領域を持ちません。また、領域があれば、その領域の面積は無限大です。
高次ボロノイ図での(N-1)番目の境界線を描いたことと同じです。
●応用
・各点をゴミ処理場などの嫌われることが多い施設の候補地と見なして、どこに置いたら良いかを考える時などに使います。
・センター問題
●アルゴリズム
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とします。
cnt=0
h=1,...,Nただしi,j以外
hとcの距離d'とします。
d'<dなら、cnt=cnt+1
next h
cnt=N-2ならば、区間の線分をひきます。
next k
next j
next i
●プログラムのダウンロード(fpvoro.java 6KB)この他にVisual basicとBasicのプログラムもあります。ご希望の方は大山までメールをください。もちろん無料です。
ご意見、ご感想、お問い合わせ、お願い等がございましたら、お気軽に、
メール送信フォームからメールを送るか、●掲示板に書き込むか、
どちらかお好きな方法で、ご連絡お願いいたします。
●大山崇のホームページの利用について
●大山崇のホームページ