Quadtree с дубликатами

Я реализую квадри. Для тех, кто не знает эту структуру данных, я включаю следующее небольшое описание:

Квадрадерево представляет собой структуру данных , и в евклидовой плоскости , что октодерева находятся в 3-мерном пространстве. Обычное использование четырех деревьев - пространственная индексация.

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

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

Меня беспокоит то, что если вы попытаетесь добавить дубликаты, может ли это быть один и тот же элемент несколько раз или несколько разных элементов с одинаковым положением, у квадродерев есть фундаментальная проблема с обработкой ребер.

Например, если вы работаете с квадродеревом с емкостью 1 и единичным прямоугольником в качестве ограничивающего прямоугольника:

[(0,0),(0,1),(1,1),(1,0)]

И вы попробуйте дважды вставить прямоугольник, верхняя левая граница которого является источником: (или аналогично, если вы попытаетесь вставить его N + 1 раз в квадродерево с емкостью N> 1)

quadtree->insert(0.0, 0.0, 0.1, 0.1)
quadtree->insert(0.0, 0.0, 0.1, 0.1)

Первая вставка не будет проблемой:

Но тогда первая вставка вызовет подразделение (потому что емкость равна 1):

Таким образом, оба прямоугольника помещаются в одно и то же поддерево.

С другой стороны, два элемента прибудут в одно и то же квадродерево и вызовут подразделение…

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

Возможно ли иметь квадродерево с дубликатами? (Если нет, то можно реализовать это как Set)

Как мы можем решить эту проблему, не нарушая полностью архитектуру квадродерева?

Вы реализуете структуру данных, поэтому вы должны принимать решения о реализации.

Если у quadtree есть что-то конкретное, чтобы сказать об уникальности - и я не знаю, что это так - это решение о реализации. Она ортогональна определению квадродерева, и вы можете обрабатывать ее так, как хотите. Дерево quadtree сообщает вам, как вставлять и обновлять ключи, но не указывает, должны ли они быть уникальными или что вы можете прикрепить к каждому узлу.

Принятие решений о внедрении - это не переизобретение колеса , по крайней мере, не более чем написание собственной реализации в первую очередь.

Для сравнения, стандартная библиотека C ++ предлагает уникальный набор, неуникальный мультимножество, уникальную карту (по сути, набор пар ключ-значение, упорядоченных и сравниваемых только по ключу) и неуникальную мультикарту. Все они, как правило, реализуются с использованием одного и того же красно-черного дерева, и ни одно из них не нарушает архитектуру просто потому, что определение красно-черного дерева ничего не говорит о уникальности ключей или типов, хранящихся в конечных узлах.

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

Я думаю, что здесь есть неправильное представление.

Насколько я понимаю, каждый узел дерева квадрантов содержит значение, проиндексированное точкой. Другими словами, он содержит тройку (x, y, значение).

Он также содержит 4 указателя на дочерние узлы, которые могут быть нулевыми. Существует алгоритмическая связь между ключами и дочерними ссылками.

Ваши вставки должны выглядеть следующим образом.

quadtree->insert(0.0, 0.0, value1)
quadtree->insert(0.0, 0.0, value2)

Первая вставка создает (родительский) узел и вставляет в него значение.

Вторая вставка создает дочерний узел, ссылается на него и вставляет в него значение (которое может совпадать с первым значением).

Какой дочерний узел создается, зависит от алгоритма. Если алгоритм имеет форму [x), а пространство координат лежит в диапазоне [0,1), то каждый дочерний элемент будет охватывать диапазон [0,0,5), и точка будет помещена в дочерний элемент NW.

Я не вижу бесконечной рекурсии.

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

Полагаю, главное в том, что это легко сделать.

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

Узлу Quadtree не требуется фиксированная емкость. Емкость используется для

• Разрешить каждому узлу дерева фиксированный размер в памяти или на диске - не требуется, если узел дерева содержит набор элементов переменного размера и вы используете систему распределения пространства, которая справляется. (Например, объекты java / c # в памяти.)
• Решите, когда разделить узел.
  • Вы можете просто переопределить правило так, чтобы узел был разделен, если он содержит больше, чем «n» элементов района, где район определяется в соответствии с расположением элементов.
  • Или используйте « составной элемент», поэтому, если в одном месте есть несколько элементов, вы вводите новый элемент, который содержит список этих элементов.

Когда вы имеете дело с проблемами пространственного индексирования, я действительно рекомендую начинать с пространственного хэша или моего личного фаворита: простой старой сетки.

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

Одним из очевидных недостатков является то, что вы могли бы тратить память на множество пустых ячеек (хотя прилично реализованная сетка не должна требовать более 32 бит на ячейку, если у вас нет фактически вставляемых миллиардов узлов). Другая причина в том, что если у вас есть элементы среднего размера, которые больше, чем размер ячейки, и часто занимают, скажем, десятки ячеек, вы можете тратить много памяти, вставляя эти элементы среднего размера в гораздо большее количество ячеек, чем в идеале. Аналогично, когда вы делаете пространственные запросы, вам, возможно, придется проверять больше ячеек, иногда гораздо больше, чем в идеале.

Но единственное, что нужно сделать с сеткой, чтобы сделать ее как можно более оптимальной по отношению к определенному входу, - это то cell size, что вам не нужно много думать и возиться, и именно поэтому это моя структура данных перехода. для задач пространственного индексирования, пока я не найду причины не использовать его. Это очень просто реализовать и не требует от вас возиться с чем-то большим, чем один ввод времени выполнения.

Вы можете получить много от простой старой сетки, и я на самом деле обошел множество реализаций quad-tree и kd tree, используемых в коммерческом программном обеспечении, заменив их простой старой сеткой (хотя они не обязательно были лучшими из реализованных). , но авторы потратили намного больше времени, чем те 20 минут, которые я потратил, чтобы навести порядок). Вот небольшая небольшая вещь, которую я подхватил, чтобы ответить на вопрос в другом месте, используя сетку для обнаружения столкновений (даже не очень оптимизированную, всего несколько часов работы, и мне пришлось потратить большую часть времени, изучая, как работает поиск пути, чтобы ответить на вопрос и я также впервые реализовал обнаружение столкновений такого рода):

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

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

Когда вы начинаете с сетки и прокладываете путь к чему-то вроде квад-дерева или дерева KD, тогда основная проблема, которую вы хотите решить, - это проблема с элементами, вставляемыми в слишком много ячеек, имеющими слишком много ячеек, и / или нужно проверить слишком много ячеек с этим типом плотного представления.

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