Quadtree для 2D обнаружения столкновений - PullRequest
Новая
       29

Quadtree для 2D обнаружения столкновений

32 голосов
/ 13 февраля 2011

Я пытаюсь использовать квадродерево для двумерного обнаружения столкновений, но я немного озадачен тем, как его реализовать. Прежде всего, у меня будет квадродерево, которое содержит четыре поддерева (по одному на каждый квадрант), а также набор объектов, которые не помещаются в одно поддерево.

При проверке объекта на наличие коллизий в дереве я хотел бы сделать что-то вроде этого (спасибо QuadTree за обнаружение коллизий 2D ):

  1. Проверка объекта на столкновения с любыми объектами в текущем узле.
  2. Для любого поддерева, пространство которого перекрывает объект, recurse.

Чтобы найти все коллизии в дереве квадрантов:

  1. Сверьте каждый объект в текущем узле с каждым другим объектом в текущем узле.
  2. Проверка каждого объекта в текущем узле на каждое поддерево.

Для вставки в квадродерево:

  1. Если объект помещается в несколько поддеревьев, добавьте его к текущему узлу и верните.
  2. В противном случае вернитесь в любое поддерево.

Для обновления дерева квадрантов:

  1. Заполните каждое поддерево.
  2. Если какой-либо элемент в текущем узле больше не помещается полностью в текущем дереве, переместите его к родительскому элементу.
  3. Если какой-либо элемент текущего узла помещается в поддерево, вставьте его в поддерево.

Это хорошо? Можно ли это улучшить?

Ответы [ 3 ]

36 голосов
/ 13 февраля 2011

Ваша структура дерева квадрантов не оптимальна.Вы вправе хранить 4 поддерева на узел, но реальные объекты должны храниться только внутри листьев, а не во внутренних узлах.Поэтому коллекцию, содержащую реальные объекты, необходимо переместить в листья.

Давайте посмотрим на реализацию операций :

  1. Вставьте объект в дерево quadtree :Проверьте, пересекает ли объект текущий узел.Если это так, рекурсивно.Если вы достигли уровня листа, вставьте объект в коллекцию.
  2. Удалите объект из дерева quadtree :
    Выполните те же самые шаги, что и при вставке объекта, нокогда вы достигнете конечного уровня, удалите его из коллекции.
  3. Проверьте, не пересекается ли какой-либо объект с каким-либо объектом внутри квадродерева :Выполните те же самые шаги, что и при вставке объекта, но когда вы достигли уровня листьев, проверьте наличие столкновений со всеми объектами в коллекции.
  4. Проверка всех столкновений между всеми объектами внутри дерева квадрантов:Для каждого объекта в quadtree выполните тест на столкновение одного объекта.
  5. Обновите quadtree :Удалите все объекты из дерева квадрантов, позиция которых была изменена, и вставьте их снова.

Это имеет несколько преимуществ :

  • Хранение только объектов вС листьями очень легко обрабатывать операции с квадродеревом (меньше особых случаев)
  • Квадро может иметь листы с различной глубиной, что позволяет адаптировать плотность квадродерева в зависимости от пространственной области, которую он покрывает.Эта адаптация может происходить во время выполнения, таким образом поддерживая оптимальное соотношение объект / узел.

Только disatvantage :

  • Объекты могут принадлежать нескольким коллекциям внутриквадри.Вам понадобится дополнительная линейная коллекция вне дерева квадрантов, чтобы перечислять каждый объект без дубликатов.
7 голосов
/ 15 июня 2015

Quad-деревья не всегда являются лучшей структурой данных для обнаружения столкновений. Служебная нагрузка на квадродерево потенциально может быть неограниченной (если вы не ограничиваете глубину дерева), и в худшем случае не дает никакой скорости вообще. Вместо этого вы можете рассмотреть возможность использования разреженной сетки, которая дает лучшую производительность, чем только для дерева квадрантов, без дополнительных затрат на обход нескольких уровней дерева.

Есть и другие совершенно разные подходы, которые могут быть даже лучше. Например, вы можете попробовать реализовать алгоритм Зомородяна и Эдельсбруннера, как я это делал в следующем модуле:

Вот также несколько статей, которые я написал, которые обсуждают эти вопросы более подробно:

В частности, если вы посмотрите на тесты в последнем разделе, то увидите, что из всех опрошенных библиотек квадри имел тенденцию работать довольно плохо по сравнению с другими методами обнаружения столкновений, такими как R-деревья, сетки или деревья сегментов.

0 голосов
/ 08 мая 2014

Я еще не уверен, насколько эффективен процессор, но, похоже, он отлично работает на моем основном дуэте в Eclipse, но все еще работает на скорости более 2400 кадров в секунду.

По сути, я добавил один список к объектам, которые можно сопоставлять, чтобы хранить ссылки на объекты узлов дерева квадрантов, с которыми я связал объект (путем вставки в дерево квадрантов). Я также добавил список к каждому узлу дерева квадрантов, в котором хранятся ссылки на любые объекты, которые считаются в пределах этого узла. Таким образом, каждый узел будет иметь только одно вхождение каждого объекта. каждый узел также хранит ссылку на свой родительский узел для навигации к соседним узлам, если я хочу проверить любой из них после начального узла для дальнейшей точности столкновения.

очень легко получить ссылки на все другие объекты в одной ячейке: 

list temp_checklist = object.cells[cell_index].objects
//('objects' being some sort of array or list of object references as described above)

надеюсь, что кому-то поможет;)

...