Дерево квадрантов
Познакомимся со структурой данных, индексирующую данные на плоскости.
Деревья квадрантов используются в самых различных сферах цифровой жизни: в компьютерных играх, в графике, при работе с картами местности, другими словами - везде, где информация связанна с расположением на плоскости. Поиск кафе поблизости с помощью карт или вызов ближайшего такси, всё это примеры квадратичных деревьев в действии. В зависимости от типа используемых деревьев, они также широко применяются в обработке графических данных, моделировании процессов, обнаружения столкновений и многом другом.
Далее мы ознакомимся поближе с деревом квадрантов на примере дерева с квадратными по форме ячейками, хранящими данные в виде точек плоскости, ознакомимся с применимостью, реализацией и попробуем написать свою.
Определение#
Дерево квадрантов — древовидная структура данных, имеющая по 4 потомка на каждый внутренний узел. Дерево квадрантов часто используется для рекурсивной разбивки плоскости на квадранты или области. Форма данных, хранящихся в узлах дерева, определяется непосредственно приложением и представляют собой «единицу интересной пространственной информации». Интересной информацию в данном случае нужно понимать как её гарантированное наличие как таковой.
Обычно квадранты представляют такие фигуры как квадраты или прямоугольники, но могут иметь и произвольную форму.
Все разновидности этой структуры данных обладают следующими свойствами:
- Они разбивают пространство на адаптивные «ячейки» - квадранты;
- Каждая «ячейка» имеет предельную вместимость, при превышении которой ячейка делится;
- Форма дерева следует пространственной декомпозиции «ячеек».
Разновидности деревьев могут быть систематизированы в зависимости от представления хранимых данных, например это могут быть области, точки, отрезки или даже кривые. Так же важной характеристикой является зависимость порядка обработки данных от формы самого дерева.
Постановка проблемы#
Рассмотрим применимость дерева квадрантов на практическом примере. Пусть в некоторой ограниченной части плоскости имеются n движущихся объектов. Задача состоит в определении столкновения объектов в некоторый момент времени.
Для решения данной задачи необходимо рассчитать расстояние от каждого объекта до всех остальных. Другими словами, алгоритмическая сложность будет квадратичной: O(n^2), ведь если имеется n объектов, то необходимо проверить расстояние от каждого из объектов до всех остальных. Итого, проводится n * n проверок.
На самом деле, большую часть проверок можно было бы избежать, если бы мы некоторым образом имели возможность разграничить слишком удалённые объекты, пересечение с которыми крайне маловероятно. Другими словами, необходимо иметь возможность иметь доступ к информации об относительной удалённости объектов в некоторой части пространства.
В этом нам и сможет помочь дерево квадрантов. Построив дерево для плоскости и предварительно зарегистрировав положение каждого объекта на плоскости, оно позволит получать информацию об объектах, находящихся в произвольной области; по итогу будет лишь необходимо провести проверку для подмножества объектов. Этот подход позволит снизить алгоритмическую сложность до O(n log n) — логарифмической, в численном сравнении — для тысячи объектов количество необходимых операций снижается примерно до трёх тысяч. Важно подчеркнуть: с миллиона до трёх тысяч. Серьёзное увеличение производительности, даже с учётом затрачиваемых ресурсов на построение самого дерева.
Таким образом, с помощью дерева квадрантов, хранящего координаты объектов, можно решать целый ряд других подобных задач, основанных на пространственном расположении.
Демонстрация работы#
С учётом использования форм таких «ячеек» как прямоугольники или квадраты, дерево разбивает плоскость на квадранты — напоминающиие собой знакомые нам четверти декартовой системы координат. С ростом вложенности дерева, квадранты разбиваются рекурсивным образом и плоскость делится на всё меньшие и меньше области:
Глубина дерева и разбивка плоскости
Пример выше визуально напоминает собой таблицу и даёт мало представления о дереве квадрантов. Рассмотрим более наглядный пример. Коснувшись области, мы можем добавить объект — точку. При последовательном добавлении всё большего количества объектов и превышении предельной вместимости (в примере это 4 объекта на квадрант), квадранты будут разбиваться, формируя дерево. В итоге, ни в одной ячейке гарантированно не будет содержаться большее количество точек, чем квадрант мог бы в себя вместить.
Построение квадратичного дерева
Коснитесь, чтобы добавить точки
Увидев, как формируется дерево и что оно из себя представляет, настало время воспользоваться им по назначению. Дерево квадрантов напоминает «пространственную базу данных». Мы можем сделать запрос, указав область и дерево квадрантов предоставит информацию об объектах, находящиеся в указанной области. Область, конечно же, может иметь произвольную форму и размеры.
На примере ниже, сформировано дерево квадрантов из ста случайно расположенных точек. Помимо точек на плоскости расположена ограниченная область (в форме окружности или прямоугольника). При перемещении данной области лишь точки, находящиеся во внутренней части ограниченной области, будут менять размер и окраску, информация о которых получена запросом из квадратичного дерева.
Запрос данных дерева из области
Таким образом, наглядно демонстрируется результат запроса. Мы получаем доступ к информации в зависимости от местоположения на плоскости, что позволяет более эффективно решать определённый круг задач.
Пример использования#
Дерево квадрантов используется на сайте в разделе визуализаций, а именно в моделировании поведения стаи.
Дерево в данном случае является оптимизацией, включенной по умолчанию. Необходимость в использовании этой структуры данных заключается в формировании различного рода сил, движущих элементом стаи. Силы формируются на основе соседей, в первую очередь, в зависимости от их отдалённости. Более далёкие соседи вкладывают заметно низкое влияние, которым можно пренебречь в целях оптимизации.
Таким образом, каждый элемент стаи обладает таким параметром как «восприятие», представляющим собой расстояние, за пределами которого другие члены стаи перестают оказывать влияние. На основе координат члена стаи и области, формируемой «восприятием», дерево квадрантов позволяет узнать лишь о тех членах стаи, которые должны оказывать существенное влияние.
Благодрая дереву квадрантов производительность анимации заметно возрастает. В этом можно убедиться, отключив оптимизацию и увеличив количество членов стаи.
Имплементация дерева квадрантов#
Псевдокод#
Данный псевдокод демонстрирует один из способов реализовать дерево квадрантов с прямоугольными по форме квадрантами и хранящим данные в виде точек.
Для работы с деревом необходимые следующие вспомогательные структуры данных:
// Представление точки или вектора на плоскости.
struct Point {
float x;
float y;
function construct(float x, float y): Point;
}
// Представление прямоугольника, выровненного по координатным осям.
struct Rect {
Point center;
float width;
float height;
function construct(Point center, float width, float height): Rect;
function contains(Point coordinate): boolean;
function intersects(Rect otherRect): boolean;
}Структура Rect в данном случае описывает прямоугольник, но может быть и видоизмененна для представления других форм. Важно реализовать методы contains и intersects для обнаружения точек внутри фигуры и обнаружения пересечения с другими фигурами.
Непосредственно класс QuadTree представляет собой 4-дерево и корневой узел. Экземпляр класса имеет постоянное значение для предельной вместимости квадрантов, задаваемой изначально.
//
class QuadTree {
// Предельная вместимость квадрантов
constant int CAPACITY = 4;
// Границы дерева
Rect boundary;
// Хранимые точки в данном узле
points: Array of Point [ size = CAPACITY ];
// Потомки
children: Array of QuadTree [ size = 4 ];
// Методы
function construct(Rect boundary): QuadTree;
function insert(Point p): boolean;
function query(Rect range): Array of Point;
private function split(): void;
}Метод insert регистрирует точку в соответствующий квадрант дерева, осуществляя разбиение при необходимости:
class QuadTree {
...
function insert(Point p): boolean {
if (!boundary.contains(p)) {
return false
}
if (points.size < CAPACITY) {
points.append(p);
return true;
}
if (children[0] == null) {
split();
}
each children as child {
if (child.insert(p)) {
return true;
}
}
// По каким-то причинам регистрация точки не осуществлена
// Этого не должно происходить
return false;
}
}Метод query осуществляет запрос в заданной области и возвращает все точки, входящие в этот диапазон:
class QuadTree {
...
query(Rect range): Array of Point {
items: Array of Point;
if (!boundary.intersects(range)) {
return items;
}
each points as point {
if (range.contains(point)) {
items.append(point);
}
}
if (children[0] == null) {
return items;
}
each children as child {
child.query(range);
}
return items;
}
}Приватный метод split осуществляет разбивку дерева. Реализация метода зависит не только от формы квадрантов дерева, но и от представления самой формы. Например, прямоугольник можно задать с помощью координат одной из вершин, принадлежащих одной диагонали, либо координатой центра и половиной величины ширины и высоты. Метод split должен сформировать координаты дочерних квадрантов на основе используемого представления.
Реализация на TypeScript#
Пример данной реализации повторяет собой уже знакомое квадратичное дерево с прямоугольными по форме потомками. Важное замечание касается хранения данных. Данные будут храниться исключительно на крайних узлах.
Как и прежде, для начала реализуем вспомогательные структуры данных. Экземпляр Point, помимо координат, имеет значение data для хранения данных. В таком случае, точка является «обёрткой» над данными для регистрации в дереве квадрантов:
/**
* Представление точки или вектора на плоскости.
*/
class Point<Data = unknown> {
readonly x: number;
readonly y: number;
readonly data?: Data;
constructor(x: number, y: number, data?: Data) {
this.x = x;
this.y = y;
this.data = data;
}
}Границы в нашем примере представляют собой прямоугольник, выровненный вдоль осей координат. В данном случае будет использоваться представление прямоугольника через координату верхней левой вершины и значений длин его сторон, которое часто используется для работы с графическими данными на экране.
Метод contains позволяет проверить, входит ли данная точка в область границы. Для этого нужно убедиться, что координаты точки находятся с внутренней стороны каждой из сторон прямоугольника.
Метод intersects позволяет проверить пересечение границы с другой. Суть проверки сводится к тому, чтобы ни одна из сторон прямоугольника не отдалялась от соответственной стороны другого прямоугольника.
/**
* Представление прямоугольной границы, выровненной вдоль осей координат
* - `x`, `y` - координаты верхней-левой вершины;
* - `w` - значение ширины;
* - `h` - значение высоты.
*/
export class Rectangle {
readonly x: number;
readonly y: number;
readonly w: number;
readonly h: number;
constructor(x: number, y: number, w: number, h: number) {
this.x = x;
this.y = y;
this.w = w;
this.h = h;
}
/**
* Проверка расположения данной координаты во внутренней области границы.
*/
contains(item: Point): boolean {
return (
item.x >= this.x &&
item.x <= this.x + this.w &&
item.y >= this.y &&
item.y <= this.y + this.h
);
}
/**
* Проверка на пересечение данной границы с другой.
*/
intersects(range: Rectangle): boolean {
return !(
this.x >= range.x + range.w ||
this.x + this.w <= range.x ||
this.y >= range.y + range.h ||
this.y + this.h <= range.y
);
}
}Теперь можно приступать к реализации самого дерева. Для практичности добавим некоторые свойства и вспомогательные методы, которых не было в псевдокоде. Например, пользователь может задать ограничение по глубине. Так как будет использоваться рекурсия, то сильная вложенность может ударить по производительности.
Потомки дерева будут храниться в массиве. Так как квадранты прямоугольника напоминают собой четверти декартовой системы координат, то будет удобно обращаться к квадранту по индексу, с единственным отличием, что нумерация будет идти от нуля.
class QuadTree<Item extends Point> {
// область границы данного узла дерева
readonly boundary: Rectangle;
// вместимость ячеек дерева
readonly capacity: number;
// глубина данного узла дерева
readonly depth: number;
// максимальный уровень вложенности дерева
private readonly depthLimit: number;
// массив зарегистрированных координат
items: Item[];
// потомки дерева
quadrants: QuadTree<Item>[];
constructor(capacity: number, boundary: Rectangle, depthLimit = 12, depth = 1) {
this.boundary = boundary;
this.capacity = capacity;
this.depth = depth;
this.depthLimit = depthLimit;
this.items = [];
this.quadrants = [];
}
...
}Далее, добавим вспомогательный метод hasChildren для проверки наличия потомков:
class QuadTree<Item extends Point> {
...
/**
* Проверяет данный узел дерева на наличие потомков.
*/
get hasChildren(): boolean {
return this.quadrants.length > 0;
}
}Следующим шагом реализуем метод split для разбивки дерева. Метод приватный, так как разбивка дерева будет происходить автоматически при определённых обстоятельствах. Метод создаёт четыре новых экземпляра класса QuadTree и добавляет их в массив квадрантов данного узла.
class QuadTree<Item extends Point> {
...
/**
* Разветвляет текущий узел дерева, добавляя 4 потомка.
*/
private split(): void {
const hw = this.boundary.w / 2;
const hh = this.boundary.h / 2;
// смещения координат вершины каждого нового квадранта
const delta = [
[ hw, 0 ],
[ 0, 0 ],
[ 0, hh ],
[ hw, hh ]
];
for (const [ dx, dy ] of delta) {
this.quadrants.push(new QuadTree<Item>(
this.capacity,
new Rectangle(this.boundary.x + dx, this.boundary.y + dy, hw, hh),
this.depthLimit,
this.depth + 1
));
}
}
}Теперь реализуем метод insert для регистрации координат.
Для начала проверяется, действительно ли данная точка лежит в границе узла дерева. В случае, если у узла нет потомков и имеется свободное место, точка регистрируется в данном узле.
В случае, если у узла уже имеются потомки и не достигнуто предельное значение глубины, дерево разветвляется. На этапе разветвления все зарегистрированные точки данного узла перерегистрируются вглубь и массив точек очищается. Этот этап необходим для того, чтобы лишь крайние узлы дерева содержали точки.
В конце концов, точка поочередно пытается зарегистрироваться в одном из квадрантов, пока её не примет один из них.
Метод возвращает булеву величину для отождествления успешности операции.
class QuadTree<Item extends Point> {
...
/**
* Регистрирует координату в экземпляре `QuadTree`.
*/
insert(item: Item): boolean {
if (!this.boundary.contains(item)) {
return false;
}
if (!this.hasChildren && this.items.length < this.capacity) {
this.items.push(item);
return true;
}
if (!this.hasChildren && this.depth < this.depthLimit) {
this.split();
// Перерегистрация прежде зарегистрированных точек вглубь
for (const thisItem of this.items) {
for (const quadrant of this.quadrants) {
if (quadrant.insert(thisItem)) {
break;
}
}
}
this.items = [];
}
for (const quadrant of this.quadrants) {
if (quadrant.insert(item)) {
return true;
}
}
return false;
}
}Напоследок, осталось реализовать метод query для запроса данных дерева. Данные будут отбираться из узлов рекурсивно. На каждой глубине вызова функции вторым параметром передаётся массив с отобранными данными, пока финальным вызовом функция не вернёт сформированный массив:
class QuadTree<Item extends Point> {
...
/**
* Запрашивает данные, хранящиеся в экземпляре дерева в заданной области.
*/
query(range: Rect, items: Item[] = []): Item[] {
// Нет пересечения, соответственно, нет и результатов
if (!range.intersects(this.boundary)) {
return items;
}
for (const item of this.items) {
if (range.contains(item)) {
items.push(item);
}
}
if (this.hasChildren) {
for (const quadrant of this.quadrants) {
quadrant.query(range, items);
}
}
return items;
}
}Собирая всё воедино, получаем следующий код:
Итоговый код
/**
* Представление координаты точки или вектора на плоскости.
*/
export class Point<Data = unknown> {
readonly x: number;
readonly y: number;
readonly data?: Data;
constructor(x: number, y: number, data?: Data) {
this.x = x;
this.y = y;
this.data = data;
}
}
/**
* Представление прямоугольной границы:
* - `x`, `y` - координаты верхнего левого угла;
* - `w` - значение ширины;
* - `h` - значение высоты.
*/
export class Rectangle {
readonly x: number;
readonly y: number;
readonly w: number;
readonly h: number;
constructor(x: number, y: number, w: number, h: number) {
this.x = x;
this.y = y;
this.w = w;
this.h = h;
}
/**
* Проверяет нахождение данной координаты в области границы.
*/
contains(item: Point): boolean {
return (
item.x >= this.x &&
item.x <= this.x + this.w &&
item.y >= this.y &&
item.y <= this.y + this.h
);
}
/**
* Проверяет пересечение данной области с другой областью.
*/
intersects(range: Rectangle): boolean {
return !(
this.x >= range.x + range.w ||
this.x + this.w <= range.x ||
this.y >= range.y + range.h ||
this.y + this.h <= range.y
);
}
}
export class QuadTree<Item extends Point> {
readonly boundary: Rectangle;
readonly capacity: number;
readonly depth: number;
private readonly depthLimit: number;
items: Item[];
quadrants: QuadTree<Item>[];
constructor(capacity: number, boundary: Rectangle, depthLimit = 12, depth = 1) {
this.boundary = boundary;
this.capacity = capacity;
this.depth = depth;
this.depthLimit = depthLimit;
this.items = [];
this.quadrants = [];
}
/**
* Проверяет наличие у данного узла дерева потомков.
*/
get hasChildren(): boolean {
return this.quadrants.length > 0;
}
/**
* Регистрирует координату в экземпляре дерева.
*/
insert(item: Item): boolean {
if (!this.boundary.contains(item)) {
return false;
}
if (!this.hasChildren && this.items.length < this.capacity) {
this.items.push(item);
return true;
}
if (!this.hasChildren && this.depth < this.depthLimit) {
this.split();
for (const thisItem of this.items) {
for (const quadrant of this.quadrants) {
if (quadrant.insert(thisItem)) {
break;
}
}
}
this.items = [];
}
for (const quadrant of this.quadrants) {
if (quadrant.insert(item)) {
return true;
}
}
return false;
}
/**
* Производит разветвление дерева.
*/
private split(): void {
const hw = this.boundary.w / 2;
const hh = this.boundary.h / 2;
const delta = [
[ hw, 0 ],
[ 0, 0 ],
[ 0, hh ],
[ hw, hh ]
];
for (const [ dx, dy ] of delta) {
this.quadrants.push(new QuadTree<Item>(
this.capacity,
new Rectangle(this.boundary.x + dx, this.boundary.y + dy, hw, hh),
this.depthLimit,
this.depth + 1
));
}
}
/**
* Запрашивает данные, хранящиеся в экземпляре дерева в заданной области.
*/
query(range: Rectangle | Circle, items: Item[] = []): Item[] {
// boundary.intersects(range) or vice versa?
if (!range.intersects(this.boundary)) {
return items;
}
for (const item of this.items) {
if (range.contains(item)) {
items.push(item);
}
}
if (this.hasChildren) {
for (const quadrant of this.quadrants) {
quadrant.query(range, items);
}
}
return items;
}
}Итоги#
В этой статье мы познакомились поближе с квадратичными деревьями, узнали о принципах их работы, почему и где они могут применяться, и даже написали свою реализацию. Тем не менее, знакомство с этой замечательной структурой данной лишь только начинается, ведь мы рассматривали лишь квадратичные деревья, обрабатывающие координаты. Следующим этапом знакомства являются деревья, работающие с областями. Ознакомиться с примером их работы можно тут.