問題タブ [space-partitioning]

大きな静的サイズの長方形を小さな長方形に分割するアルゴリズムが必要です。私にとって完璧な実装は次のようになります。

GetRectしたがって、FreeRectメソッドのアルゴリズムが必要です。アイデアやリンクをいただければ幸いです。

特定のボリューム内のオブジェクトを見つける非常に効率的な方法が必要であるという問題があります。オブジェクトは、X-min、Y-min、Z-min、および X-max、Y-max、Z-max の値を持つボックスとして表されると想像できます。このようなオブジェクトが空間に何百万も存在する可能性があります。問題は、ユーザーが任意に指定したボリューム内のオブジェクトを見つけることです。ユーザーは、ボックスの X、Y、および Z 値の最小値、最大値を入力します。

現在、X、Y、および Z 値の範囲インデックスが作成された Oracle データベース テーブルにすべてのオブジェクトがあります。オブジェクトを見つけるためのクエリには、指定された X、Y、および Z 値とオブジェクト値の比較が含まれます。パフォーマンスが満足できるものではなく、これを解決するためのメモリ内アルゴリズムを考えています。また、完全に入っている、部分的に入っているオブジェクトを見つけることも必要です。

ありがとうエイ

ゲームに空間分割アルゴリズムを実装しようとしていますが、空間ハッシュと四分木はどちらも探しているものではありません。

レベル サイズに制限はありません (Int32 制限のみ)。「レベル幅」と「レベル高さ」を必要としない空間分割アルゴリズムが必要です。

私は多くの動く物体を持っています。500 以上のオブジェクトをサポートするのに十分な速さのアルゴリズムが必要です。

代替案はありますか？

(0,0)からまでの 2 次元の空間領域があります(MAX_X, MAX_Y)。

この空間の領域内に、いくつかの線を描きます。線は領域の周囲と交差し、互いに交差する場合もあります。このように、これらの線は空間の領域をサブ領域に分割し、それらを合計すると、空間の領域全体が得られます。

この領域内には、いくつかのポイントがあり(x,y)ます。私は決定しなければならない

1. 線によって作成された空間のすべての部分領域を構成するすべての頂点の座標
2. 空間の特定の部分領域に 1 つ以上の点が含まれているか含まれていないか

これをJavaでコーディングしようとしていますが、言語はそれほど重要ではありません。これらの 2 つのタスクを達成する方法がわかりません。誰かが私にヒントを与えることができれば、本当に感謝しています。

エッジでラップする 2D マップがあります。したがって、右端から移動すると、マップの左側に再び表示されます。他の 3 つのエッジについても同様です。

これは、ポイントの範囲内の要素を見つけるために使用する KDTree の継承可能な問題です。通常、超球体が超平面と衝突するかどうかをチェックして、ツリーの反対側を検索し続ける必要があるかどうかを確認しますが、このチェックはラップ エッジでは機能しません。

ドーナツ 2D 空間で動作するように KD ツリーを変更する方法はありますか?

kdツリーを使用して2次元空間のポイントを検索するアプリを作成しています。開発中に、各ポイントを囲む最も近いゾーンを「見る」ことができれば便利です。

添付の画像では、赤い点はkdツリー内の点であり、各点を囲む青い線は、最近傍探索が含まれている点を返すゾーンを境界付けています。

画像は次のように作成されました。

このアルゴリズムには2つの問題があります。

• （より重要）私の（かなり速いCore i7）コンピューターでは遅いです。
• （それほど重要ではありません）青い線の幅が変化していることがわかるように、それはずさんです。

この一連のポイントの「視覚化」とは何ですか？

そのような視覚化を作成するためのいくつかの良いアルゴリズムは何ですか？

空間分割については、R-Tree、kd-tree、境界間隔階層などについて読みました。これらのデータ構造は、空間クエリに役立つことがわかりました。ただし、パーティション分割は行いますが、データ構造からそれらのパーティションを取得する方法がわかりません。したがって、私の質問は、「数値 N と、たとえば X 個のポリゴンを含むマップが与えられた場合、ほぼ同じ数のポリゴンを含む N 個のパーティションを取得できますか?」ということになります。

バイナリ スペース パーティション ツリーによって指定された 3D ボリュームがあります。通常、これらはポリゴン モデルから作成され、分割されたポリゴンはツリー ノード内に既に格納されています。

しかし、私のものはそうではないので、ポリゴンはありません。すべてのノードには、切断面以外には何もありません (たとえば、法線と原点の距離によって与えられます)。したがって、ツリーは、作成されたすべてのカットによって定義されるソリッド 3D ボリュームを表します。ただし、視覚化するには、このボリュームのポリゴン メッシュが必要です。どうすればそれを効率的に再構築できますか？

大雑把な方法は、葉の無限の半空間を十分な大きさの多面体 (立方体など) に変換し、それらのすべてをツリーの上に押し上げて、通過するすべてのノードの平面で切断することです。ツリーのバランスが取れていない可能性があるため（たとえば、凸多面体から愚かに作成された場合）、これは非常にコストがかかるようです。古典的な解決策はありますか？

_{(ソース: hiveworkshop.com )}

上の図では、20 個の任意のポイントを 5 つのクラスターに分割しています。右側には、最大クラスター サイズを定義する円があります。右上はクラスターあたりの最大ポイントです。ポイント k の任意のセットを取り、それらを最大半径 r の最大サイズ n のクラスターに分割できるようにしたいと考えています。可能な限り完全なクラスターを取得するアルゴリズムが必要です(上記の例では、できるだけ多くの 4 つのクラスター)。任意のポイントは 1 つのクラスターにのみ属することができ、クラスターが重複することはありません。

アルゴリズムが既存のセットにポイントを追加/削除し、クラスターを更新できる場合も役立ちます。

これを達成する方法について、私は完全に迷っています。これまでの私の最善のアイデアは、ポイントのセットの中心を計算し、それらの中心をバイナリ空間分割に使用することでしたが、そのアプローチを使用して期待できる最善の方法は、クラスターが均等に分散されることです。

どんな助けでも大歓迎です:)。

edit
領域が形成する形状が他の領域が形成する形状と交差せず、その領域が他の領域の内側に位置しない (例えば、円の中の円) ように重ならないでください。上の図では、各領域に形状があります。これらの形状はいずれも交差せず、別の領域内に領域はありません。

私は数百万の原子のシステムを含むいくつかのMDシミュレーションを実行しています。

XYZ原子座標のリストであるファイルを生成するためのコードをいくつか作成しました。次に、原子間に結合を生成する必要があります。2つの原子が互いに一定の距離内にある場合、それは結合と見なされます。

XYZファイルの例：

だから私は5つの原子を持っています。距離のしきい値が2単位の場合、債券のリストは次のようになります。

（ここで、番号はXYZファイルの座標のインデックスに対応します）。

このリストを生成するための素朴なアプローチは次のとおりです。

ただし、これはすぐにアルゴリズムの限界に達し、数百万の原子に対して高度に最適化されたCでも、少なくともこのプロセスを実行するのと同じくらい頻繁に遅くなります。

スペースパーティションデータ構造で私が経験したのは、フォトンマッパーを一度作成したときのkdツリーでの経験だけなので、この問題の最善の解決策が何であるかはわかりません。しかし、これに最適なものがおそらくそこにあると確信しています。

また、シミュレーションボックスは周期的です。つまり、（0.5、0、0）の原子は、2などの距離しきい値で（boxWidth --0.5、0、0）の原子に結合します。