Дерево квадрантов (также квадродерево, 4-дерево, ) — дерево, в котором у каждого внутреннего узла ровно 4 потомка. Деревья квадрантов часто используются для рекурсивного разбиения двухмерного пространства по 4 квадранта (области). Области представляют собой квадраты, прямоугольники или имеют произвольную форму. Англоязычный термин quadtree был придуман Рафаэлем Финкелем и в 1974 году. Аналогичное разбиение пространства известно как Q-дерево. Общие черты разных видов деревьев квадрантов: разбиение пространства на адаптирующиеся ячейки (), максимально возможный объём каждой ячейки, соответствие направления дерева пространственному разбиению.
Классификация Деревья квадрантов могут быть классифицированы в соответствии с типом данных, который они представляют — пространством, точками, прямыми, кривыми. Также их можно разделить по тому, зависит ли форма дерева от порядка обработки данных. Некоторые виды деревьев квадрантов:
Region quadtree Деревья квадрантов, разбивающие пространство (), представляют какую-либо часть двумерного пространства, разбивая его на 4 квадранта, субквадранты и так далее, причём, каждый лист дерева соответствует определённой области. У каждого узла дерева либо 4 потомка, либо их нет вовсе (у листьев). Деревья квадрантов, разбивающие пространство, не являются деревьями в полной мере, поскольку положение субквадрантов не зависит от данных. Более правильное название — префиксные деревья ().
Дерево высоты n может быть использовано для представления изображения, состоящего из 2n × 2n пикселей, где каждый пиксель имеет значение 0 или 1. Корень дерева представляет всю область изображения. Если не все пиксели - только нули или только единицы, она разбивается. В этом случае каждый лист соответствует множеству пикселей — либо только из нулей, либо только из единиц.
Деревья квадрантов, разбивающие пространство, также могут быть использованы для представления переменного разрешения какого-либо набора данных. Например, информация о температуре может храниться в виде дерева квадрантов, каждый узел которого хранит среднюю температуру дочерних узлов.
Если дерево используется для представления множества точек (например, широты и долготы положений каких-либо городов), области разбиваются до тех пор, пока листья будут содержать не более одной точки.
Point quadtree Деревья квадрантов, хранящие информацию о точках (), — разновидность бинарных деревьев, используемых для хранения информации о точках на плоскости. Форма дерева зависит от порядка задания данных. Использование таких деревьев очень эффективно в сравнении упорядоченных точек плоскости, причём время обработки равно O(n log n).
Структура узла Узел дерева квадрантов, хранящего информацию о точках плоскости, аналогичен узлу бинарного дерева лишь с той оговоркой, что узел первого имеет четыре потомка (по одному на каждый квадрант) вместо двух («правого» и «левого»). Ключ узла состоит из двух компонент (для координат x и y). Таким образом, узел дерева содержит следующую информацию: 4 указателя: quad[‘NW’], quad[‘NE’], quad[‘SW’], и quad[‘SE’], точка, описываемая следующим образом: ключ key, обычно выражает координаты x и y, значение value, например, имя.
Edge quadtree Деревья квадрантов, хранящие информацию о линиях (), используются для описания прямых и кривых. Кривые описываются точными приближениями путём разбиения ячеек на очень мелкие. Это может привести к разбалансировке дерева, что будет означать проблемы с индексацией.
Polygonal map quadtree Деревья квадрантов, хранящие информацию о многоугольниках (), могут содержать информацию о полигонах, в том числе и о вырожденных (имеющих изолированные вершины или грани)Hanan Samet and Robert Webber. “Storing a Collection of Polygons Using Quadtrees”. ACM Transactions on Graphics July 1985: 182-222. InfoLAB. Web. 23 March 2012 .
Варианты использования Представление изображений. Пространственные базы данных. Эффективное обнаружение столкновений в двух измерениях. (). Хранение данных для табличных или матричных вычислений. Вычисления, связанные с многомерными полями (в вычислительной гидродинамике, электромагнетизме). Симуляция игры Жизнь. Вычисление состояний наблюдаемой динамической системыHenning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation, Proceedings of the 13th International Conference on Information Fusion, Edinburgh, United Kingdom, July, 2010.. Анализ частей фрактальных изображений.
Деревья квадрантов являются двухмерным аналогом деревьев октантов ().
Псевдокод Следующий код демонстрирует использование деревьев квадрантов для хранения информации о точках. Возможны и другие подходы к построению.
Структуры данных Предполагается использование следующих структур данных.
// Простая структура для представления точки или вектора struct XY { float x; float y;
function __construct(float _x, float _y) {...}
// Ограничивающий параллелепипед, выровненный по координатным осям // (axis-aligned bounding box, AABB), половинной размерности с центром struct AABB { XY center; XY halfDimension;
function __construct(XY center, XY halfDimension) {...} function containsPoint(XY p) {...} function intersectsAABB(AABB other) {...}
Класс QuadTree Класс представляет собственно 4-дерево и корневой узел.
class QuadTree { // Константа — количество элементов, которые можно хранить в одном узле constant int QT_NODE_CAPACITY = 4;
// Ограничивающий параллелепипед, выровненный по координатным осям, // показывает границы дерева AABB boundary;
// Точки Array of XY [size = QT_NODE_CAPACITY] points;
// Потомки QuadTree* northWest; QuadTree* northEast; QuadTree* southWest; QuadTree* southEast;
// Методы function __construct(AABB _boundary) {...} function insert(XY p) {...} function subdivide() {...} // Создание 4 потомков, делящих квадрант на 4 равные части function queryRange(AABB range) {...}
Вставка Следующий метод осуществляет вставку точки в соответствующий квадрант дерева, осуществляя разбиение, если это необходимо.
class QuadTree { ...
// Вставить точку function insert(XY p)
// Игнорировать объекты, не принадлежащие дереву if (!boundary.containsPoint(p)) return false; // Объект не может быть добавлен
// Если есть место, осуществить вставку if (points.size < QT_NODE_CAPACITY)
points.append(p); return true;
// Далее необходимо разделить область и добавить точку в какой-либо узел if (northWest == null) subdivide();
if (northWest->insert(p)) return true; if (northEast->insert(p)) return true; if (southWest->insert(p)) return true; if (southEast->insert(p)) return true;
// По каким-то причинам вставка может не осуществиться (чего на самом деле не должно происходить) return false;
Вхождение в диапазон Следующий метод находит все точки, входящие в некоторый диапазон.
class QuadTree { ...
// Найти точки, входящие в диапазон function queryRange(AABB range)
// Подготовить массив под результат Array of XY pointsInRange;
// Отмена, если диапазон не совпадает с квадрантом if (!boundary.intersectsAABB(range)) return pointsInRange; // Пустой список
// Проверить объекты текущего уровня for (int p := 0; p < points.size; p++)
if (range.containsPoint(points[p])) pointsInRange.append(points[p]);
// Остановка, если больше нет потомков if (northWest == null) return pointsInRange;
// Добавить все точки потомков pointsInRange.appendArray(northWest->queryRange(range)); pointsInRange.appendArray(northEast->queryRange(range)); pointsInRange.appendArray(southWest->queryRange(range)); pointsInRange.appendArray(southEast->queryRange(range));
return pointsInRange;
См. также Двоичное разбиение пространства K-мерное дерево Октодерево R-дерево UB-дерево () Пространственная база данных
Ссылки
Примечания
Источники
Chapter 14: Quadtrees: pp. 291–306.
Внешние ссылки Java quad tree example and explanation A discussion of the Quadtree and an application Considerable discussion and demonstrations of Spatial Indexing Example C# code for a quad tree Javascript Implementation of the QuadTree used for collision detection C++ Implementation of a QuadTree used for spatial indexing of triangles Quadtree Search JavaScript implementation
Категория:Деревья (структуры данных) Категория:Геометрические структуры данных