コンピュータジオメトリ計算幾何学 アルゴリズムと応用


2重連結辺リスト
デローニー三角形分割

ボロノイ図の計算

用語

サイト…ボロノイ図の母点。放物線の焦点でもある。
サイトイベント…走査線が新たなサイトにぶつかるイベント
ビーチライン…複数の放物線の弧の外側をたどったライン。
ブレークポイント…ビーチライン上にある、異なる放物線同士の交点。このブレークポイントはボロノイ図の辺をたどる。
円イベント…走査線がビーチライン上の連続する弧を定める3つのサイト(放物線の焦点)を通る円の最下点に到達するときのイベントを円イベントという。
$\tau$…ビーチラインの弧を表している

登場人物

$\tau$,$D(S)$…三角形分割。m個の三角形を持っているらしい。その三角形の辺は$e$と呼ばれる。点$p_i$と点$p_j$を結ぶ辺は$\overline{p_{i}p_{j}}$と表現する。サイト$S$のデローニー三角形分割
$P$…点の集合。$P_r$は点の集合$P$のr番目の頂点
$\alpha$…三角形の内角らしい。$\alpha_{i}$は、i番目の内角。この場合のi番目というのは、どうやって決まるかというと、三角形リスト$\tau$の中で$\alpha$達は昇順にソートされて若い順に番号が振られているらしい。結構順番は適当かな?
$Vor(P)$…Pのボロノイ図
$v(p)$,$v_i$…ボロノイセル。中に点pを含んでいる。ボロノイセルとはボロノイ1領域のこと。ボロノイ領域$v_i$は、すべての点の点$p_{0}~p_n$の中で点$p_i$に最も近いもので構成されている。

特殊な用語

フリップする…不要な辺を取り除いて、新しい辺を挿入すること。ここでいう不要な辺とは、新しい辺を挿入した方がより均等な三角形になる場合、不要な辺という。
サイト$P$の別称。ボロノイダイアグラムの点。平面上にある。
有界な面
凸包(Convex)..
ボロノイダイアグラム..n個の凸包な領域に分割する。
母点…1ボロノイ領域の中にある点

サポートサイト Wikidot.com