私は、特定のボリューム内でオブジェクトを見つけるための非常に効率的な方法が必要であるという問題があります。オブジェクトはX-min、Y-min、Z-min、X-max、Y-max、Z-maxの値を持つボックスとして表されると想像することができます。宇宙には何百万ものオブジェクトが存在する可能性があり、問題は、任意に与えられたユーザーが提供するボリューム内のオブジェクトを見つけることです。ユーザーはボックスのX、Y、Z値の最小値、最大値を入力します。ボリューム内のオブジェクト
現時点では、X、Y、およびZの値に索引付けされた範囲のOracle Database表にすべてのオブジェクトがあります。オブジェクトを見つけるためのクエリは、指定されたX、Y、&のZ値とオブジェクト値のZ値の比較を含みます。私はパフォーマンスが満足できるものではないことを知り、これを解決するインメモリアルゴリズムを考える。また、完全に部分的に入っているオブジェクトを見つける必要があります。
おかげ エー
部分的に内、または指定された境界ボリュームなしに、自分の軸平行境界ボックスが内に収まるかどうかを見つけるのは比較的迅速な方法があります。基本的に、バインドされた比較の値にビットマスクを割り当て、ビットマスクの論理積をとって境界ボックスの交点を決定することができます。それはあなたが望むものであり、非常に効率的な方法です。私は何年も前（真剣に、15年前のように）それを見て覚えています。私はそれを見つけたときに、そのメソッドについての参照とより多くのデータを投稿します。
更新：私が思い出した元の方法は、この正確な状況ではなかったと思いますが、これには比較的迅速な解決策があります。 1次元の場合（他の次元を一般化することができます）、その次元のボックスのポイントの両方がボックスの最小値より小さい場合、または両方がボックスより大きい場合、オブジェクトは失格になりますmax。ディメンションごとに繰り返します。これにより、必要なものが得られます。
非常に洗練されたソリューションではありませんが、効率的であることを願っています。
初期化には時間がかかりますが、それはうまくいくはずです。クエリはうまくいくでしょう。
まず、クエリされたコンテナ内のポイントを検索できる空間分割データ構造を作成します。この方法でボックスを見つけることができます。
ノードあたり8人の子供がいるツリーになります。他の選択肢があります。見てくださいk-d trees
すべてのボックスが含まれている最も小さい容器を探します。
この容器は、8つの等間隔の容器で分割します。
セット内の各ポイントについて、それが属するコンテナを見つけます。
複数のポイントがあるコンテナごとに、このプロセスを繰り返します。
あなたは一点を持つ葉のコンテナで終わるでしょう。
この構造を使用すると、クエリされたコンテナ内のすべてのポイントを検索したいとします。
ツリーの先頭から始め、照会されたコンテナと交差するすべてのブランチ/コンテナをトラバースします。
3つのケースがあります：
1）コンテナは照会されたコンテナ内に完全に囲まれています=>このサブツリーのすべてのポイントが照会されたコンテナにあります。
2）コンテナは照会されたコンテナの外にあります=>それをトラバースしません。 （これはあなたが効率を得るべきところです）
3）コンテナが照会されたコンテナと交差している=>あなたはそのすべての子プロセスを繰り返す必要があります。
把握しなければならないエッジケースがいくつかあります。
ボックスを見つけるには、その8つのコーナーのそれぞれをそのデータ構造に配置する必要があります。
コーナーはボックスに戻ってリンクする必要があります。コーナーが見つかると、それが属するボックスが分かります。
は完全にX、Y、Zの整数であるあなたが見つけボックス
面白そうに見えますが、私はこのアプローチを試み、どのように動作するかを見ていきます。ありがとう – eeykay
のそれぞれをテストする必要が照会容器に囲まれたボックス検索するには？その範囲はどれくらい大きいですか？ – titus