0

照合する 2 つの幾何学的データ セットがあり、両方とも何万もの PathGeometry を含んでいます。正確には、あるセットから別のセットにオーバーラップする領域を見つける必要があるため、次のようなループが得られました

foreach (var p1 in firstGeometries)
{
  foreach (var p2 in secondGeometries)
  {
      PathGeometry sharedArea = PathGeometry.Combine(p1, p2, GeometryCombineMode.Intersect, null);
      if (sharedArea.GetArea() > 0) // only true 0.01% of the time
      {
        [...]
      }
  }
}

さて、私のデータの性質上、99.99% の確率で組み合わせがまったく交差しません。プロファイリングは、これがこの計算の最も「高価な」部分であると私に言いました。

2 つの PathGeometry 間の衝突検出を高速化または高速化する方法はありますか?

4

5 に答える 5

2

Geometry クラスに慣れてきたので、新しい回答を追加します。まず、境界ボックスを使用して交差をテストします。正直なところ、PathGeometry.Combine はおそらく既にこれを行っています。では、本当の問題は何ですか？各オブジェクトの境界を他のすべてのオブジェクトの境界に対してテストすることは、二次時間です。代わりに四分木を使用して交差 (または CS の一部の領域での衝突) を見つけた場合、パフォーマンスが大幅に向上する可能性があります。ただし、テストと微調整なしで言うのは難しいです。http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/

于 2013-10-14T17:18:07.793 に答える
1

複数の CPU コアを使用できる場合は、Parallel.ForEachメソッドを使用できます。

于 2011-10-07T11:35:30.790 に答える
0

これを行うには、間違いなく「広いフェーズと狭いフェーズ」が必要です。このような場合、バウンディング ボックス チェックは必須です。四分木に代わるはるかに単純な方法は、「空間ハッシュ」(「空間インデックス」とも呼ばれる) を使用することです。この手法により、必要な時間が 1000 分の 1 に短縮されます。参考用: http://www.playchilla.com/as3-spatial-hash AS3 ですが、C# に変換するのは簡単です。

于 2013-10-19T03:13:42.420 に答える
0

各パス ジオメトリの正確な性質についてはわかりませんが、ポリゴンであると仮定します。

境界に基づいて各オブジェクトを並べ替えることができます。if (sharedArea.GetArea() > 0)このようにして、条件が失敗すると、内側のループの残りの要素が 0 より大きい面積を生成しないことが保証されるため、ループから抜け出すことができます。

ほとんどの場合、この条件は失敗する可能性が高いため、実行時間が大幅に改善されます。

于 2011-10-07T11:40:52.717 に答える
0

私はそれをテストしていませんが、代わりにGetFlattenedPathGeometryを使用してその結果を組み合わせると役立つ場合があります。結合するジオメトリのタイプによっては、毎回多角形の近似に変換される可能性があります。事前に GetFlattenedPathGeometry を使用すると、冗長な計算をなくすことができます。

于 2013-09-17T15:32:21.640 に答える