特定のボリューム内のオブジェクトを見つける非常に効率的な方法が必要であるという問題があります。オブジェクトは、X-min、Y-min、Z-min、および X-max、Y-max、Z-max の値を持つボックスとして表されると想像できます。このようなオブジェクトが空間に何百万も存在する可能性があります。問題は、ユーザーが任意に指定したボリューム内のオブジェクトを見つけることです。ユーザーは、ボックスの X、Y、および Z 値の最小値、最大値を入力します。
現在、X、Y、および Z 値の範囲インデックスが作成された Oracle データベース テーブルにすべてのオブジェクトがあります。オブジェクトを見つけるためのクエリには、指定された X、Y、および Z 値とオブジェクト値の比較が含まれます。パフォーマンスが満足できるものではなく、これを解決するためのメモリ内アルゴリズムを考えています。また、完全に入っている、部分的に入っているオブジェクトを見つけることも必要です。
ありがとうエイ
軸に沿って配置されたバウンディング ボックスが、指定されたバウンディング ボリュームの範囲内にあるか、部分的に範囲内にあるか、または範囲外にあるかを比較的迅速に確認する方法があります。基本的に、境界比較の値にビットマスクを割り当て、ビットマスクの AND 演算によって境界ボックスの交点を決定できます。それはまさにあなたが望むものであり、非常に効率的な方法です。何年も前に見たのを覚えています（真剣に、15年前のように）。メソッドが見つかったら、リファレンスとメソッドに関する詳細データを投稿します。
更新: わかりました。私が覚えていた元の方法は、この正確な状況には適していなかったと思いますが、これには比較的迅速な解決策があります。1 次元の場合 (そこから他の次元を一般化できます)、その次元のボックスの両方のポイントがボックスの最小値よりも小さい場合、または両方ともボックスよりも大きい場合に、オブジェクトを失格にする必要があります。最大 ディメンションごとに繰り返すと、必要なものが得られます。
あまりエレガントなソリューションではありませんが、効率的であることを願っています。
初期化の部分には時間がかかりますが、それが報われるはずです。クエリが高速になることを願っています。
まず、スペース分割データ構造を作成します。これを使用して、クエリされたコンテナ内のポイントを検索できます。この方法でボックスを見つけることができます。
これは、ノードごとに8つの子を持つツリーになります。他の選択肢があります、kd木を見てください
すべてのボックスを含む最小の囲みコンテナを見つけます。
このコンテナを8つの同じサイズのコンテナに分割します。
セット内の各ポイントについて、それが属するコンテナを見つけます。
複数のポイントが含まれるコンテナごとに、このプロセスを繰り返します。
最終的には、単一のポイントを持つリーフコンテナになります。
この構造を使用して、クエリされたコンテナ内のすべてのポイントを検索するとします。
ツリーの最上部から開始し、照会されたコンテナーと交差するすべてのブランチ/コンテナーをトラバースします。
3つのケースがあります：
1）コンテナがクエリされたコンテナ内に完全に囲まれている=>このサブツリーのすべてのポイントがクエリされたコンテナ内にあります。
2）コンテナがクエリされたコンテナの外側にある=>あなたはそれを横断しません。（これは効率を得る必要がある場所です）
3）コンテナがクエリされたコンテナと交差しています=>すべての子に対してプロセスを繰り返す必要があります。
あなたが理解しなければならないいくつかのエッジケースがあります。
ボックスを見つけるには、そのデータ構造に8つのコーナーをそれぞれ配置する必要があります。
コーナーはボックスにリンクする必要があります。したがって、コーナーを見つけると、それがどのボックスに属しているかがわかります。
クエリされたコンテナに完全に含まれているボックスを見つけるには、見つかった各ボックスをテストする必要があります