Los quadtrees son árboles que se utilizan para almacenar de manera eficiente datos de puntos en un espacio bidimensional. En este árbol, cada Node tiene como máximo cuatro hijos. Podemos construir un quadtree a partir de un área bidimensional siguiendo los siguientes pasos:
- Divide el espacio bidimensional actual en cuatro cajas.
- Si una caja contiene uno o más puntos, cree un objeto secundario, almacenando en él el espacio bidimensional de la caja.
- Si un cuadro no contiene ningún punto, no cree un hijo para él
- Recurso para cada uno de los hijos.
Quadtrees se utilizan en la compresión de imágenes, donde cada Node contiene el color promedio de cada uno de sus hijos. Cuanto más profundo atraviese el árbol, mayor será el detalle de la imagen. Los quadtrees también se utilizan para buscar Nodes en un área bidimensional. Por ejemplo, si quisiera encontrar el punto más cercano a las coordenadas dadas, puede hacerlo usando quadtrees.
Función de inserción:
Las funciones de inserción se utilizan para insertar un Node en un Quad Tree existente. Esta función primero verifica si el Node dado está dentro de los límites del quad actual. Si no es así, detenemos inmediatamente la inserción. Si está dentro de los límites, seleccionamos el elemento secundario apropiado para contener este Node en función de su ubicación. Esta función es O(Log N) donde N es el tamaño de la distancia.
Buscando función:
La función de búsqueda se utiliza para localizar un Node en el cuadrante dado. También se puede modificar para devolver el Node más cercano al punto dado. Esta función se implementa tomando el punto dado, comparándolo con los límites de los quads secundarios y recursivamente. Esta función es O(Log N) donde N es el tamaño de la distancia.
El programa que se muestra a continuación demuestra el almacenamiento de Nodes en un quadtree.
CPP
// C++ Implementation of Quad Tree
#include <cmath>
#include <iostream>
using namespace std;
// Used to hold details of a point
struct Point {
int x;
int y;
Point(int _x, int _y)
{
x = _x;
y = _y;
}
Point()
{
x = 0;
y = 0;
}
};
// The objects that we want stored in the quadtree
struct Node {
Point pos;
int data;
Node(Point _pos, int _data)
{
pos = _pos;
data = _data;
}
Node() { data = 0; }
};
// The main quadtree class
class Quad {
// Hold details of the boundary of this node
Point topLeft;
Point botRight;
// Contains details of node
Node* n;
// Children of this tree
Quad* topLeftTree;
Quad* topRightTree;
Quad* botLeftTree;
Quad* botRightTree;
public:
Quad()
{
topLeft = Point(0, 0);
botRight = Point(0, 0);
n = NULL;
topLeftTree = NULL;
topRightTree = NULL;
botLeftTree = NULL;
botRightTree = NULL;
}
Quad(Point topL, Point botR)
{
n = NULL;
topLeftTree = NULL;
topRightTree = NULL;
botLeftTree = NULL;
botRightTree = NULL;
topLeft = topL;
botRight = botR;
}
void insert(Node*);
Node* search(Point);
bool inBoundary(Point);
};
// Insert a node into the quadtree
void Quad::insert(Node* node)
{
if (node == NULL)
return;
// Current quad cannot contain it
if (!inBoundary(node->pos))
return;
// We are at a quad of unit area
// We cannot subdivide this quad further
if (abs(topLeft.x - botRight.x) <= 1
&& abs(topLeft.y - botRight.y) <= 1) {
if (n == NULL)
n = node;
return;
}
if ((topLeft.x + botRight.x) / 2 >= node->pos.x) {
// Indicates topLeftTree
if ((topLeft.y + botRight.y) / 2 >= node->pos.y) {
if (topLeftTree == NULL)
topLeftTree = new Quad(
Point(topLeft.x, topLeft.y),
Point((topLeft.x + botRight.x) / 2,
(topLeft.y + botRight.y) / 2));
topLeftTree->insert(node);
}
// Indicates botLeftTree
else {
if (botLeftTree == NULL)
botLeftTree = new Quad(
Point(topLeft.x,
(topLeft.y + botRight.y) / 2),
Point((topLeft.x + botRight.x) / 2,
botRight.y));
botLeftTree->insert(node);
}
}
else {
// Indicates topRightTree
if ((topLeft.y + botRight.y) / 2 >= node->pos.y) {
if (topRightTree == NULL)
topRightTree = new Quad(
Point((topLeft.x + botRight.x) / 2,
topLeft.y),
Point(botRight.x,
(topLeft.y + botRight.y) / 2));
topRightTree->insert(node);
}
// Indicates botRightTree
else {
if (botRightTree == NULL)
botRightTree = new Quad(
Point((topLeft.x + botRight.x) / 2,
(topLeft.y + botRight.y) / 2),
Point(botRight.x, botRight.y));
botRightTree->insert(node);
}
}
}
// Find a node in a quadtree
Node* Quad::search(Point p)
{
// Current quad cannot contain it
if (!inBoundary(p))
return NULL;
// We are at a quad of unit length
// We cannot subdivide this quad further
if (n != NULL)
return n;
if ((topLeft.x + botRight.x) / 2 >= p.x) {
// Indicates topLeftTree
if ((topLeft.y + botRight.y) / 2 >= p.y) {
if (topLeftTree == NULL)
return NULL;
return topLeftTree->search(p);
}
// Indicates botLeftTree
else {
if (botLeftTree == NULL)
return NULL;
return botLeftTree->search(p);
}
}
else {
// Indicates topRightTree
if ((topLeft.y + botRight.y) / 2 >= p.y) {
if (topRightTree == NULL)
return NULL;
return topRightTree->search(p);
}
// Indicates botRightTree
else {
if (botRightTree == NULL)
return NULL;
return botRightTree->search(p);
}
}
};
// Check if current quadtree contains the point
bool Quad::inBoundary(Point p)
{
return (p.x >= topLeft.x && p.x <= botRight.x
&& p.y >= topLeft.y && p.y <= botRight.y);
}
// Driver program
int main()
{
Quad center(Point(0, 0), Point(8, 8));
Node a(Point(1, 1), 1);
Node b(Point(2, 5), 2);
Node c(Point(7, 6), 3);
center.insert(&a);
center.insert(&b);
center.insert(&c);
cout << "Node a: " << center.search(Point(1, 1))->data
<< "\n";
cout << "Node b: " << center.search(Point(2, 5))->data
<< "\n";
cout << "Node c: " << center.search(Point(7, 6))->data
<< "\n";
cout << "Non-existing node: "
<< center.search(Point(5, 5));
return 0;
}
Node a: 1 Node b: 2 Node c: 3 Non-existing node: 0
Ejercicio: Implemente un Quad Tree que devuelva los 4 Nodes más cercanos a un punto dado.
Este artículo es una contribución de Aditya Kamath . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA