木構造のデータ処理・検索に関する質問

質問

情報処理のデータ構造にツリー構造というものがあります。
１つのノードから複数のノードが派生して出ており、一番最初を親として子・孫という言い方をしたり、根（一番上とか下）から始まって葉に向かう階層構造のようなものですね。情報処理の専門家はおなじみだろうと思います。
そのようなツリー構造の１つの例として四分木構造というものがあり、カーペットを４つ切りにして細かく見ていくような感じです。以下に説明サイトがあります。１つ１つのカーペットをノードと称するようです。
https://ja.wikipedia.org/wiki/%E5%9B%9B%E5%88%86%E6%9C%A8

カーペットという平面を４つ切り（小さなカーペット）にするので階層が深まる（何回も４分の１にする）につれて部分的に分解能が上がるという利点があります。

この四分木構造について以下のような質問があります。

１．添付図なのですが、最終的に使用する格子は葉（これ以上分岐しない）となります。
この場合、その葉格子が別のどの葉格子と境界を接しているか抽出するアルゴリズムとしてどのようなものがあるでしょうか。

２．分木構造は細分化している処理は足しこんでいくだけなので与しやすしですが、その逆つまり、分木構造をやめて４つ切りから１つに統合する場合、どのようなアルゴリズムになるでしょうか。ノードが消えていくのですが、ノード番号などの割り振りは変えず、全体番号として歯が抜けたようになっていくのでしょうか。
要は分木が増えたり減ったりすることをダイナミックに処理する方法なのですが。

フォートランでできないかなと思っています。Cの再帰呼び出し、ポインタで処理するのが普通らしいですが、ループと配列でフォートランでもできるとのことでした。
よろしくお願いします。

回答No.1

chachaboxx

ご質問にあるリンクページの下方に記載されている『データ構造』テーブルに出典されている、BSP木がアルゴリズムに詳しいかと。
レンダリングのサンプルコードもあります。
https://ja.wikipedia.org/wiki/%E3%83%90%E3%82%A4%E3%83%8A%E3%83%AA%E7%A9%BA%E9%96%93%E5%88%86%E5%89%B2

お礼

回答ありがとうございます。
コンピュータグラフィックスは描画速度の向上が目的でポリゴンに付与された深さ（奥行情報の段階）にはグラデーションになるみたいに細分化されるようです。目に見えるものが精度よくなっていればいいということでしょうか。
私の方は単純で形状が正方形であり、深さ方向には5段階もあれば十分というものです。たいていは3段階ぐらいです。そのかわり隣はどうなっているかということと、その隣との間で物理量のやり取りを考える必要があります。コンピュータグラフィックスでもシューティングゲームのように接触・衝突の判別になると絵を描いてみせる以上の処理が必要のようですが。