1. 序章

このチュートリアルでは、ボロノイ図について説明します。 これは、自然界でしばしば発生する単純な数学的複雑さであり、科学において非常に実用的なツールにもなり得ます。 有名なロシアの数学者ゲオルギ・フェローノイにちなんで名付けられました。 ボロノイ分割、ボロノイ分解、またはボロノイ分割と呼ぶこともできます。

使用されている名前に関係なく、非常に独特な視覚的特徴を持っているため、そのパターンをすぐに認識できないことは困難です。 そのため、最初に視覚的な直感を得るつもりです。 次に、その背後にある数学的規則について説明します。

2. 意味

次の図では、ボロノイ図とともに、2次元平面上にランダムに配置された40個のオレンジ色の点のセットがあります。 結果として得られる領域またはタイルは、ボロノイセルと呼ばれます。

オレンジ色の点のほとんどが各セルの中心近くにあることがすぐにわかります。 ただし、すべてのセルの境界は、その周囲のポイントまでの距離に基づいており、と黒い線は、ポイント間のスペースを完全に分割するように描画されます。

さらに、セル内に追加のポイントを追加した場合、それらはセルの元の対応するポイントにのみ最も近くなります。 これは、近くのポイントが少ないほど、結果のセルが大きくなることを意味します。 数学的には、上記の観察結果を次のように簡潔に表すことができます。

与えられた有限の点のセットに対して、各点は対応するボロノイセルを持ちます。これは、の距離がセットからの他の点までの距離以下である平面内のすべての点で構成されます。

3. 計算

ボロノイ図が何であるかが明確に定義されたので、計算に取り掛かることができます。 多くのアルゴリズムがその役割を果たします。 ただし、最も理解しやすい方法では、実際にはボロノイ図を直接計算するのではなく、最初に一連の点のドロネー三角形分割を計算する必要があります。

しかし、ドロネー三角形分割とは正確には何であり、ボロノイ図を見つけるのにどのように役立ちますか？ これは、元の点のセットを頂点として使用して構築された三角形のコレクションです。 ただし、条件が1つあります。 三角形の頂点は、フォーメーション内の他の三角形の外接円の内側にあるべきではありません。たとえば、そのような構造の1つの図を次に示します。

ここでは、黒で10個の点があり、描かれた外接円内に他の点がないことが簡単にわかります。 また、ボロノイ図を見つけるのに役立つ重要な詳細であるため、各外接円の原点を緑色の点で示します。

最初の40ポイントのセットでのボロノイ図をそのドロネー三角形分割と並べて比較することにより、これが当てはまる理由を見てみましょう。

2つのグラフを視覚的に綿密に比較し、右側の各三角形の周りの円を画像化することにより、左側の結果のボロノイ図との関係を確認できます。 さらに、私たちが描くすべての三角形の外接円は、実際にはボロノイグラフの頂点に対応しています。

そのため、ドロネー三角形分割の準備ができている場合は、隣接する各三角形の外接円からそれ自体の外接円までのエッジを形成して、ボロノイグラフのエッジを見つける必要があります。 かなりきちんと！

では、どのようにしてドロネー三角形分割を計算するのでしょうか。 これを行う1つの方法は、Bowyer-Watsonアルゴリズムを使用することです。

このアルゴリズムは、既存のDelaunay三角形分割にポイントを繰り返し追加することで機能します。通常、三角形分割するすべてのポイントを囲むような非常に単純な三角形分割から開始します。 挿入するたびに、三角形の外接円に新しい点が含まれているかどうかを確認し、含まれている場合は削除して、空洞を残し、空洞の境界で頂点を結合します。

基本的な実装の擬似コードは、実際には非常に単純です。

このアルゴリズムの計算の複雑さは、データ構造を注意深く選択することでさらに改善できますが、この正確な定式化では、すべての三角形の接続性がチェックされるため、になります。

4. 結論

この短い記事では、複雑なボロノイ図と、その密接に関連するいとこであるドロネー三角形分割を視覚的に紹介しました。 見つかった関係を使用して、最終的な図の計算にどのように役立つかを説明することにより、Bowyer-Watsonアルゴリズムの使用を推奨しました。