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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Разбитая с помощью дерева квадрантов плоскость

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

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

Классификация[править | править исходный текст]

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

Region quadtree[править | править исходный текст]

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

Дерево высоты n может быть использовано для представления изображения, состоящего из 2n × 2n пикселей, где каждый пиксель имеет значение 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].

Варианты использования[править | править исходный текст]

Деревья квадрантов являются двухмерным аналогом деревьев октантов (англ. 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;
  }
}

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]

Примечния[править | править исходный текст]

  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). Проверено 20 мая 2009. Архивировано из первоисточника 3 октября 2012.
  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). Проверено 23 марта 2012. Архивировано из первоисточника 3 октября 2012.

Внешние ссылки[править | править исходный текст]