Структура данных, основанная на R-дереве: создание новых дочерних узлов при заполнении узла, но что если у меня много объектов в одной и той же позиции?

Question

Я понимаю, что мой титул не очень понятен, но мне трудно думать о лучшем.Если кто-то хочет исправить это, пожалуйста.

Я разрабатываю структуру данных для моей двухмерной игры с бесконечной вселенной.Структура данных основана на простой (!) Системе узел / лист, такой как R-Tree .

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

Это работает для обычных объектов.Единственная проблема возникает, когда у меня больше, чем maxChildsPerNode объектов с одинаковым расположением X, Y: поскольку узел заполнен, он будет создавать более точные подузлы, но все старые листы будут снова помещены в один и тот же узел, потому что они имеютточно такая же позиция - в результате получается бесконечный цикл создания большего количества узлов и большего количества узлов.

Итак, что мне делать, если я хочу добавить больше листьев, чем maxChildsPerNode с точно такой же позицией в мое дерево?

PS.если я не смог объяснить свою проблему, пожалуйста, сообщите мне, чтобы я мог попытаться улучшить объяснение.

Обновление : таким образом я проверяю, все ли листья в полном узле имеют одинаковые позиции:

//returns whether all leafs in the given leaf list are identical
    private function allLeafsHaveSamePos(leafArr:Array<RTLeaf<T>>):Bool {
        if (leafArr.length > 1) {
            var lastLeafTopX:Float = leafArr[0].topX;
            var lastLeafTopY:Float = leafArr[0].topY;
            for (i in 1...leafArr.length) {
                if ((leafArr[i].topX != lastLeafTopX) || (leafArr[i].topY != lastLeafTopY)) return false;
            }
        }
        return true;
    }

Answer 1

Я хотел бы задать вопрос ...

• это важно, чтобы соблюдалось ограничение maxChildsPerNode?

Я бы лучше подумал об этоммаксимум как подсказка структуре, когда нужно разделить, и просто игнорируйте его, когда нет никакого осмысленного способа выполнить разделение.

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

Answer 2

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

Answer 3

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

Исправление взлома: примените крошечное случайное смещение к вновь созданным объектам. Это должно позволить разделить пространство существующим алгоритмом.

Лучшее исправление: убедитесь, что ваш алгоритм разбиения конечного узла всегда генерирует как минимум 2 новых конечных узла. При переназначении объектов на новые конечные узлы или при выполнении обычных вставок выполняйте итерации по всем кандидатам, и, если более одного подходит одинаково, вы можете сделать привязку к размеру в зависимости от того, насколько они полны. Это должно привести к тому, что ваши расположенные рядом игроки будут равномерно разделены между одинаковыми узлами.

Answer 4

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