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

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

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

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




Wikimedia Foundation. 2010.

Поможем с написанием учебной работы

Полезное


Смотреть что такое "Дерево квадрантов" в других словарях:

  • дерево квадрантов — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN quadtree …   Справочник технического переводчика

  • Дерево отрезков — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Содержание 1 Дерево отрезков в памяти …   Википедия

  • Дерево Фенвика — (двоичное индексированное дерево, англ. Fenwick tree, binary indexed tree, BIT) структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Впервые описано Питером Фенвиком в 1994 году …   Википедия

  • Дерево Фибоначчи — АВЛ дерево с наименьшим числом вершин при заданной высоте (глубине). Если для какой либо из вершин высота поддерева, для которого эта вершина является корнем, равна , то правое и левое поддерево этой вершины имеют высоты равные соответственно и …   Википедия

  • Дерево (теория графов) — У этого термина существуют и другие значения, см. Дерево (значения). Дерево  это связный ациклический граф.[1] Связность означает наличие путей между любой парой вершин, ацикличность  отсутствие циклов и то, что между парами вершин… …   Википедия

  • Дерево (структура данных) — У этого термина существуют и другие значения, см. Дерево (значения). Простой пример неупорядоченного дерева Дерево  одна из наиболее широко распространённых структу …   Википедия

  • Суффиксное дерево — Суффиксное дерево  бор, содержащий все суффиксы некоторой строки (и только их). Позволяет выяснять, входит ли строка w в исходную строку t, за время O(|w|), где |w|  длина строки w. Содержание 1 Основные определения и описание структуры …   Википедия

  • Двоичное дерево поиска — Тип Дерево Временная сложность в О символике В среднем В худшем случае Расход памяти O(n) O(n) Поиск O(h) O(n) Вставка O(h) O(n) Удаление O(h) O(n) где h высота дерева …   Википедия

  • Красно-чёрное дерево — Тип дерево поиска Изобретено в 1972 году Изобретено Рудольф Байер Временная сложность в О символике В среднем В худшем случае Расход памяти O(n) O(n) Поиск O(log n) O(log n) Вставка O(log n) O(log n) Удаление O(log n) O(log n) Красно чёрное… …   Википедия

  • Двоичное дерево — древовидная структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. Для практических целей обычно используют два подвида… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»