#algorithm #data-structures #2d #complexity-theory #collision-detection
#алгоритм #структуры данных #2d #теория сложности #обнаружение столкновений
Вопрос:
У меня есть 2D пространство с объектами, каждый объект имеет вектор координат и массив вершин относительно его координаты, теперь мне нужен эффективный способ хранения объектов, это хранилище должно иметь возможность добавлять и удалять объекты, также наиболее важной частью является обнаружение столкновений:
Я хочу получить список объектов, которые имеют шанс столкнуться (близкий сосед и т.д.), Должен быть быстрым и простым примерно в
O([number of objects with collision chance] * log([number of all objects])) таким образом, когда нет близких объектов, это должно выполняться в O(1) , а не методом перебора всех объектов O(n) .
Спрашивайте, если что-то непонятно.
Может быть, вы знаете какую-нибудь ссылку по этому вопросу или какие-нибудь хорошие идеи.
Спасибо.
Ответ №1:
вы могли бы использовать quadtree для этого, чтобы проверить все близлежащие объекты.
Ответ №2:
Chipmunk Physics и Box2D предлагают эффективное обнаружение столкновений 2D. Вы могли бы либо использовать один из них, либо просто проверить их источник.
Ответ №3:
Вы можете использовать древовидную структуру данных, используя двоичное разделение пространства, вот статья в Википедии об этом. Насколько мне известно, это наиболее эффективный способ хранения информации о местоположении объектов в n-мерном пространстве.
Вот как это работает: допустим, у вас есть следующее поле
Допустим, у вас есть пространство размером 100×100.
У вас есть 6 объектов с именами от A до F и координатами A (25,25), B (25,75), C (25,85), D (75,75), E (90,60)
Теперь мы разделим наше пространство на 4 части, каждая часть будет дочерним узлом корневого узла в дереве. Верхний левый угол содержит только точку A, так что это поле с одним конечным узлом. нижний левый угол содержит 2 объекта, B и C, поэтому они будут конечными узлами второго chield. Теперь в нижнем правом углу будут 3 элемента, которые нам не нужны из-за идеи двоичного дерева, поэтому мы делаем другое подразделение. Выполняя это рекурсивно, вы получаете очень эффективную структуру данных для поиска объектов в 2D пространстве.
Ответ №4:
Вы хотите использовать пространственный индекс или дерево квадратиков. Квадродерево может быть простой кривой заполнения пробела (sfc) или кривой Гильберта. SFC уменьшают сложность 2d до сложности 1d и используются во многих приложениях maps или тепловых картах. SFC также может использоваться для хранения результатов поиска по почтовому индексу. Вы хотите выполнить поиск в блоге Nick’s hilbert curve quadtree spatial index.