algorithm - Delaunay 三角形分割からボロノイ領域のサイズを計算しますか?

Question

2D の一連のボロノイ領域の面積の平均と標準偏差を計算したいと思います (領域が無限に広がる場合は、それを単位正方形にクリップします)。

ただし、可能であれば、ボロノイ領域を明示的に計算せずに、ドロネー三角形分割からこの計算を行いたいですか? これは可能ですか、それともボロノイ図を明示的に計算する方が良いですか?

Answer 1

頂点のボロノイ領域を計算するには、その周りの 1 リングを反復する必要があります。次に、領域の面積は次のように定義されます。

A = 1/8 * (sum for every adjacent vertex p_i) { (cot alpha_i + cot beta_i) * (p_i - c).Length² }

画像では、ボロノイ領域全体が薄い赤で表示されています。その一部が濃い赤で示されています。これは合計によって蓄積された部分の 1 つです。alphaとbetaは、画像に表示されている角度です。c中心頂点位置です。p_i反対の vertex_position です。alpha、繰り返しながら変更しますbeta。その価値を保ちます。p_ic

隣接する頂点ごとにこれらの部分を計算すると、ボロノイ領域の 8 倍の面積が得られます。