締切済み

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

  • 困ってます
  • 質問No.9566763
  • 閲覧数134
  • ありがとう数1
  • 気になる数0
  • 回答数1
  • コメント数0

お礼率 49% (292/589)

情報処理のデータ構造にツリー構造というものがあります。
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の再帰呼び出し、ポインタで処理するのが普通らしいですが、ループと配列でフォートランでもできるとのことでした。
よろしくお願いします。

回答 (全1件)

  • 回答No.1

ベストアンサー率 22% (173/762)

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

お礼率 49% (292/589)

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

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,500万件のQ&Aを分析して最適な回答をご提案します。

関連するQ&A
こんな書き方もあるよ!この情報は知ってる?あなたの知識を教えて!
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する

特集


OKWAVE若者応援スペシャル企画

ピックアップ

ページ先頭へ