Четырехдерево

Четырехдерево
Тип	Дерево
Изобретенный	1974
Изобретён	Рафаэль Финкель и Джей Эл Бентли
Временная сложность в обозначении большого О Операция Средний Худший случай Пространственная сложность

Квадродерево точки-области с точечными данными. Вместимость ковша 1.

Пошаговое сжатие изображения Quadtree. Слева показано сжатое изображение с ограничивающими рамками дерева, а справа показано только сжатое изображение.

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

Подразделенные области могут быть квадратными или прямоугольными или могут иметь произвольную форму. Эта структура данных была названа квадродеревом Рафаэлем Финкелем и Дж. Л. Бентли в 1974 году. Подобное разбиение также известно как Q-дерево .

Все формы квадродеревьев имеют некоторые общие черты:

• Они разлагают пространство на адаптируемые клетки.
• Каждая ячейка (или ведро) имеет максимальную вместимость. При достижении максимальной вместимости ведро разбивается.
• Каталог дерева соответствует пространственной декомпозиции квадродерева.

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

Типы

Пример рекурсивного квадродерева разделения двоичного пространства для двумерного индекса.

Квадродеревья можно классифицировать по типу данных, которые они представляют, включая области, точки, линии и кривые. Квадродеревья также можно классифицировать по тому, не зависит ли форма дерева от порядка обработки данных. Ниже приведены распространенные типы квадродеревьев.

Квадродерево регионов

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

Квадродерево региона глубиной n может использоваться для представления изображения, состоящего из 2 ^н × 2 ^н пикселей, где значение каждого пикселя равно 0 или 1. Корневой узел представляет всю область изображения. Если пиксели в какой-либо области не полностью имеют 0 или 1, она подразделяется. В этом приложении каждый листовой узел представляет собой блок пикселей, все из которых имеют 0 или 1. Обратите внимание на потенциальную экономию места при использовании этих деревьев для хранения изображений; изображения часто имеют множество областей значительного размера, которые имеют одинаковое значение цвета повсюду. Вместо того, чтобы хранить большой двумерный массив каждого пикселя изображения, квадродерево может захватывать ту же информацию, потенциально на много уровней деления выше, чем ячейки с разрешением в пикселях, которые нам в противном случае потребовались бы. Разрешение и общий размер дерева ограничены размерами пикселей и изображения.

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

Квадродерево точек

Точечное квадродерево представляет собой адаптацию двоичного дерева, используемого для представления двумерных точечных данных. Оно обладает чертами всех квадродеревьев, но является настоящим деревом, поскольку центр подразделения всегда находится в точке. Часто он очень эффективен при сравнении двумерных упорядоченных точек данных, обычно работающих за время O (log n) . Стоит упомянуть квадродеревья точек из-за полноты, но их превзошли k деревья -d как инструменты обобщенного бинарного поиска.

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

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

Структура узлов для квадродерева точек

Узел точечного квадранта аналогичен узлу бинарного дерева , с той основной разницей, что он имеет четыре указателя (по одному на каждый квадрант) вместо двух («левый» и «правый»), как в обычном бинарном дереве. . Также ключ обычно разбивается на две части, ссылаясь на координаты x и y. Таким образом, узел содержит следующую информацию:

• четыре указателя: Quad['NW'], Quad['NE'], Quad['SW'] и Quad['SE']
• точка; который, в свою очередь, содержит:
  • ключ; обычно выражается как координаты x, y
  • ценить; например имя

Квадродерево точки-региона (PR)

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

Краевое квадродерево

Краевые квадродеревья (так же, как квадродеревья PM) используются для хранения линий, а не точек. Кривые аппроксимируются путем разделения ячеек с очень высоким разрешением, особенно до тех пор, пока на ячейку не будет приходиться один сегмент линии. Вблизи углов/вершин рёберные квадродеревья будут продолжать делиться, пока не достигнут максимального уровня разложения. Это может привести к крайне несбалансированным деревьям, что может привести к срыву цели индексации.

Квадродерево полигональной карты (PM)

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

Существует три основных класса PM Quadtrees, которые различаются в зависимости от того, какую информацию они хранят в каждом черном узле. Кваддеревья PM3 могут хранить любое количество непересекающихся ребер и не более одной точки. Деревья квадроциклов PM2 аналогичны деревьям квадроциклов PM3, за исключением того, что все ребра должны иметь одну и ту же конечную точку. Наконец, квадродеревья PM1 похожи на PM2, но черные узлы могут содержать точку и ее ребра или просто набор ребер, которые имеют общую точку, но вы не можете иметь точку и набор ребер, которые не содержат эту точку.

Сжатые деревья квадрантов

В этом разделе обобщены подразделы из книги Сариэля Хар-Пеледа .

Если бы нам пришлось хранить каждый узел, соответствующий разделенной ячейке, мы могли бы в конечном итоге сохранить много пустых узлов. Мы можем сократить размер таких редких деревьев, сохраняя только те поддеревья, листья которых содержат интересные данные (т.е. «важные поддеревья»). На самом деле мы можем еще больше сократить размер. Когда мы сохраняем только важные поддеревья, процесс сокращения может оставить длинные пути в дереве, где промежуточные узлы имеют степень два (ссылка на одного родительского и одного дочернего элемента). Получается, что нам нужно хранить только узел $u$ в начале этого пути (и свяжите с ним некоторые метаданные для представления удаленных узлов) и прикрепите поддерево, коренящееся в его конце, к $u$. Эти сжатые деревья по-прежнему могут иметь линейную высоту при наличии «плохих» входных точек.

Хотя при выполнении этого сжатия мы обрезаем большую часть дерева, все же можно добиться логарифмического поиска, вставки и удаления, используя преимущества Z кривых -порядка . Кривая Z -порядка отображает каждую ячейку полного квадродерева (и, следовательно, даже сжатого квадродерева) в $O(1)$ время в одномерную линию (и отображает ее обратно в $O(1)$ время тоже), создавая полный порядок в элементах. Следовательно, мы можем хранить квадродерево в структуре данных для упорядоченных наборов (в которой мы храним узлы дерева).

Прежде чем продолжить, мы должны сформулировать разумное предположение: мы предполагаем, что даны два действительных числа. $\alpha ,\beta \in [0,1)$ выраженный в двоичном виде, мы можем вычислить в $O(1)$ time индекс первого бита, которым они отличаются. Мы также предполагаем, что мы можем вычислить в $O(1)$ найдите наименьшего общего предка двух точек/ячейок в квадродереве и установите их относительный Z -упорядочение, и мы сможем вычислить функцию пола в $O(1)$ время.

При этих предположениях местоположение данной точки $q$ (т.е. определение ячейки, которая будет содержать $q$), операции вставки и удаления могут выполняться в $O(\log {n})$ время (т.е. время, необходимое для поиска в базовой структуре данных упорядоченного набора).

Чтобы выполнить локацию точки для $q$ (т.е. найти его ячейку в сжатом дереве):

1. Найдите существующую ячейку в сжатом дереве, которая была раньше. $q$ в Z -порядке. Позвоните на этот сотовый $v$.
2. Если $q\in v$, возвращаться $v$.
3. В противном случае найдите то, что было бы наименьшим общим предком точки. $q$ и клетка $v$ в несжатом дереве квадрантов. Назовите эту клетку-предка $u$.
4. Найдите существующую ячейку в сжатом дереве, которая была раньше. $u$ в Z -порядке и верните его.

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

Некоторые распространенные варианты использования квадродеревьев

• Представление изображения
  
• Обработка изображений
• Генерация сетки
• Пространственное индексирование , запросы местоположения точек и запросы диапазона.
• Эффективное обнаружение столкновений в двух измерениях
• Просмотр отсечения данных о местности по усечению пирамиды
• Хранение разреженных данных, таких как информация о форматировании электронной таблицы. или для некоторых матричных вычислений
• Решение многомерных полей ( вычислительная гидродинамика , электромагнетизм )
• Программа моделирования «Игры жизни» Конвея .
• Оценка состояния
• Квадродеревья также используются в области фрактального анализа изображений.
• Максимальные непересекающиеся множества

Обработка изображений с использованием квадродеревьев

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

Объединение/пересечение изображений

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

Алгоритм работает путем обхода двух входных квадродеревьев ( $T_{1}$ и $T_{2}$) при построении выходного квадродерева $T$. Неформально алгоритм следующий. Рассмотрим узлы $v_{1}\in T_{1}$ и $v_{2}\in T_{2}$ соответствующие одной и той же области на изображениях.

• Если $v_{1}$ или $v_{2}$ черный, соответствующий узел создается в $T$ и окрашен в черный цвет. Если только один из них черный, а другой серый, серый узел будет содержать поддерево. Это поддерево не обязательно пересекать.
• Если $v_{1}$ (соответственно, $v_{2}$) белый, $v_{2}$ (соответственно, $v_{1}$), а поддерево под ним (если есть) копируется в $T$ .
• Если оба $v_{1}$ и $v_{2}$ серые, то соответствующие потомки $v_{1}$ и $v_{2}$ считаются.

Хотя этот алгоритм работает, он сам по себе не гарантирует квадродерево минимального размера. Например, рассмотрим результат, если бы мы объединили шахматную доску (где каждая плитка представляет собой пиксель) размером $2^{k}\times 2^{k}$ с его дополнением. В результате получается гигантский черный квадрат, который должен быть представлен квадродеревом только с корневым узлом (окрашенным в черный цвет), но вместо этого алгоритм создает полное 4-арное дерево глубины. $k$. Чтобы исправить это, мы выполняем обход результирующего квадродерева снизу вверх, где проверяем, имеют ли четыре дочерних узла одинаковый цвет, и в этом случае мы заменяем их родительский элемент листом того же цвета.

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

Маркировка подключенных компонентов

Рассмотрим два соседних черных пикселя в бинарном изображении. Они являются смежными, если имеют общий ограничивающий горизонтальный или вертикальный край. В общем, два черных пикселя соединяются , если до одного можно добраться из другого, перемещаясь только к соседним пикселям (т. е. между ними существует путь черных пикселей, где каждая последовательная пара является соседней). Каждый максимальный набор связанных черных пикселей является связным компонентом . Используя представление изображений в виде квадродерева, Самет показал, как мы можем найти и пометить эти связные компоненты за время, пропорциональное размеру квадродерева. Этот алгоритм также можно использовать для раскраски полигонов.

Алгоритм работает в три этапа:

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

Чтобы упростить обсуждение, предположим, что дочерние элементы узла в квадродереве следуют Z -порядку (ЮЗ, СЗ, ЮВ, СВ). Поскольку мы можем рассчитывать на эту структуру, мы знаем, как перемещаться по дереву квадрантов для любой ячейки, чтобы найти соседние ячейки на разных уровнях иерархии.

Первый шаг завершается пост-заказным обходом дерева квадрантов. За каждый черный лист $v$ мы смотрим на узел или узлы, представляющие ячейки, которые являются северными соседями и восточными соседями (т. е. северные и восточные ячейки, которые имеют общие ребра с ячейкой $v$). Поскольку дерево организовано в Z -порядке, у нас есть инвариант, согласно которому южные и западные соседи уже позаботились и учтены. Пусть рассматриваемым в настоящее время северным или восточным соседом будет $u$. Если $u$ представляет черные пиксели:

• Если только один из $u$ или $v$ имеет метку, присвойте эту метку другой ячейке
• Если ни у одного из них нет меток, создайте одну и назначьте ее обоим.
• Если $u$ и $v$ имеют разные метки, запишите эквивалентность этой метки и двигайтесь дальше

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

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

Генерация сетки с использованием квадродеревьев

В этом разделе обобщена глава из книги Хар-Пеледа и де Берга и др.

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

Сбалансированный лист имеет не более одного угла на стороне.

Рассмотрим лист квадродерева и соответствующую ему ячейку $v$. Мы говорим $v$ является сбалансированным (для построения сетки), если стороны ячейки пересекаются угловыми точками соседних ячеек не более одного раза с каждой стороны. Это означает, что уровни квадродеревьев листьев, прилегающих к $v$ отличаться не более чем на единицу от уровня $v$. Когда это верно для всех листьев, мы говорим, что все квадродерево сбалансировано (для генерации сетки).

Рассмотрим ячейку $v$ и $5\times 5$ окрестности ячеек одинакового размера с центром в $v$. Мы называем эту окрестность расширенным кластером . Мы говорим, что квадродерево хорошо сбалансировано, если оно сбалансировано, и для каждого листа $u$ который содержит точку из набора точек, его расширенный кластер также находится в квадродереве, и расширенный кластер не содержит других точек из набора точек.

Создание сетки происходит следующим образом:

1. Постройте квадродерево по входным точкам.
2. Убедитесь, что дерево квадрантов сбалансировано. Для каждого листа, если есть слишком большой сосед, разделите его. Это повторяется до тех пор, пока дерево не будет сбалансировано. Мы также следим за тем, чтобы для листа, в котором есть точка, узлы расширенного кластера каждого листа находились в дереве.
3. Для каждого листового узла $v$ которое содержит точку, если расширенный кластер содержит другую точку, мы далее подразделяем дерево и при необходимости перебалансируем. Если бы нам нужно было разделить, для каждого ребенка $u$ из $v$ мы обеспечиваем узлы $u$расширенный кластер находятся в дереве (и при необходимости перебалансируются).
4. Повторяйте предыдущий шаг, пока дерево не станет хорошо сбалансированным.
5. Преобразуйте квадродерево в триангуляцию.

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

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

В конце всего этого у нас есть красивая триангулированная сетка нашего набора точек, построенная из квадродерева.

Псевдокод

Следующий псевдокод показывает один из способов реализации квадродерева, обрабатывающего только точки. Существуют и другие подходы.

Предварительные условия

Предполагается, что эти структуры используются.

// Simple coordinate object to represent points and vectors
struct XY
{
    float x;
    float y;

    function __construct(float _x, float _y) {...}
}

// Axis-aligned bounding box with half dimension and center
struct AABB
{
    XY center;
    float halfDimension;

    function __construct(XY _center, float _halfDimension) {...}
    function containsPoint(XY point) {...}
    function intersectsAABB(AABB other) {...}
}

Класс QuadTree

Этот класс представляет как одно четырехъядерное дерево, так и узел, в котором оно находится.

class QuadTree
{
    // Arbitrary constant to indicate how many elements can be stored in this quad tree node
    constant int QT_NODE_CAPACITY = 4;

    // Axis-aligned bounding box stored as a center with half-dimensions
    // to represent the boundaries of this quad tree
    AABB boundary;

    // Points in this quad tree node
    Array of XY [size = QT_NODE_CAPACITY] points;

    // Children
    QuadTree* northWest;
    QuadTree* northEast;
    QuadTree* southWest;
    QuadTree* southEast;

    // Methods
    function __construct(AABB _boundary) {...}
    function insert(XY p) {...}
    function subdivide() {...} // create four children that fully divide this quad into four quads of equal area
    function queryRange(AABB range) {...}
}

Вставка

Следующий метод вставляет точку в соответствующий квадрат дерева квадроциклов, при необходимости разбивая его.

class QuadTree
{
    ...
  
    // Insert a point into the QuadTree
    function insert(XY p)
    {
        // Ignore objects that do not belong in this quad tree
        if (!boundary.containsPoint(p))
            return false; // object cannot be added
    
        // If there is space in this quad tree and if doesn't have subdivisions, add the object here
        if (points.size < QT_NODE_CAPACITY && northWest == null)
        {
            points.append(p);
            return true;
        }
    
        // Otherwise, subdivide and then add the point to whichever node will accept it
        if (northWest == null)
            subdivide();
        // We have to add the points/data contained in this quad array to the new quads if we only want
        // the last node to hold the data
    
        if (northWest->insert(p)) return true;
        if (northEast->insert(p)) return true;
        if (southWest->insert(p)) return true;
        if (southEast->insert(p)) return true;
    
        // Otherwise, the point cannot be inserted for some unknown reason (this should never happen)
        return false;
    }
}

Диапазон запроса

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

class QuadTree
{
    ...
  
    // Find all points that appear within a range
    function queryRange(AABB range)
    {
        // Prepare an array of results
        Array of XY pointsInRange;
    
        // Automatically abort if the range does not intersect this quad
        if (!boundary.intersectsAABB(range))
            return pointsInRange; // empty list
    
        // Check objects at this quad level
        for (int p = 0; p < points.size; p++)
        {
            if (range.containsPoint(points[p]))
                pointsInRange.append(points[p]);
        }
    
        // Terminate here, if there are no children
        if (northWest == null)
            return pointsInRange;
    
        // Otherwise, add the points from the children
        pointsInRange.appendArray(northWest->queryRange(range));
        pointsInRange.appendArray(northEast->queryRange(range));
        pointsInRange.appendArray(southWest->queryRange(range));
        pointsInRange.appendArray(southEast->queryRange(range));
    
        return pointsInRange;
    }
}

См. также

• Адаптивное уточнение сетки
• Разделение двоичного пространства
• Бинарная мозаика
• k -d дерево
• Октри
• R-дерево
• UB-дерево
• Пространственная база данных
• Мощение
• Кривая Z-порядка

Ссылки

Опросы Алуру и Самет дайте хороший обзор квадродеревьев.

Общие ссылки

1. Рафаэль Финкель и Дж. Л. Бентли (1974). «Четверные деревья: структура данных для поиска по составным ключам». Акта Информатика . 4 (1): 1–9. дои : 10.1007/BF00288933 . S2CID   33019699 .
2. Марк де Берг , Марк ван Кревелд , Марк Овермарс и Отфрид Шварцкопф (2000). Вычислительная геометрия (2-е исправленное изд.). Издательство Спрингер . ISBN  3-540-65620-0 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) Глава 14: Quadtrees: стр. 291–306.
3. Самет, Ханан ; Уэббер, Роберт (июль 1985 г.). «Хранение коллекции полигонов с использованием квадродеревьев» (PDF) . Проверено 23 марта 2012 г.