Дерево квадрантів (також квадродерево, 4-дерево, ) — дерево, в якому у кожного внутрішнього вузла рівно чотири нащадки. Дерева квадрантів можуть використовуватися для рекурсивного розбиття двовимірного простору по 4 квадранти (області). Області представляють собою квадрати, прямокутники або мають довільну форму. Англомовний термін quadtree був придуманий і в 1974 році. Аналогічне розділення простору відомо як Q-дерево. Загальні риси різних видів дерев квадрантів: розбиття простору на адаптивні секції () максимальний розмір кожної секції відповідність напряму дерева просторому розподіленню.
Дерево-піраміда (англ. tree-pyramid, T-pyramid) це "повне" дерево; кожна вершина Д-піраміди має чотири дитини, окрім вершин-листів; усі листи знаходяться на одному рівні, де рівень відповідає за характерний піксель на зображенні. Дані в дереві-піраміді можна компактно зберігати в масиві як неявну структуру даних подібно до того, як повне двійкове дерево може бути компактно збережене в масиві.
Класифікація Дерева квадрантів можуть бути класифіковані відповідно до типу даних та факту залежності від порядку їх обробки.
Region quadtree Дерево квадрантів області виконує розділ двовимірного простору, рекурсивно розкладаючи його на чотири рівних квадрати, де кожен термінальний (листовий) вузол містить дані, що відповідають конкретному субрегіону. Такі структури відносяться до типу префіксних дерев.
Point quadtree Дерева квадрантів точок (), — різновид бінарних дерев, що використовуються для зберігання інформації про точки на площині. Форма дерева залежить від порядку даних. Використання таких дерев є ефективним для задач порівняння впорядкованих двовимірних точок площини, маючи складність O(log n). Структура вузла дерева квадрантів, що зберігає інформацію про точки площини, є аналогічною структурі вузла бінарного дерева. Відмінність полягає лише в наявності у першого чотирьох нащадків (по одному на кожен квадрант) замість двох («правого» і «лівого») у другого. Ключ вузла складається з двох компонент (координат x і y).
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 Клас одночасно виконує роль вузла дерева квадрантів та надає інтерфейс структури даних.
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(XYp) { // Ігнорувати об'єкти, що не належать дереву 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(AABBrange) { // Підготувати масив під результат Array of XYpointsInRange;
// Скасування, якщо діапазон не збігається з квадрантом if(!boundary.insersectsAABB(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;
Примітки
Джерела
Chapter 14: Quadtrees: pp. 291–306.