Interested Article - Дерево квадрантов

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

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

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

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

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

Region quadtree

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

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

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

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

Point quadtree

Деревья квадрантов, хранящие информацию о точках ( англ. point quadtree ), — разновидность бинарных деревьев , используемых для хранения информации о точках на плоскости. Форма дерева зависит от порядка задания данных. Использование таких деревьев очень эффективно в сравнении упорядоченных точек плоскости, причём время обработки равно O(n 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 ), могут содержать информацию о полигонах, в том числе и о вырожденных (имеющих изолированные вершины или грани) .

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

Представление изображений.
Пространственные базы данных .
Эффективное обнаружение столкновений в двух измерениях.
Отсечение невидимых частей ландшафта ( англ. ).
Хранение данных для табличных или матричных вычислений.
Вычисления, связанные с многомерными полями (в вычислительной гидродинамике , электромагнетизме ).
Симуляция игры Жизнь .
Вычисление состояний наблюдаемой динамической системы .
Анализ частей фрактальных изображений.

Деревья квадрантов являются двухмерным аналогом деревьев октантов ( англ. 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. (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 (англ.) // (англ.) ( : journal. — 1974. — Vol. 4 , no. 1 . — P. 1—9 . — doi : .
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 [ 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. (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.

Дерево (структура данных)
Двоичное дерево поиска Дерево (теория графов) Древовидная структура
Двоичные деревья	Двоичное дерево T-дерево
	АВЛ-дерево Красно-чёрное дерево Splay-дерево Декартово дерево Дерево Фибоначчи B-дерево T-дерево
B-деревья	2-3-дерево B⁺-дерево B*-дерево B ^x -дерево UB-дерево Танцующее дерево
Префиксные деревья	Суффиксное дерево Сжатое префиксное дерево
Двоичное разбиение пространства	k-мерное дерево VP-дерево
Недвоичные деревья	Октодерево Sparse Voxel Octree PQ-дерево
Разбиение пространства	R-дерево R-дерево Гильберта R*-дерево Дерево Фенвика Дерево отрезков
Другие деревья	Куча Дерево хешей Дерево покрытий LSM-дерево
Алгоритмы	Поиск в ширину Поиск в глубину Протокол остовного дерева