加速 PathGeometry.Combine (c#.net)？
我有两个要匹配的几何数据集，都包含数以万计的 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
{
[...]
}
}
}
Now 这样的循环，由于我的数据的性质，99,99% 的情况下组合根本不相交。分析告诉我这是该计算中最“昂贵”的部分。
有什么方法可以加快或更快地检测两个 PathGeometry 之间的碰撞吗？
I've got two geometrical data sets to match, both containing tens of thousands PathGeometries. To be exact I need to find areas which overlap from one set to the other, so I got a loop like
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
{
[...]
}
}
}
Now, due to the nature of my data, 99,99% of the times the combinations do not intersect at all. Profiling told me this is the most 'expensive' part of this calculation.
Is there any way to speed up or get a faster collision detection between two PathGeometries?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
添加新答案，因为我现在对几何类更加熟悉了。首先，我将使用它们的边界框测试相交。老实说，PathGeometry.Combine 可能已经做到了这一点。那么真正的问题是什么？相对于每个其他对象的边界来测试每个对象的边界是二次时间。如果您使用四叉树来发现交叉点（或 CS 某些区域中的碰撞），则可能会获得显着的性能提升。但如果没有测试和微调就很难说。 http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/
Adding a new answer since I'm more familiar with the Geometry class now. First, I'd test for intersection using their bounding boxes. Though honestly, PathGeometry.Combine probably already does this. So what's the real problem? That testing the boundary of each object against the boundary of every other object is quadratic time. If you instead found intersections (or collisions in some areas of CS) using a quadtree, you could have significant performance gains. Hard to say without testing and fine tuning though. http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/
如果您有超过一个CPU核心可用。
Maybe you can use the Parallel.ForEach method, if you have more than one cpu core avaiable.
虽然我不确定每个路径几何形状的确切性质，但假设它们是多边形：
您可以根据每个对象的边界对每个对象进行排序。这样，您就可以放心，一旦条件
if (sharedArea.GetArea() > 0)失败，内循环中的剩余元素将不会产生大于 0 的面积，因此您可以跳出循环。它将显着缩短运行时间，因为大多数情况下该条件可能会失败。
Though I am not sure about the exact nature of each of the path geometry, but assuming that they are polygons:
You can sort each object based on their bounds. This way, you are assured that, once the condition
if (sharedArea.GetArea() > 0)fails, the remaining elements in the inner loop will not produce an area greater than 0, so you can break out of the loop.It will significantly improve the running time, since the condition is likely to fail most of the time.
我还没有测试过它，但使用 GetFlattenedPathGeometry 可能会有所帮助并结合其结果。根据您组合的几何形状的类型，每次都可能会转换为多边形近似值。提前使用 GetFlattenedPathGeometry 将有望消除冗余计算。
I haven't tested it, but it may be helpful to use GetFlattenedPathGeometry and combine the results of that instead. Depending on the type of geometry your combining, it's likely getting converted to a polygonal approximation each time. Using GetFlattenedPathGeometry ahead of time will hopefully eliminate the redundant computation.
你肯定需要一个“广义和狭义阶段”来做到这一点。
对于这样的事情，边界框检查是必须的。
四叉树的一个更简单的替代方案是使用“空间哈希”（有时也称为“空间索引”）。这项技术应该可以将所需的时间减少千倍。仅供参考：http://www.playchilla.com/as3-spatial-hash 它是 AS3 语言，但将其转换为 C# 很简单
You definitely need a "broad and narrow phase" to do this.
Bounding-Box checks are a must for something like this.
A much simpler alternative to a quad tree would be to use "spatial hashing" (sometimes also called "spatial indexing"). This technique should reduce the needed time a thousandfold. For a reference use: http://www.playchilla.com/as3-spatial-hash It's in AS3 but it's trivial to convert it to C#