使い方

ボロノイ図・ドロネー三角形分割の実験室

クリックで三角形や辺を選ぶと、読み取りのパネルに空円性や双対の対応が出ます。点を打つのは右クリック、動かすのはドラッグ、消すのは Shift を押しながらのクリックです。ホイールを回すと図の見た目の倍率が変わり、中ボタンか Space を押しながらのドラッグで図をずらせます。段階のパネルで凸包・ドロネー・ボロノイを選ぶと、選んだところまでが順に積み上がって出ます。

三角形を指すと外接円が出ます。どの三角形の外接円にも他の点は入りません。これが空円性で、ドロネー三角形分割を決めている性質です。辺を指すと、その辺と直角に交わるボロノイ辺が出ます。ドロネーとボロノイは、同じ情報を裏表から見たものです。

あり得る三角形分割のうち、ドロネーはいちばん細い三角形をいちばんマシにするもの、つまり最小角を最大にするものです。点をつなぐ最短の木である最小全域木も、必ずドロネーの辺だけでできています。

点の配り方には、わざと退化させた配置が混ぜてあります。円周・正方格子・同心円では複数の点が同じ円に乗るので、外接円の判定が引き分けになります。正方格子では、正方形をどちらの対角線で割るかが決まりません。同じ格子をわずかにゆらすと引き分けが解けて、向きが確定します。直線では三角形が 1 つもできず、領域は帯になります。そこから 1 点だけ外へ出すと、扇のように三角形が 1 列だけできます。ならすのは各点を自分の領域の重心へ寄せる操作で、繰り返すと領域が六角形へ近づきます。