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

Разбитая с помощью дерева квадрантов плоскость

Дерево квадрантов (также квадродерево, 4-дерево, англ. quadtree) — дерево, в котором у каждого внутреннего узла ровно 4 потомка. Деревья квадрантов часто используются для рекурсивного разбиения двухмерного пространства по 4 квадранта (области). Области представляют собой квадраты, прямоугольники или имеют произвольную форму. Англоязычный термин quadtree был придуман Рафаэлем Финкелем (англ. Raphael Finkel) и Джоном Бентли (англ. Jon Bentley) в 1974. Аналогичное разбиение пространства известно как Q-дерево. Общие черты разных видов деревьев квадрантов:

• разбиение пространства на адаптирующиеся ячейки (англ. adaptable cells),
• максимально возможный объём каждой ячейки,
• соответствие направления дерева пространственному разбиению.

Классификация

Деревья квадрантов могут быть классифицированы в соответствии с типом данных, который они представляют — пространством, точками, прямыми, кривыми. Также их можно разделить по тому, зависит ли форма дерева от порядка обработки данных. Некоторые виды деревьев квадрантов:

Region quadtree

Деревья квадрантов, разбивающие пространство (англ. region quadtree), представляют какую-либо часть двумерного пространства разбивая его на 4 квадранта, субквадранты и так далее, причём каждый лист дерева соответствует определённой области. У каждого узла дерева либо 4 потомка, либо их нет вовсе (у листьев). Деревья квадрантов, разбивающие пространство, не являются деревьями в полной мере, поскольку положение субквадрантов не зависит от данных. Более правильное название — префиксные деревья (англ. trie).

Дерево высоты n может быть использовано для представления изображения, состоящего из 2ⁿ × 2ⁿ пикселей, где каждый пиксель имеет значение 0 или 1. Корень дерева представляет всю область изображения. Если не все пиксели только нули или только единицы, она разбивается. В этом случае каждый лист соответствует множеству пикселей — либо только из нулей, либо только из единиц.

Деревья квадрантов, разбивающие пространство, также могут быть использованы для представления переменного разрешения какого-либо набора данных. Например, информация о температуре может храниться в виде дерева квадрантов, каждый узел которого хранит среднюю температуру дочерних узлов.

Если дерево используется для представления множества точек (например, ширины и долготы положений каких-либо городов), области разбиваются до тех пор, пока листья будут содержать не более одной точки.

Point quadtree

Деревья квадрантов, хранящие информацию о точках (англ. point quadtree), — разновидность бинарных деревьев, используемых для хранения информации о точках на плоскости. Форма дерева зависит от порядка задания данных. Использование таких деревьев очень эффективно в сравнении упорядоченных точек плоскости, причём время обработки равно O(log n).

Структура узла

Узел дерева квадрантов, хранящего информацию о точках плоскости, аналогичен узлу бинарного дерева лишь с той оговоркой, что узел первого имеет четыре потомка (по одному на каждый квадрант) вместо двух («правого» и «левого»). Ключ узла состоит из двух компонент (для координат x и y). Таким образом, узел дерева содержит следующую информацию:

• 4 указателя: quad[‘NW’], quad[‘NE’], quad[‘SW’], and quad[‘SE’],
• точка, описываемая следующим образом:
  • ключ key, обычно выражает координаты x и y,
  • значение value, например, имя.

Edge quadtree

Деревья квадрантов, хранящие информацию о линиях (англ. edge quadtree), используются для описания прямых и кривых. Кривые описываются точными приближениями путём разбиения ячеек на очень мелкие. Это может привести к разбалансировке дерева, что будет означать проблемы с индексацией.

Polygonal map quadtree

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

Варианты использования

• Представление изображений.
  
• Пространственные базы данных.
• Эффективное обнаружение столкновений в двух измерениях.
• Отсечение невидимых частей ландшафта (англ. view frustum culling).
• Хранение данных для табличных или матричных вычислений.
• Вычисления, связанные с многомерными полями (в вычислительной гидродинамике, электромагнетизме).
• Симуляция игры Жизнь^[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

Класс представляет собственно 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.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;
  }
}

См. также

• Двоичное разбиение пространства
• K-мерное дерево
• Октодерево
• R-дерево
• UB-дерево (англ. UB-tree)
• Пространственная база данных

Ссылки

Примечния

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 An Algorithm for Compressing Space and Time (1 апреля 2006). Архивировано из первоисточника 3 октября 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 Computational Geometry. — 2nd revised. — Springer-Verlag, 2000. — ISBN 3-540-65620-0 Chapter 14: Quadtrees: pp. 291–306.
3. [http://infolab.usc.edu/csci585/Spring2008/den_ar/p182-samet.pdf Storing a Collection of Polygons Using

Quadtrees] (July 1985). Архивировано из первоисточника 3 октября 2012. Проверено 23 марта 2012.

Внешние ссылки

• 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