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

Дерево квадрантов (также квадродерево, 4-дерево, англ. quadtree) — дерево, в котором у каждого внутреннего узла ровно 4 потомка. Деревья квадрантов часто используются для рекурсивного разбиения двухмерного пространства по 4 квадранта (области). Области представляют собой квадраты, прямоугольники или имеют произвольную форму. Англоязычный термин quadtree был придуман Рафаэлем Финкелем и Jon Bentley (computer scientist) — версия статьи «Бентли, Джон Луис» на английском языке Джоном Бентли (англ.) (рус. в 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’], и 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;
  }
}

См. такжеПравить

СсылкиПравить

ПримечанияПравить

↑ 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. An Algorithm for Compressing Space and Time (неопр.) (1 апреля 2006). Дата обращения: 20 мая 2009. Архивировано 2 октября 2012 года.
↑ 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. Quad Trees: A Data Structure for Retrieval on Composite Keys (англ.) // Acta Informatica (англ.) (рус. : journal. — 1974. — Vol. 4, no. 1. — P. 1—9. — doi:10.1007/BF00288933.
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.
Samet, Hanan; Webber, Robert [http://infolab.usc.edu/csci585/Spring2008/den_ar/p182-samet.pdf Storing a Collection of Polygons Using

Quadtrees] (неопр.) (июль 1985). Дата обращения: 23 марта 2012. Архивировано 2 октября 2012 года.

Внешние ссылкиПравить

[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. Архивировано 2 октября 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]

[2]

[3]