Движение объекта Quadtree

Question

Так что мне нужна помощь в мозговом штурме с теоретической точки зрения. Прямо сейчас у меня есть код, который просто рисует некоторые объекты. Объекты лежат в листьях дерева. Теперь, когда объекты движутся, я хочу сохранить их в правильном листе дерева квадрантов.

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

Кто-нибудь имеет представление о том, как определить узел, в который перемещается объект, не имея повсюду тонны указателей или ссылки на статьи по этому вопросу? Все, что я мог найти, - это разные способы построения квадродерева, ничего об его обновлении.

Answer 1

Если я понимаю ваш вопрос.Вам нужен какой-то способ отображения между пространственными координатами и листьями на квадродереве.

Вот одно из возможных решений, на которое я смотрел:

Для простоты, давайте сначала сделаем 1D случай.И давайте предположим, что у нас есть 32 точки сетки в x.Каждая точка сетки тогда соответствует некоторому листу на квадродереве глубины пять.(глубина 0 = вся сетка, глубина 1 = 2 точки, глубина 2 = 4 точки ... глубина 5 = 32 точки).

Каждый лист может быть представлен индексами ветвей, ведущими к листу.На каждом уровне есть две ветви, которые мы можем обозначить A и B. Таким образом, конкретный лист может быть помечен BBAAB, что будет означать переход вниз по ветви B, затем ветви B, затем ветви A, затем ветви B и затемветвь B.

Итак, как вы сопоставляете, например, BBABB с точкой сетки x между 0..31?Просто преобразуйте его в двоичный файл, чтобы BBABB-> 11011 = 27. Таким образом, преобразование точки сетки в конечный узел - это просто вопрос перевода букв A и B в 0 и 1, а затем интерпретации результата как двоичного числа.

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

Теперь, чтобы преобразовать строку (например, 'CDABB') в пару значений сетки (x, y).

Предположим, что A - это левый нижний угол, B - правый нижний угол, C - левый верхний угол, а D - правый верхний угол.Тогда, символически, мы могли бы написать: Ax = 0, Ay = 0 / Bx = 1, By = 0 / Cx = 0, Cy = 1 / Dx = 1, Dy = 1.

На примере CDABBСначала мы рассмотрим его значения x (CDABB) .x = (01011), что дает нам точку сетки x.И аналогично для y.

Наконец, если вы хотите выяснить, например, узел непосредственно справа от CDABB, а затем просто преобразовать его в пару двоичных чисел в x и y, добавьте +1 к xзначение и преобразовать новую пару двоичных чисел обратно в строку.

Я уверен, что все это было обнаружено, но я еще не нашел эту информацию в Интернете.

Answer 2

Если у вас есть пространственные данные, необходимые для вставки элемента в четырехугольник в первую очередь (например, его точка или прямоугольник), то у вас есть те же данные, которые необходимы для его удаления.

AnПроще всего перед тем, как переместить элемент, удалите его из четырехугольного дерева, используя те же данные, которые использовались для его первоначальной вставки, затем переместите его, а затем вставьте заново.

Сначала можно удалить из четырехугольного дерева.удалите элемент из конечных узлов, затем, если конечные узлы станут пустыми, удалите их из родительских узлов.Если родители становятся пустыми, удалите их от своих родителей и т. Д.

Этот простой метод достаточно эффективен для сложного мира объектов, перемещающихся в каждом кадре, до тех пор, пока вы эффективно реализуете квад-дерево (например:используйте свободный список для узлов).Для его вставки не должно быть выделение кучи для каждого узла или освобождение кучи для удаления каждого отдельного узла.Большинство распределений / освобождений узлов должны быть простыми операциями с постоянным временем, включающими, скажем, манипуляции с парой целых чисел или указателей.

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

Обновление

Обычно я стараюсь не связывать свои предыдущие ответы, но в этом случае я в конечном итоге делалдовольно подробное описание темы, которую трудно воспроизвести где-либо еще.Вот оно: https://stackoverflow.com/a/48330314/4842163