ドロネー図の構成の仕方

問題を読み替える

今回はドロネー図の書き方を考えていきます。ただし、元となるボロノイ図が非退化であるような場合に限って話を進めます。

ドロネー図といえば、あの三角がいっぱい敷き詰まっている図の事でしたね。
あの三角形、「頂点がある円周上に乗っていて、さらにその円の中には他の母点を含まない(空円性)」という性質があったのは覚えていますでしょうか。

「頂点がある円周上に乗っている」ということは、『円を見つければ、その円の上のどこかに3つの頂点がある』ということになりますね。
ここでさらにすべての円を列挙すれば、円同士の交点が出来がります。交点が出来上がればそれがちょうど、ドロネー三角形の頂点であるといえそうです。
つまり、『ボロノイ図を書いて隣合う母点どうしを繋ぐ』という問題が『空円性を持ち、その円周上に3つ母点を持つような円をすべて列挙する』という問題に変換されたことが分かります。

空円の条件

と、いうわけでこの円の構成方法について考えていきます。一般の点をP(x,y)としましょう。
 F(P_i, P_j, P_k, P)=\begin{vmatrix} 1 & x_i & y_i &x_i^2+y_i^2 \\ 1 & x_j & y_j &x_j^2+y_j^2 \\ 1 & x_k & y_k &x_k^2+y_k^2 \\ 1 & x & y & x^2+y^2 \end{vmatrix} \cdots(1)
という新たな関数を定義します。このとき3点P_i,\ P_j,\ P_kの座標を固定して考えれば、
 F(P_i, P_j, P_k, P)=0
が3点P_i,\ P_j,\ P_kを通る円の方程式を表すことはいいでしょうか。これを満たすようなP(x,y)が平面に円状に分布しているというわけです。

したがってP_i, P_j, P_kがドロネー三角形の頂点となるためには他のあらゆる母点P_l=(x_l, y_l)について
 F(P_i, P_j, P_k, P_l)=\begin{vmatrix} 1 & x_i & y_i &x_i^2+y_i^2 \\ 1 & x_j & y_j &x_j^2+y_j^2 \\ 1 & x_k & y_k &x_k^2+y_k^2 \\ 1 & x_l & y_l & x_l^2+y_l^2 \end{vmatrix} >0 \cdots(2)
が成立すれば必要十分であると分かります。他の母点P_lが円の外にあればよいだろうというわけです。

さらにここでまとめておきましょう。前項において、
『ボロノイ図を書いて隣合う母点どうしを繋ぐ』という問題が『空円性を持ち、その円周上に3つ母点を持つような円をすべて列挙する』という問題になりました。
ここで、後者の条件を数式で書くと式(2)になるということなので、ボロノイ図を書くというのは結局
『式(2)を満たすような円をすべて列挙する。』
という問題に帰着されたというわけです。

次元を上げて考える

上のように問題を手を変え品を変えこねくり回して結局数式に帰着させることが出来ました。この項ではさらに問題をこねくり回して空間上における問題に変換させます。

母点P_iに対して、3次元空間の点P_i^*
 P_i^*=(x_i, y_i, x_i^2+y_i^2)
で定義してみます。
ここで母点の次元を1個上げたS^*=\{P_1^*, P_2^*, \cdots, P_n^*\}という新たな集合が出来ます。
平面で与えられた母点を全部回転放物面に持ち上げたわけです。

ここで3次元上の一般の点P^*=(x,y,z)について
 G(P_i^*, P_j^*, P_k^*, P^*)=\begin{vmatrix} 1 & x_i & y_i &x_i^2+y_i^2 \\ 1 & x_j & y_j &x_j^2+y_j^2 \\ 1 & x_k & y_k &x_k^2+y_k^2 \\ 1 & x & y & z \end{vmatrix} \cdots (3)
という関数を定義します。ここでP_i*,\ P_j^*,\ P_k^*の座標を固定して考えてみますと
 G(P_i*, P_j^*, P_k^*, P^*)=0
P_i*,\ P_j^*,\ P_k^*が通る平面を表しています。したがって
 G(P_i*, P_j^*, P_k^*, P^*)>0
とすれば、P_i*,\ P_j^*,\ P_k^*が通る平面の上の点の集合を表していることになります。

さて、ここで『一般の点』P^*というのを他の母点P_l^*に変えてみます。すると式(3)は、3次元にあげた母点が回転放物面に乗っているという条件を鑑みて
 G(P_i^*, P_j^*, P_k^*, P^*)=\begin{vmatrix} 1 & x_i & y_i &x_i^2+y_i^2 \\ 1 & x_j & y_j &x_j^2+y_j^2 \\ 1 & x_k & y_k &x_k^2+y_k^2 \\ 1 & x_l & y_l & x_l^2+y_l^2 \end{vmatrix}
という関数になります。また
 G(P_i*, P_j^*, P_k^*, P_l^*)=\begin{vmatrix} 1 & x_i & y_i &x_i^2+y_i^2 \\ 1 & x_j & y_j &x_j^2+y_j^2 \\ 1 & x_k & y_k &x_k^2+y_k^2 \\ 1 & x_l & y_l & x_l^2+y_l^2 \end{vmatrix}>0\cdots (4)
というのは、P_i*,\ P_j^*,\ P_k^*以外の母点がすべて平面の上側に存在しているという条件になります。

…この式(4)、最近どこかで見ましたね。そう、式(2)です。
つまり、『式(2)を満たすような円をすべて列挙する。』という問題は、式が同じなので当たり前ですが『式(4)を満たすような円をすべて列挙する。』という問題に切り替えられます。
式の形状は一緒ですが、式の導入は違います。式(2)は空円性より定義しましたが、式(4)は
『次元を上げた母点S^*において、ある3つの母点P_i*,\ P_j^*,\ P_k^*がなす平面よりそれ以外の母点がすべて平面の上側に存在している』
という前提条件で考えて導いたものです。ドロネー図を書くという問題が3次元に来て、↑こんな問題にまで成り変わったわけです。

3次元凸包

いよいよ仕上げです。
『次元を上げた母点S^*において、ある3つの母点P_i*,\ P_j^*,\ P_k^*以外の母点がすべて平面の上側に存在している』
という命題をもう一歩変えてみます。

結論から言ってしまいますと、これ、S^*が3次元の凸包の「下半分」をなしているという条件になります。
卵みたいな形を考えてみてください。これに接平面を付けたとき、この接平面の上というのは卵の内側に向かっているはずです。
つまりドロネー図を書くという問題が
Sの次元を上げてS^*を作り、そのS^*の3次元凸包の下半分を作る。できたら凸包頂点をxy平面に射影する』
という手続きに代わったわけです。3次元凸包の作り方は前項でやりましたから、もうドロネー図は作れるようになったということです。

javascript plugin Error : このプラグインで利用できない命令または文字列が入っています。
最終更新:2012年10月24日 09:39
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。
添付ファイル