ドロネー図

母点が隣り合っているとは？

ある母点Aの勢力圏を囲むドロネー辺が、同時に母点Bの勢力圏を囲むドロネー辺であったとします。
このようなとき母点AとBは隣り合っているといいます。

なんか言い方がごちゃごちゃしていますが、要は↓みたいなことです。

(a)は「辺」で繋がっている母点どうしですので「隣り合っている」といえます。
ただし(b)の対角線同士の母点は「点」でつながっているので隣り合っているとはいえません。

ドロネー図

(上の画像はwikipediaよりの引用)
ここで、隣り合っている母点同士をつないだような図をドロネー図といいます。
ドロネー図は通常、上のように三角形の分割になります。このような三角形をドロネー三角形と言います。
「通常」と言ったということは例外もあるということです。三角形でないような分割の図形をドロネー多角形と言います。

ではどのような場合にドロネー三角形になるのかということですが、これは前頁の『退化/非退化』が絡んできます。
非退化というのはボロノイ点のまわりに３つの母点があるような場合でした。
この３つの母点が、ちょうどドロネー三角形の頂点となります。

さて、じゃあ四角形になる場合はどうでしょう。
それはボロノイ図を中心とする同一円周上に、４つの母点が乗っているような場合になります。
これら４つの母点がちょうど四角形の頂点になるわけです。
ここでもしかすると、「四角形の対角線にある母点同士を結べば、三角形分割になるのではないか？」と思われた方もいるかもしれませんが
これは先の図の(b)みたいな感じで対角線同士は点での接触しかしていませんので、これらを結ぶ線は引けないというわけです。

javascript plugin Error : このプラグインで利用できない命令または文字列が入っています。