これを実行する方法がわからないので、皆さんに聞いてみることにしました。
私は長方形のリストを持っています-実際にはatmは正方形だけですが、後で長方形に移行する必要があるかもしれないので、それらに固執してもう少し一般的にしてみましょう-2次元空間で。各長方形は2つのポイントで指定されます。長方形はオーバーラップする可能性があり、セットアップ時間についてはあまり気にしません。長方形は基本的に静的であり、セットアップに関するもの（ツリーの構築、並べ替え、追加のベクトルの事前計算など）を事前に計算する余地があるためです。何でも）。これが気になる場合は、JavaScriptで開発しています。
私の実際の質問に対して：ポイントが与えられた場合、そのポイントを含むすべての長方形のセットを取得するにはどうすればよいですか？
線形アプローチは十分に機能しません。そこで、O（n）よりも優れたパフォーマンスを発揮するものを探します。バウンディングボリューム階層などを読んでいますが、長方形が重なる可能性があるという事実を試したものは何でも（ポイントが複数の長方形内にある場合は、実際にすべてを取得したい）、常に邪魔になるようです。
何か提案はありますか？明らかな何かを見逃したことがありますか？BVHは、重複する可能性のある境界にも適用できますか？もしそうなら、どうすればそのようなおそらく重複するツリーを構築できますか？そうでない場合、他に何を使用できますか？境界線が内側にあるか、外側にあるか、または決定されていないかどうかは私には関係ありません。
誰かがリンクや、Some_Super_Cool_Structure_Perfectly_Suited_For_My_ProblemではなくBVHを使用するのがいかに愚かであるかについての怒りのような何かを思い付くことができれば、本当に感謝しています！
編集：わかりました、私はR-Treesで少し遊んでいました、そしてこれはまさに私が探していたものです。実際、私は現在、endy_cによって提案されているようにRTree実装http://stackulator.com/rtree/を使用しています。それは本当にうまく機能し、私の要件を完全に満たします。サポートしてくれてありがとう！