問題タブ [spatial]

特定の長方形または円内のすべてのオブジェクトをすばやく取得できるように、それぞれが x 座標値と y 座標値を持つ一連のオブジェクトを格納する高速な方法を決定しようとしています。オブジェクトの小さなセット (~100) の場合、単にそれらをリストに格納し、それを反復処理する単純なアプローチは比較的迅速です。ただし、はるかに大きなグループの場合、これは遅くなると予想されます。次のコードを使用して、x座標でソートされたツリーマップとy座標でソートされたツリーマップのペアにもそれらを格納しようとしました。

これも機能し、より大きなオブジェクトのセットの方が高速ですが、それでも思ったより遅くなります。問題の一部は、これらのオブジェクトが移動し、このストレージに挿入し直す必要があることです。これは、ツリー/リストからオブジェクトを削除して再度追加することを意味します。そこにはもっと良い解決策があるはずだと思わずにはいられません。私はこれをJavaで実装していますが、違いがあれば、解決策はより有用なパターン/アルゴリズムの形になると思います。

3D の 3 次多項式の大規模なセットがあります。

マトリックス形式で

Pn = [1,t,t ² ,t ⁴ ]*[An]

[Pn]と[An]は1xNと4xN行列です

各関数には重み Wn があります。私は、いくつかのために、そのような最初の場所n, m, Tを見つけたいですt0tt>t0

(Wn*Wm) * |Pn-Pm| ^-2 > T

O(n ² ) の「すべてを試す」アプローチは別として、どこから始めればよいかさえわかりません。さらに言えば、既知の n & m であっても、これに答える方法がわかりません。

何か案は

編集：

• セットサイズは10～1000程度
• 重みは〜対数的に分布しています（非常に少数の大きなもの、多くの小さなもの）
• このテストは n-ボディ シミュレータの内部ループにあるため、何度も実行されます。
• 1 つのパスが変更された後に新しい答えを見つけるのにうまく (償却されて) いるバージョンは、良いことです。

SQL Server 2008 で、 GEOMETRY列とその計算されたバリエーションを含むテーブルを作成しようとしています。

計算された列がバッファリングされたジオメトリを返す次の表を検討してください。

これに関する問題は、次のエラーが発生することです。

メッセージ 4994、レベル 16、状態 1、行 2 テーブル 'Test' の計算列 'BufferedGeometry' は、列の型 'geometry' がバイト順でない CLR 型であるため、永続化できません。

BOL と Web を検索しましたが、問題の解決策が見つからないようです。効果的にインデックスを作成できるように、永続化したいと思います。コードで設定できますが、ある時点で両方の値が必要になるため、データの一貫性が失われる可能性があります。

誰でもこれで遊んで、解決策または回避策を知っていますか?

更新: Microsoft は、SQL Server 2012 にこの機能を追加しました。

多くの移動オブジェクト (球体、三角形、ボックス、点など) を処理するのに最適なデータ構造は何だろうと考えていました。Nearest Neighbor と Collsion detection という 2 つの質問に答えようとしています。

伝統的に、R ツリーのようなデータ構造は最近傍クエリに使用され、Oct/Kd/BSP は静的オブジェクトまたは非常に少数の移動オブジェクトを扱う衝突検出問題に使用されることを認識しています。

他にもっと良いものがあることを願うばかりです。

私はすべての助けに感謝します。

オブジェクトのコレクションがあります。各オブジェクトは、座標範囲 (つまり、ブロック) を表します。私が望むのは、特定の方向の別の座標の近くにあるオブジェクトを見つけることです。

コレクション全体を常にトラバースせずにこれを行う方法はありますか?

2Dポイントがたくさんあるので、特定の長方形にあるポイントをすばやく取得したいと思います。「。」としましょう。は任意の点であり、「X」は、TopLeftとして「T」、BottomRight点として「B」を持つ長方形の内側で見つけたい点です。

セットの最初にTopLeftポイントをソートし、最後にBottomRightをソートするソートファンクターを使用してstd::setを試しました。最初にX値でソートすると、次のポイントが見つかります。

これは、見つかった各ポイントが実際に長方形の内側にあるかどうかを確認する必要があることを意味します。あまりよくありません。

これを行うためのより良い方法は何でしょうか？

私の言語はC++（Windows）で、STLとブーストを利用できます。

アップデート

これまでの回答を読んだ後、問題のすべてのパラメーターを考慮していないことに気付きました。固定された長方形が1つではありません。長方形は、実行時にユーザーが設定できます。これは、この更新の前にArteliusによって提案されたように、ポイントのセットをソートすることは、すべてのポイントを線形検索するよりも効率的であることが約束されていることを意味します。それでも試してみます！ユーザーが長方形を頻繁に設定することはないと思います。したがって、実装作業に関しては、それが私にとって良い解決策であることがわかるかもしれません。

Sql Server 2008 は、新しいジオメトリおよび地理 UDT で空間データをサポートします。どちらも AsGml() メソッドをサポートして、データを gml 形式でシリアル化します。ただし、データを GML3 形式にシリアル化します。データを GML2 形式にシリアル化するように指示する方法はありますか?

私は現在、SQL Server 2008 地理タイプを処理する必要があるプロジェクトに取り組んでいます。プロジェクトの大部分が ORM として NHibernate を使用しているため、このタイプで NHibernate.Spatial を使用/拡張するのにどれだけの作業が必要になるのだろうか (私が見る限り、Nh Spatial はまだジオメトリ タイプしかサポートしていません)。ところで。このSQLタイプをサポートする他の.net ORMはありますか? ありがとう

最初から、衝突検出は O(n^2) の問題のように感じます。

多数のオブジェクトがあり、各オブジェクトが他のオブジェクトと衝突しているかどうかを確認する必要があります。ただし、各オブジェクトを他のすべてのオブジェクトに対してチェックするのは非常に非効率的であることを私は知っています。2 つのボールが互いに近くにさえないのに、なぜ比較的コストのかかる 2 つのボール間の衝突チェックを行うのでしょうか?

私が取り組んでいる簡単なプログラムの例を次に示します。

1000 個のボールがある場合、単純な衝突検出を使用すると、1000^2 (100 万) のコレクション チェックが発生します。この衝突チェックは、すぐに私のアプリケーションのボトルネックになりました。大まかなフェーズの剪定を実装する必要があります。

2D の円形オブジェクトで作業する場合、衝突チェックを削除するにはどのようなテクニックを使用する必要がありますか? QuadTrees、BSP、空間ハッシュなどについて読んだことがありますが、このユースケースに最も適した方法を整理するのは困難です。

何が最も効果的かについて誰か知っている人はいますか?