問題タブ [space-partitioning]

私は最近、バイナリ スペース パーティショニング ツリーと、その 3D グラフィックスおよび衝突検出への応用について学びました。また、四分木と八分木に関連する資料を簡単に調べました。bsp ツリーではなくクワッドツリーを使用するのはいつですか、またはその逆ですか? それらは交換可能ですか？次のような表に記入するのに十分な情報があれば満足です。

A、B、Cとは？

私は C++ でゲームを書いており、それぞれが独自の頂点バッファーを持つ多くの個別のメッシュで構成されるレベルを持っています。vmmlib (華麗な無料の gl compat. vector/matrix library ) を使用して錐台カラーを作成し、レベル内のすべてのメッシュの境界球に対してテストしています。悲しいことに、私のレベルは最大 800 のメッシュで構成されている可能性があり、フレームごとにそれらすべてを反復するのは遅いです。すべての反復ですべてのメッシュを確認する必要がないように、コードを最適化する最良の方法は何ですか? フラスタム内のバウンディング ボリューム?

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

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

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

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

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

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

最も近い隣人を見つけるためのアルゴリズムの 1 つにSpace Partitioningがあります。それはどのように機能しますか？

点 (x 座標と y 座標) の 2D セットがあり、点 (a,b) が与えられているとします。このアルゴリズムはどのようにして最近傍を見つけますか?

経度の緯度がx百万ポイントあるシナリオがあります。

新しいlong/latポイントが追加されたときに、ユーザーが構成した距離パラメーター内にある他のポイントを効率的に知りたいので、それらをリストに追加できます。

バウンディングボックスよりも優れたものはありますか？

アルゴリズム、リファレンス、いくつかの実装を見てみたいです;）ありがとうございます！

何千もの光線と三角形があります。すべての交点を取得する必要があります。通常の 2 レベル ループを使用する場合、O(m n) 時間の複雑さが必要です。時間の複雑さを O(m n) から O(m* logn) または O(logm*n) に下げる方法はありますか?

よろしくお願いします、

ベクトル量子化の実装を、さまざまなタイプとベクトルの次元 (たとえば、バイトの 16 次元ベクトル、または double の 4d ベクトルなど) を処理できる C++ テンプレート クラスとして設計しようとしています。

私はアルゴリズムを読んでいて、ほとんどを理解しています：

こことここ

Linde-Buzo-Gray (LBG) アルゴリズムを実装したいのですが、クラスターを分割するための一般的なアルゴリズムを理解するのに苦労しています。平面の両側に等しい数があるように、クラスター内のベクトルを分割する平面 (超平面?) を定義する必要があると思います。

[編集して詳細情報を追加] これは反復プロセスですが、すべてのベクトルの重心を見つけることから始めて、その重心を使用して分割平面を定義し、平面の各側面の重心を取得し、続行すると思いますVQ アルゴリズムに必要な数のクラスターが得られるまで (途中で歪みが少なくなるように最適化を繰り返します)。上記の最初のリンクのアニメーションは、それをうまく示しています。

私の質問は次のとおりです。

重心を取得したら、平面を見つけるアルゴリズムは何ですか?

ベクトルをテストして、その平面の両側にあるかどうかを確認するにはどうすればよいですか?

長方形内に含まれる一連のポイントがあります。ポイント密度に基づいて長方形をサブ長方形に分割したいと思います（サブ長方形の数または目的の密度のいずれか簡単な方を指定します）。

分割は正確である必要はありませんが（通常のグリッドよりも優れた近似はほとんどありません）、アルゴリズムは多数のポイントに対処する必要があります。2億。ただし、必要なサブ長方形の数は大幅に少なくなります（約1000）。

この特定のタスクで私を助けるかもしれないアルゴリズムを誰かが知っていますか？

同じ 1 次元 (線形) 空間に対応する間隔の 2 つのセット。これは大まかなビジュアルです。実際には、さらに多くの間隔があり、さらに広がっていますが、これで基本的な考え方がわかります。

これらの間隔にはそれぞれ情報が含まれており、私は間隔の 1 つのセット (赤) の情報を他のセット (青) に含まれる情報と比較するプログラムを作成しています。

これが私の問題です。各チャンクで実行される比較作業の量がほぼ同じになるように、スペースをnチャンクに分割したいと思います (作業量は、スペースのその部分の間隔の数によって異なります)。また、パーティションは赤または青の間隔を 2 つのチャンクに分割しないでください。

したがって、入力は 2 セットの間隔であり、目的の出力は次のような空間の分割です。

• 間隔は、パーティションの各要素に (おおまかに) 均等に分散されます。
• 複数のパーティション要素と間隔が重複しない

これを行うためのアプローチまたはアルゴリズムを提案できる人はいますか?