1

位置とサイズが最小値と最大値x、yおよびz座標で指定されている（主軸に平行であるため）多数の直方体があります。

たとえば、次の 3 つの直方体があるとします。

10.5 <= x <= 39.4、90.73 <= y <= 110.2、90.23 <= z <= 95.87
20.1 <= x <= 30.05、9.4 <= y <= 37.6、0.1 <= z <= 91.2
10.2 <= x <= 10.3、0.1 <= y <= 99.8、23.7 <= z <= 24.9

次にポイント (例: (25.3,10.2,90.65)) を指定した場合、自分がどの立方体にいるかをすばやく判断する方法はありますか?

  • 明らかに、すべての直方体を反復処理することもできますが、潜在的に数百万の直方体が存在するため、単純な反復処理よりも高速に処理する必要があります (O(log n) またはそれ以上の値が望ましい)。

  • これは「ファジー マッチング」タイプの問題のように思えます。Apache Luceneが範囲クエリをサポートしていることに気付きましたが、これは逆に機能するようです (点を含む立方体ではなく、立方体で点を見つける)。

  • さらに複雑なことに、次元の数が 3 より大きくなる場合があります (20 までになる可能性があります)。つまり、立方体ではなく「超立方体」を探している可能性があります。)

4

2 に答える 2

2

あなたは「バイナリ空間分割」と「衝突検出」の領域に突入します。基本的に、アイデアは直方体をツリー型の構造に格納することです。これにより、直方体が占めるスペースがきちんとした小さなボックスに分割されます。各直方体が占める「空間の部分」についての決定は、樹木構造への挿入中に行われます。

Octreesでグーグル検索を行います。

3D空間を効率的に分割し、その空間に含まれるオブジェクトは、コンピューターサイエンスのかなりの部分を占めています。主にコンピュータゲームの開発に使用されます。一部のアルゴリズムでは、時間的要因、つまりオブジェクトがパーティションスペース間を移動することを考慮しています。

于 2009-07-21T12:50:36.757 に答える