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

Дерево квадрантів області виконує розділ двовимірного простору, рекурсивно розкладаючи його на чотири рівних квадрати, де кожен термінальний (листовий) вузол містить дані, що відповідають конкретному субрегіону. Такі структури відносяться до типу префіксних дерев.

Дерева квадрантів точок (англ. point quadtree), — різновид бінарних дерев, що використовуються для зберігання інформації про точки на площині. Форма дерева залежить від порядку даних. Використання таких дерев є ефективним для задач порівняння впорядкованих двовимірних точок площини, маючи складність O(log n). Структура вузла дерева квадрантів, що зберігає інформацію про точки площини, є аналогічною структурі вузла бінарного дерева. Відмінність полягає лише в наявності у першого чотирьох нащадків (по одному на кожен квадрант) замість двох («правого» і «лівого») у другого. Ключ вузла складається з двох компонент (координат x і y).

Дерева квадрантів ліній (англ. edge quadtree), використовуються для представлення прямих і кривих. Шляхом апроксимації криві розбиваються на дрібні відрізки, кожен з яких належить до окремого листового вузла. Такий спосіб може призвести до розбалансування дерева, що буде означати проблеми з індексацією.

Дерева квадрантів, що зберігають інформацію про многокутники (англ. polygonal map quadtree/PMQuadtree), можуть містити інформацію про полігони, у тому числі ті, які мають ізольовані вершини або межі[1].

Передбачається використання наступних структур даних.

// Проста структура для представлення точки або вектора

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) {...}
}

Клас одночасно виконує роль вузла дерева квадрантів та надає інтерфейс структури даних.

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;
 }
}