QuadTreeと最大余空間とOpenLayers3メモ

ご存知の通りQuadTreeはただの4分木だが、どういうわけか私のまわりでは「効率が悪い方の空間木」という不名誉な語られ方をすることが多い(効率が良い方の空間木はR-Tree)。効率が悪いのは探索木としてQuadTreeを使おうとするからであって、QuadTreeの使い方は探索木以外にもある。その例として「最大余空間を得る」というものがある。

「最大余空間」というのは私の造語で、意味は「確実に中身が存在しないことが判明している空間の中でも最大のもの」である。たぶん私以外には誰も使ってないと思うし、ひょっとしたらアカデミックな分野にはこれと同値な別の単語があるのかもしれない。

例えば「地球上に存在する日本語の列車駅」のインデックスを作るとする。(私の知っている限り)日本語の列車駅は南半球には存在しないので、例えばGoogle Mapsなどを利用する「列車駅の位置をマーカーで表示する」ようなアプリを作った際、アプリの地図領域内に南半球のエリアしかない状態であれば、(日本語の列車駅は確実に存在しないので)そもそも駅の位置などをサーバにfetchする必要が無い。地図上において南半球エリアは極めて広大な領域だが、これが広ズームのタイル1枚でマスキングすることによって、サーバ負荷を低減することができる。