0

我有两个要匹配的几何数据集，都包含数万个 PathGeometries。确切地说，我需要找到从一组重叠到另一组的区域，所以我得到了一个循环

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% 的组合根本不相交。分析告诉我这是这个计算中最“昂贵”的部分。

有什么方法可以加快或获得两个 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

虽然我不确定每个路径几何的确切性质，但假设它们是多边形：

您可以根据边界对每个对象进行排序。这样，你就可以放心，一旦条件if (sharedArea.GetArea() > 0)失败，内循环中的剩余元素不会产生大于 0 的面积，因此你可以跳出循环。

它将显着提高运行时间，因为大多数情况下条件可能会失败。

于 2011-10-07T11:40:52.717 回答
0

我尚未对其进行测试，但使用GetFlattenedPathGeometry并结合其结果可能会有所帮助。根据您组合的几何类型，它可能每次都转换为多边形近似。提前使用 GetFlatnedPathGeometry 有望消除冗余计算。

于 2013-09-17T15:32:21.640 回答
0

你肯定需要一个“广泛而狭窄的阶段”来做到这一点。边界框检查对于这样的事情是必须的。四叉树的一个更简单的替代方法是使用“空间散列”（有时也称为“空间索引”）。这种技术应该将所需的时间减少一千倍。供参考使用：http ://www.playchilla.com/as3-spatial-hash 它在 AS3 中，但将其转换为 C# 很简单

于 2013-10-19T03:13:42.420 回答