quadtreeとは? わかりやすく解説

Weblio 辞書 > 学問 > OR事典 > quadtreeの意味・解説 

四分木

(quadtree から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/06/19 08:05 UTC 版)

ナビゲーションに移動 検索に移動
領域四分木

四分木(しぶんぎ、: Quadtree)は、各内部ノードが4個までの子ノードを持つ木構造データ構造である。四分木は主に、2次元空間を再帰的に4つの象限または領域に分割するのに使われる。領域は四角形または矩形の場合もあるし、任意の形状の場合もある。このデータ構造は1974年、Raphael Finkel と J.L. Bentley が四分木と名づけた。同様の分割手法はQ木 (Q-tree) とも呼ばれている。四分木に共通する特徴は以下の通りである。

  • 空間を適応可能セルに分割する。
  • 各セル(またはバケット)は容量の上限がある。容量が最大に達すると、バケットは分割される。
  • 木構造ディレクトリは四分木の空間分割に従う。

種類

四分木は表現するデータの型によって分類され、領域 (area)、点 (point)、線 (line)、曲線 (curve) などがある。また、木構造の形状とデータを処理する順序が独立しているかどうかでも分類される。典型的な四分木について以下に解説する。

領域四分木

領域四分木は、2次元の空間を同じ大きさの4つの象限に再帰的に分割していくもので、各ノードは特定の領域に対応したデータを保持する。各ノードは4つの子ノードを持つか、あるいは全く子ノードを持たないか(つまり葉ノード)のどちらかである。領域四分木は、分割位置がデータに依存していないため、厳密には木構造ではないとされる。より厳密に言えばTrieに近い。

深さ n の領域四分木は、カテゴリ



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「quadtree」の関連用語

quadtreeのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



quadtreeのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2025 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの四分木 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS