みんなの「教えて(疑問・質問)」にみんなで「答える」Q&Aコミュニティ

こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

締切り済みの質問

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

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

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

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

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

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

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

投稿日時 - 2018-12-11 12:10:14

QNo.9566763

困ってます

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(1)

ANo.1

ご質問にあるリンクページの下方に記載されている『データ構造』テーブルに出典されている、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

投稿日時 - 2018-12-11 18:36:02

お礼

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

投稿日時 - 2018-12-12 14:36:31

あなたにオススメの質問