空間分割

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

概要

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

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

用途

コンピュータグラフィックスにおいて

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

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

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

集積回路設計において

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

確率と統計学習理論において

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

地理学とGIS

地理的空間現実を水文学的基準、 行政的基準、数学的基準など によって分割する研究や応用は数多くあります。

地図作成や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}$

参照

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

参考文献

1. Tomas Nikodym (2010). 「インタラクティブアプリケーションのためのレイトレーシングアルゴリズム」(PDF) .チェコ工科大学, FEE .
2. Ingo Wald、William R. Mark他 (2007). 「アニメーションシーンにおけるレイトレーシングの最新技術」. Eurographics . CiteSeerX 10.1.1.108.8495 . 
3. レイトレーシング - 補助データ構造
4. Vapnik, VN; Chervonenkis, A. Ya. (1971). 「事象の相対頻度とその確率の一様収束について」.確率論とその応用. 16 (2): 266. doi : 10.1137/1116025 .これは、B. セックラーによるロシア語論文「事象の相対頻度とその確率の一様収束について」 の英訳です。Dokl . Akad. Nauk . 181 (4): 781. 1968. 翻訳は以下のように転載されました： Vapnik, VN; Chervonenkis, A. Ya. (2015). 「事象の相対頻度とその確率の一様収束について」『複雑性の尺度』p. 11. doi : 10.1007/978-3-319-21852-6_3 . ISBN 978-3-319-21851-9。
5. n=2の場合 と一般の場合の詳細な議論と説明も参照してください。また、 Winder, RO (1966). "Partitions of N-Space by Hyperplanes". SIAM Journal on Applied Mathematics . 14 (4): 811– 818. doi : 10.1137/0114068 .も参照してください。