Дерево квадрантів
Дерево квадрантів (також квадродерево, 4-дерево, англ. quadtree) — дерево, в якому у кожного внутрішнього вузла рівно чотири нащадки. Дерева квадрантів можуть використовуватися для рекурсивного розбиття двовимірного простору по 4 квадранти (області). Області представляють собою квадрати, прямокутники або мають довільну форму. Англомовний термін quadtree був придуманий Рафаелем Финкелем[en] і Джоном Бентлі[en] в 1974 році. Аналогічне розділення простору відомо як Q-дерево. Загальні риси різних видів дерев квадрантів:
- розбиття простору на адаптивні секції (англ. adaptable cells)
- максимальний розмір кожної секції
- відповідність напряму дерева просторому розподіленню.
Дерево-піраміда (англ. tree-pyramid, T-pyramid) це "повне" дерево; кожна вершина Д-піраміди має чотири дитини, окрім вершин-листів; усі листи знаходяться на одному рівні, де рівень відповідає за характерний піксель на зображенні. Дані в дереві-піраміді можна компактно зберігати в масиві як неявну структуру даних подібно до того, як повне двійкове дерево може бути компактно збережене в масиві.
Класифікація[ред. | ред. код]
Дерева квадрантів можуть бути класифіковані відповідно до типу даних та факту залежності від порядку їх обробки.
Region quadtree[ред. | ред. код]
Дерево квадрантів області виконує розділ двовимірного простору, рекурсивно розкладаючи його на чотири рівних квадрати, де кожен термінальний (листовий) вузол містить дані, що відповідають конкретному субрегіону. Такі структури відносяться до типу префіксних дерев.
Point quadtree[ред. | ред. код]
Дерева квадрантів точок (англ. point quadtree), — різновид бінарних дерев, що використовуються для зберігання інформації про точки на площині. Форма дерева залежить від порядку даних. Використання таких дерев є ефективним для задач порівняння впорядкованих двовимірних точок площини, маючи складність O(log n). Структура вузла дерева квадрантів, що зберігає інформацію про точки площини, є аналогічною структурі вузла бінарного дерева. Відмінність полягає лише в наявності у першого чотирьох нащадків (по одному на кожен квадрант) замість двох («правого» і «лівого») у другого. Ключ вузла складається з двох компонент (координат x і y).
Edge quadtree[ред. | ред. код]
Дерева квадрантів ліній (англ. edge quadtree), використовуються для представлення прямих і кривих. Шляхом апроксимації криві розбиваються на дрібні відрізки, кожен з яких належить до окремого листового вузла. Такий спосіб може призвести до розбалансування дерева, що буде означати проблеми з індексацією.
Polygonal map quadtree[ред. | ред. код]
Дерева квадрантів, що зберігають інформацію про многокутники (англ. polygonal map quadtree/PMQuadtree), можуть містити інформацію про полігони, у тому числі ті, які мають ізольовані вершини або межі[1].
Способи використання[ред. | ред. код]
- Представлення зображень.
- Просторові бази даних.
- Ефективне виявлення зіткнень у двовимірному просторі.
- Відсікання невидимих частин ландшафту (англ. view frustum culling[en]).
- Зберігання даних табличних або матричних обчислень.
- Обчислення, пов'язані з багатовимірними полями (обчислювальна гідродинаміка, електромагнетизм).
- Симуляція гри Життя[2].
- Обчислення станів динамічної системи, за якою ведеться спостереження.[3].
- Аналіз частин фрактальних зображень.
Дерева квадрантів є двомірним аналогом дерев октантів (англ. octree).
Псевдокод[ред. | ред. код]
Приведений псевдокод демонструє використання дерев квадрантів для зберігання інформації про об'єкти. Можливі й інші підходи до побудови такої структури даних.
Структури даних[ред. | ред. код]
Передбачається використання наступних структур даних.
// Проста структура для представлення точки або вектора
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;
}
}
Примітки[ред. | ред. код]
- ↑ 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
- ↑ Tomas G. Rokicki (1 квітня 2006). An Algorithm for Compressing Space and Time. Архів оригіналу за 2 жовтня 2012. Процитовано 20 травня 2009.
- ↑ 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.
Джерела[ред. | ред. код]
- Raphael Finkel and J.L. Bentley (1974). Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Informatica. 4 (1): 1—9. doi:10.1007/BF00288933.
- Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000). Computational Geometry (вид. 2nd revised). Springer-Verlag. ISBN 3-540-65620-0. Chapter 14: Quadtrees: pp. 291–306.
- Storing a Collection of Polygons Using Quadtrees (PDF). July 1985. Архів оригіналу (PDF) за 2 жовтня 2012. Процитовано 23 березня 2012.
| |||||||||||||||||