計算幾何（凸包・ドロネー・ボロノイ）
平面に置いた点から、凸包・ドロネー三角形分割・ボロノイ図を作る様子を見せます。ギフト包装法とグラハムスキャン、ボウヤー・ワトソン法を 1 手ずつ進め、点を足したり消したりして形の変化を確かめられます。
点を頂点とする三角形に分け、どの三角形の外接円にもほかの点が入らないようにしたものです。細長い三角形ができにくく、地形の表現や有限要素法のメッシュに使われます。
点 30 / 200 個。図の何もないところを押すと点を足し、点を押すと消します。
大きな三角形の頂点につながる三角形を取り除いて完成（三角形 50 個）
数
- 点の数 n
- 30
- 三角形
- 50 個（2n − 2 − h = 50）
- 辺
- 79 本（3n − 3 − h = 79）
- 一番小さい角
- 1.4°
凸包の頂点が h 個のとき、三角形の数と辺の数は分け方によらず決まります（一直線に並ぶ点がない場合）。ドロネー三角形分割は、その中で一番小さい角を最大にする分け方です。
使い方
- 上のボタンで、凸包・ドロネー三角形分割・ボロノイ図を切り替えます。
- 図の何もないところを押すと点を足し、点を押すと消します。例のボタンで、ランダムな点や円の上の点などをまとめて置けます。
- 凸包とドロネー三角形分割は、再生や ◀ ▶（キーボードの ← →）で 1 手ずつ進められます。速さも選べます。
- 凸包の図では、青い円が今の頂点、青の破線が今の候補、橙が調べている点、赤い × が取り除いた点です。ドロネー三角形分割の図では、赤が外接円に新しい点が入ったので取り除く三角形、紫が作り直した三角形です。
しくみ
計算幾何のアルゴリズムの多くは、「3 点 a → b → c が左回りか右回りか」（向きの判定）と、「点 d が 3 点 a, b, c を通る円の内側にあるか」（円の判定）という 2 つの判定の組み合わせでできています。どちらも座標の掛け算と引き算だけで計算でき、角度や三角関数は要りません。
ボウヤー・ワトソン法は、点を 1 つずつ加えるたびに、外接円がその点を含む三角形（ドロネーの条件を満たさなくなった三角形）をまとめて取り除き、できた穴を新しい点と結んで埋め直します。最初はすべての点を囲む大きな三角形から始め、最後にその頂点につながる三角形を取り除きます。このアプリでは、大きな三角形の頂点を無限に遠い点として扱い、凸包の近くの三角形が欠けないようにしています。
ボロノイ図は、携帯電話の基地局の受け持ち範囲、一番近いコンビニの地図、結晶や生物の細胞の形など、身の回りのあちこちに現れます。ドロネー三角形分割の各三角形の外接円の中心がボロノイ図の頂点になり、隣り合う三角形の中心を結ぶとボロノイ図の辺になります。