Ускорить PathGeometry.Combine (c # .net)?

Question

У меня есть два набора геометрических данных, каждый из которых содержит десятки тысяч 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% случаев комбинации вообще не пересекаются. Профилирование говорит мне, что это самая «дорогая» часть этого расчета.

Есть ли способ ускорить или ускорить обнаружение столкновений между двумя PathGeometries?

Answer 1

Добавление нового ответа, так как теперь я больше знаком с классом Geometry.Сначала я бы проверил пересечение, используя их ограничивающие рамки.Хотя, если честно, PathGeometry.Combine, вероятно, уже делает это.Так в чем же проблема?Это проверка границы каждого объекта по отношению к границе любого другого объекта является квадратичным временем.Если вместо этого вы обнаружили пересечения (или коллизии в некоторых областях CS) с использованием квадродерева, вы могли бы получить значительный прирост производительности.Трудно сказать без тестирования и тонкой настройки, хотя.http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/

Answer 2

Может быть, вы можете использовать метод Parallel.ForEach , если у вас имеется более одного доступного ядра процессора.

Answer 3

Вам определенно нужна "широкая и узкая фаза", чтобы сделать это. Проверки ограничивающего прямоугольника являются необходимостью для чего-то подобного. Гораздо более простой альтернативой четырехугольному дереву было бы использование «пространственного хеширования» (иногда также называемого «пространственным индексированием»). Эта техника должна сократить необходимое время в тысячу раз. Для справки: http://www.playchilla.com/as3-spatial-hash Он в AS3, но его просто конвертировать в C #

Answer 4

Я не проверял это, но может быть полезно использовать GetFlattenPathGeometry и объединить результаты этого вместо этого. В зависимости от типа геометрии, которую вы комбинируете, она, вероятно, каждый раз преобразуется в полигональное приближение. Надеемся, что преждевременное использование GetFlattensPathGeometry исключит избыточные вычисления.

Answer 5

Хотя я не уверен в точном характере каждой геометрии пути, но предполагаю, что они являются полигонами:

Вы можете отсортировать каждый объект по его границам.Таким образом, вы уверены, что после сбоя условия if (sharedArea.GetArea() > 0) оставшиеся элементы во внутреннем цикле не будут создавать область больше 0, поэтому вы можете выйти из цикла.

Это значительноулучшить время выполнения, так как в большинстве случаев условие может быть неудачным.