Speed up PathGeometry.Combine (c#.net)?

Question

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?

Answer 1

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/

Answer 2

Maybe you can use the Parallel.ForEach method, if you have more than one cpu core avaiable.

Answer 3

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.

Answer 4

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.

Answer 5

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#