Да - либо так, либо при вставке разделите свой квадрат на 4 отдельных в этом случае. Проще просто разрешить хранение дубликатов на листьях и сделать это дешевым (например, указатель/индекс на квадрат)
Вы также можете создать свободное дерево, в котором вы просто выбираете одного из дочерних элементов, чтобы вставить этот квадрат, но расширяете его ограничивающую рамку, чтобы он соответствовал. В этих случаях у вас есть перекрывающиеся разделы, и вам нужно рекурсивно спускаться вниз по дереву для поиска, так что у этого есть свои плюсы и минусы.
Еще одна вещь, которую вы можете сделать, это разрешить хранение элементов в ветвях, а не только в листьях. В этом случае, если элемент хочет перейти к нескольким дочерним элементам, просто сохраните его в ветке, а не опускайтесь дальше. Для этого вам нужно проверять элементы на каждой ветви во время обхода, а не только на листьях.
Я бы посоветовал начать с дубликатов. Другие методы могут быть настоящими хлопотами, и не нужно заморачиваться с такими хлопотами (пока вы не измерите потребность в этом).
Элементы такого типа, которые имеют область в мертвой точке любой ветви, могут сделать ваше дерево действительно глубоким и несбалансированным, поэтому вам обычно нужен здоровый стоп-зазор, чтобы предотвратить его повторение навсегда. Как правило, это не большая проблема, если у вас нет множества таких элементов.
Кроме того, для 2D-случаев иногда можно обойтись фиксированной сеткой. На самом деле иногда может работать лучше просто иметь сетку NxM, чем квадродерево, поскольку его очень просто построить (что упрощает быстрое обновление для очень динамичного контента, когда у вас есть, скажем, спрайты, перемещающиеся по экрану каждый кадр) , и не имеет сложных сценариев наихудшего случая, поскольку в нем нет понятия «глубина», а только ячейки, содержащие элементы.
person
Community
schedule
22.11.2015
