空間分割

幾何学において、空間分割とは、空間全体（通常はユークリッド空間）を 2 つ以上の互いに素な 部分集合に分割するプロセスです （集合の分割も参照）。言い換えると、空間分割は空間を重複しない領域に分割します。空間内の任意の点は、それらの領域の 1 つに正確に存在すると識別できます。

空間分割システムは階層的であることが多く、つまり、空間 (または空間の領域) が複数の領域に分割され、作成された各領域に同じ空間分割システムが再帰的に適用されます。領域は、空間分割ツリーと呼ばれるツリーに編成できます。

ほとんどの空間分割システムでは、平面（または、高次元では超平面）を使用して空間を分割します。平面の片側の点は 1 つの領域を形成し、反対側の点は別の領域を形成します。平面上にある点は、通常、どちらかの側に任意に割り当てられます。このように平面を使用して空間を再帰的に分割すると、最も一般的な空間分割形式の 1 つである BSP ツリーが生成されます。

空間分割はコンピュータグラフィックスにおいて特に重要であり、特にレイトレーシングで頻繁に使用され、仮想シーン内のオブジェクトを整理するために使用されます。一般的なシーンには数百万のポリゴンが含まれる場合があります。各ポリゴンでレイ/ポリゴン交差テストを実行すると、計算コストが非常に高くなります。

オブジェクトを空間分割データ構造（k -dツリーやBSPツリーなど）に格納すると、特定の種類のジオメトリクエリを簡単かつ高速に実行できるようになります。たとえば、光線がオブジェクトと交差するかどうかを判断する場合、空間分割により交差テストの回数を主光線ごとにわずか数回に減らすことができ、ポリゴンの数に対して対数的な時間計算量が得られます。 ^{[1] [2] [3]}

空間分割は、カメラの視野錐台からポリゴンを除去して、パイプラインで処理されるポリゴンの数を制限するために、スキャンライン アルゴリズムでもよく使用されます。衝突検出にも使用されます。空間分割を使用すると、2 つのオブジェクトが互いに近いかどうかを判断するのがはるかに速くなります。

集積回路の設計において、重要なステップは設計ルール チェックです。このステップでは、完成した設計が製造可能であることを確認します。チェックには、幅や間隔、その他のジオメトリ パターンを指定するルールが含まれます。最新の設計では、配線やトランジスタを表すポリゴンが数十億個あります。効率的なチェックは、ジオメトリ クエリに大きく依存しています。たとえば、ルールでは、ポリゴンは他のポリゴンから少なくともnナノメートル離れている必要があると指定できます。これは、ポリゴンをすべての辺でn/2に拡大し、交差するポリゴンをすべて検索するクエリを実行することで、ジオメトリ クエリに変換されます。

空間分割内のコンポーネントの数は、確率論のいくつかの結果において中心的な役割を果たします。詳細については、 成長関数を参照してください。

地理的空間現実を水文学的基準、 行政的基準、数学的基準、その他多くの基準で分割する研究やアプリケーションは数多くあります。

地図作成とGIS (地理情報システム)のコンテキストでは、パーティションのセルを標準コードで識別するのが一般的です。たとえば、水路流域とサブ流域を識別するHUC コード、国とその下位区分を識別するISO 3166-2コード、または任意のDGG (象限または場所を識別する個別のグローバル グリッド)など です。

一般的な空間分割システムには以下のものがあります。

• BSPツリー
• クワッドツリー
• オクトツリー
• k -d ツリー
• ビン

n次元ユークリッド空間が -次元の超平面で分割されているとします。分割された要素の数はいくつでしょうか。要素の最大数は、超平面が一般的な位置にあるとき、つまり、どの2つも平行ではなく、どの3つも同じ交差点を持たないときに得られます。この最大要素数を と表記します。すると、次の再帰関係が成り立ちます。 ^{[4] [5]}${\displaystyle r}$ ${\displaystyle (n-1)}$${\displaystyle Comp(n,r)}$

${\displaystyle Comp(n,r)=Comp(n,r-1)+Comp(n-1,r-1)}$

${\displaystyle Comp(0,r)=1}$- 次元がない場合、点は 1 つだけです。

${\displaystyle Comp(n,0)=1}$- 超平面が存在しない場合は、空間全体が単一のコンポーネントになります。

その解決策は次のとおりです。

${\displaystyle Comp(n,r)=\sum _{k=0}^{n}{r \choose k}}$もし${\displaystyle r\geq n}$

${\displaystyle Comp(n,r)=2^{r}}$もし${\displaystyle r\leq n}$

(例えば、垂直な超平面を考えてみましょう。追加の超平面ごとに、既存の各コンポーネントが 2 に分割されます)。${\displaystyle r}$

これは次のように上限が定められます。

${\displaystyle Comp(n,r)\leq r^{n}+1}$

• バイナリ空間分割
• 離散グローバルグリッド
• ポリゴンパーティション
• テッセレーション