Loading AI tools
дерево, в котором у каждого внутреннего узла ровно 4 потомка Из Википедии, свободной энциклопедии
Дерево квадрантов (также квадродерево, 4-дерево, англ. quadtree) — дерево, в котором у каждого внутреннего узла ровно 4 потомка. Деревья квадрантов часто используются для рекурсивного разбиения двухмерного пространства по 4 квадранта (области). Области представляют собой квадраты, прямоугольники или имеют произвольную форму. Англоязычный термин quadtree был придуман Рафаэлем Финкелем и Джоном Бентли[англ.] в 1974 году. Аналогичное разбиение пространства известно как Q-дерево. Общие черты разных видов деревьев квадрантов:
Деревья квадрантов могут быть классифицированы в соответствии с типом данных, который они представляют — пространством, точками, прямыми, кривыми. Также их можно разделить по тому, зависит ли форма дерева от порядка обработки данных. Некоторые виды деревьев квадрантов:
Деревья квадрантов, разбивающие пространство (англ. region quadtree), представляют какую-либо часть двумерного пространства разбивая его на 4 квадранта, субквадранты и так далее, причём каждый лист дерева соответствует определённой области. У каждого узла дерева либо 4 потомка, либо их нет вовсе (у листьев). Деревья квадрантов, разбивающие пространство, не являются деревьями в полной мере, поскольку положение субквадрантов не зависит от данных. Более правильное название — префиксные деревья (англ. trie).
Дерево высоты n может быть использовано для представления изображения, состоящего из 2n × 2n пикселей, где каждый пиксель имеет значение 0 или 1. Корень дерева представляет всю область изображения. Если не все пиксели только нули или только единицы, она разбивается. В этом случае каждый лист соответствует множеству пикселей — либо только из нулей, либо только из единиц.
Деревья квадрантов, разбивающие пространство, также могут быть использованы для представления переменного разрешения какого-либо набора данных. Например, информация о температуре может храниться в виде дерева квадрантов, каждый узел которого хранит среднюю температуру дочерних узлов.
Если дерево используется для представления множества точек (например, широты и долготы положений каких-либо городов), области разбиваются до тех пор, пока листья будут содержать не более одной точки.
Деревья квадрантов, хранящие информацию о точках (англ. point quadtree), — разновидность бинарных деревьев, используемых для хранения информации о точках на плоскости. Форма дерева зависит от порядка задания данных. Использование таких деревьев очень эффективно в сравнении упорядоченных точек плоскости, причём время обработки равно O(n log n).
Узел дерева квадрантов, хранящего информацию о точках плоскости, аналогичен узлу бинарного дерева лишь с той оговоркой, что узел первого имеет четыре потомка (по одному на каждый квадрант) вместо двух («правого» и «левого»). Ключ узла состоит из двух компонент (для координат x и y). Таким образом, узел дерева содержит следующую информацию:
Деревья квадрантов, хранящие информацию о линиях (англ. edge 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) {...}
}
Класс представляет собственно 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;
}
}
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
