Эффективная структура данных для объектов в 2D-пространстве

Question

У меня есть 2D-пространство с объектами, у каждого объекта есть вектор координат и массив вершин относительно его координаты, теперь мне нужен эффективный способ хранения объектов, этот магазин должен иметь возможность добавлять и удалять объекты, а такженаиболее важной частью является обнаружение столкновений:

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

O([number of objects with collision chance] * log([number of all objects])), поэтому, когда нет близких объектов, нужно сделать это за O(1), а не методом грубой силы, просто перебрав все объекты в O(n).

Askесли что-то неясно.

Может быть, вы знаете какую-нибудь ссылку на эту тему или какие-нибудь хорошие идеи.

Спасибо.

Answer 1

вы можете использовать quadtree для этого, чтобы проверить все близлежащие объекты.

Answer 2

Вы хотите использовать пространственный индекс или квадродерево.Квадродерево может быть простой кривой заполнения пространства (sfc) или кривой Гильберта.SFC уменьшает сложность 2d до сложности 1d и используется во многих приложениях карт или тепловых картах.SFC также может быть использован для хранения поиска по почтовому индексу.Вы хотите найти блог пространственного индекса квадричного дерева кривой Гильберта.

Answer 3

Вы можете использовать древовидную структуру данных с помощью разбиения двоичного пространства, о ней статья в Википедии . Насколько мне известно, это наиболее эффективный способ хранения информации о расположении объектов в n-мерном пространстве.

Вот как это работает. Допустим, у вас есть следующее поле

Допустим, у вас есть пробел 100x100.

У вас там 6 объектов с координатами от A до F А (25,25) В (25,75), С (25,85), D (75,75), E (90,60)

Теперь мы разделим наше пространство на 4 части, каждая часть будет дочерним узлом корневого узла в дереве. Верхний левый угол содержит только точку А, так что это щит с одним листом. нижний левый угол содержит 2 объекта, B и C, поэтому они будут листовыми узлами второго щита. Теперь в правом нижнем углу будет 3 элемента, которые нам не нужны из-за идеи двоичного дерева, поэтому мы сделаем еще одно подразделение. Делая это рекурсивно, вы получаете очень эффективную структуру данных для поиска объектов в 2D-пространстве.

Answer 4

Физика бурундука и Box2D оба предлагают эффективное 2D обнаружение столкновений.Вы можете использовать один из них или просто проверить их источник.