使い方

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

クリックで点を打ち、ドラッグで動かし、Shift を押しながらクリックすると消えます。段階のパネルで凸包・ドロネー・ボロノイを選ぶと、選んだところまでが順に積み上がって出ます。

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

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

点の配り方のうち、円周と直線はわざと退化させた配置です。共円ではすべての点が 1 つの円に乗るので、外接円の判定が引き分けになります。共線では三角形が 1 つもできず、領域は帯になります。ならすのは各点を自分の領域の重心へ寄せる操作で、繰り返すと領域が六角形へ近づきます。