母点が隣り合っているとは?
ある母点Aの勢力圏を囲むドロネー辺が、同時に母点Bの勢力圏を囲むドロネー辺であったとします。
このようなとき母点AとBは隣り合っているといいます。
なんか言い方がごちゃごちゃしていますが、要は↓みたいなことです。
(a)は「辺」で繋がっている母点どうしですので「隣り合っている」といえます。
ただし(b)の対角線同士の母点は「点」でつながっているので隣り合っているとはいえません。
ドロネー図
(上の画像は
wikipediaよりの引用)
ここで、隣り合っている母点同士をつないだような図をドロネー図といいます。
ドロネー図は通常、上のように三角形の分割になります。このような三角形を
ドロネー三角形と言います。
「通常」と言ったということは例外もあるということです。三角形でないような分割の図形を
ドロネー多角形と言います。
ではどのような場合にドロネー三角形になるのかということですが、これは前頁の『退化/非退化』が絡んできます。
非退化というのはボロノイ点のまわりに3つの母点があるような場合でした。
この3つの母点が、ちょうどドロネー三角形の頂点となります。
さて、じゃあ四角形になる場合はどうでしょう。
それはボロノイ図を中心とする同一円周上に、4つの母点が乗っているような場合になります。
これら4つの母点がちょうど四角形の頂点になるわけです。
ここでもしかすると、「四角形の対角線にある母点同士を結べば、三角形分割になるのではないか?」と思われた方もいるかもしれませんが
これは先の図の(b)みたいな感じで対角線同士は点での接触しかしていませんので、これらを結ぶ線は引けないというわけです。
javascript plugin Error : このプラグインで利用できない命令または文字列が入っています。
最終更新:2012年10月21日 10:09