Share to: share facebook share twitter share wa share telegram print page

Дерево квадрантів

Площина, розбита за допомогою дерева квадрантів

Дерево квадрантів (також квадродерево, 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].

Способи використання

Дерева квадрантів є двомірним аналогом дерев октантів (англ. 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;
 }
}

Примітки

  1. ↑ 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
  2. ↑ Tomas G. Rokicki (1 квітня 2006). An Algorithm for Compressing Space and Time. Архів оригіналу за 2 жовтня 2012. Процитовано 20 травня 2009.
  3. ↑ 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.

Джерела

  1. 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.
  2. 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.
  3. Storing a Collection of Polygons Using Quadtrees (PDF). July 1985. Архів оригіналу (PDF) за 2 жовтня 2012. Процитовано 23 березня 2012.
Kembali kehalaman sebelumnya