Octtree es una estructura de datos de árbol en la que cada Node interno puede tener como máximo 8 hijos. Al igual que el árbol binario que divide el espacio en dos segmentos, Octtree divide el espacio en ocho partes como máximo, lo que se denomina octanos. Se utiliza para almacenar el punto 3-D que ocupa una gran cantidad de espacio. Si todo el Node interno del Octárbol contiene exactamente 8 hijos, entonces se llama Octárbol completo. También es útil para gráficos de alta resolución como gráficos 3D por computadora.
El Octtree se puede formar a partir de un volumen 3D siguiendo los siguientes pasos:
- Divide el volumen 3D actual en ocho cajas
- Si algún cuadro tiene más de un punto, divídalo más en cuadros
- No divida la caja que tiene uno o cero puntos
- Realice este proceso repetidamente hasta que todo el cuadro contenga uno o cero puntos.
Los pasos anteriores se muestran en la figura.
Si S es el número de puntos en cada dimensión, entonces el número de Nodes que se forman en Octtree viene dado por esta fórmula 
.
Inserción en Octtree:
- Para insertar un Node en Octtree, en primer lugar, verificamos si existe un Node o no, si existe un Node, luego regresamos, de lo contrario, vamos recursivamente.
- Primero, comenzamos con el Node raíz y lo marcamos como actual
- Luego encontramos el Node secundario en el que podemos almacenar el punto.
- Si el Node está vacío, se reemplaza con el Node que queremos insertar y convertirlo en un Node hoja
- Si el Node es el Node hoja, conviértalo en un Node interno y si es un Node interno, vaya al Node secundario. Este proceso se realiza de forma recursiva hasta que no se encuentra un Node vacío.
- La complejidad temporal de esta función es
donde, N es el número de Nodes
Buscar en Octtree:
- Esta función se utiliza para buscar el punto existe es el árbol o no
- Comience con el Node raíz y busque recursivamente si se encuentra el Node con el punto dado y luego devuelva verdadero, si se encuentra un Node vacío o un punto límite o un punto vacío, devuelva falso
- Si se encuentra un Node interno, vaya a ese Node. La complejidad temporal de esta función también es O(Log N) donde N es el número de Nodes
A continuación se muestra la implementación del enfoque anterior.
CPP14
// Implementation of Octree in c++
#include <iostream>
#include <vector>
using namespace std;
#define TopLeftFront 0
#define TopRightFront 1
#define BottomRightFront 2
#define BottomLeftFront 3
#define TopLeftBottom 4
#define TopRightBottom 5
#define BottomRightBack 6
#define BottomLeftBack 7
// Structure of a point
struct Point {
int x;
int y;
int z;
Point()
: x(-1), y(-1), z(-1)
{
}
Point(int a, int b, int c)
: x(a), y(b), z(c)
{
}
};
// Octree class
class Octree {
// if point == NULL, node is internal node.
// if point == (-1, -1, -1), node is empty.
Point* point;
// Represent the boundary of the cube
Point *topLeftFront, *bottomRightBack;
vector<Octree*> children;
public:
// Constructor
Octree()
{
// To declare empty node
point = new Point();
}
// Constructor with three arguments
Octree(int x, int y, int z)
{
// To declare point node
point = new Point(x, y, z);
}
// Constructor with six arguments
Octree(int x1, int y1, int z1, int x2, int y2, int z2)
{
// This use to construct Octree
// with boundaries defined
if (x2 < x1
|| y2 < y1
|| z2 < z1) {
cout << "boundary points are not valid" << endl;
return;
}
point = nullptr;
topLeftFront
= new Point(x1, y1, z1);
bottomRightBack
= new Point(x2, y2, z2);
// Assigning null to the children
children.assign(8, nullptr);
for (int i = TopLeftFront;
i <= BottomLeftBack;
++i)
children[i] = new Octree();
}
// Function to insert a point in the octree
void insert(int x,
int y,
int z)
{
// If the point already exists in the octree
if (find(x, y, z)) {
cout << "Point already exist in the tree" << endl;
return;
}
// If the point is out of bounds
if (x < topLeftFront->x
|| x > bottomRightBack->x
|| y < topLeftFront->y
|| y > bottomRightBack->y
|| z < topLeftFront->z
|| z > bottomRightBack->z) {
cout << "Point is out of bound" << endl;
return;
}
// Binary search to insert the point
int midx = (topLeftFront->x
+ bottomRightBack->x)
/ 2;
int midy = (topLeftFront->y
+ bottomRightBack->y)
/ 2;
int midz = (topLeftFront->z
+ bottomRightBack->z)
/ 2;
int pos = -1;
// Checking the octant of
// the point
if (x <= midx) {
if (y <= midy) {
if (z <= midz)
pos = TopLeftFront;
else
pos = TopLeftBottom;
}
else {
if (z <= midz)
pos = BottomLeftFront;
else
pos = BottomLeftBack;
}
}
else {
if (y <= midy) {
if (z <= midz)
pos = TopRightFront;
else
pos = TopRightBottom;
}
else {
if (z <= midz)
pos = BottomRightFront;
else
pos = BottomRightBack;
}
}
// If an internal node is encountered
if (children[pos]->point == nullptr) {
children[pos]->insert(x, y, z);
return;
}
// If an empty node is encountered
else if (children[pos]->point->x == -1) {
delete children[pos];
children[pos] = new Octree(x, y, z);
return;
}
else {
int x_ = children[pos]->point->x,
y_ = children[pos]->point->y,
z_ = children[pos]->point->z;
delete children[pos];
children[pos] = nullptr;
if (pos == TopLeftFront) {
children[pos] = new Octree(topLeftFront->x,
topLeftFront->y,
topLeftFront->z,
midx,
midy,
midz);
}
else if (pos == TopRightFront) {
children[pos] = new Octree(midx + 1,
topLeftFront->y,
topLeftFront->z,
bottomRightBack->x,
midy,
midz);
}
else if (pos == BottomRightFront) {
children[pos] = new Octree(midx + 1,
midy + 1,
topLeftFront->z,
bottomRightBack->x,
bottomRightBack->y,
midz);
}
else if (pos == BottomLeftFront) {
children[pos] = new Octree(topLeftFront->x,
midy + 1,
topLeftFront->z,
midx,
bottomRightBack->y,
midz);
}
else if (pos == TopLeftBottom) {
children[pos] = new Octree(topLeftFront->x,
topLeftFront->y,
midz + 1,
midx,
midy,
bottomRightBack->z);
}
else if (pos == TopRightBottom) {
children[pos] = new Octree(midx + 1,
topLeftFront->y,
midz + 1,
bottomRightBack->x,
midy,
bottomRightBack->z);
}
else if (pos == BottomRightBack) {
children[pos] = new Octree(midx + 1,
midy + 1,
midz + 1,
bottomRightBack->x,
bottomRightBack->y,
bottomRightBack->z);
}
else if (pos == BottomLeftBack) {
children[pos] = new Octree(topLeftFront->x,
midy + 1,
midz + 1,
midx,
bottomRightBack->y,
bottomRightBack->z);
}
children[pos]->insert(x_, y_, z_);
children[pos]->insert(x, y, z);
}
}
// Function that returns true if the point
// (x, y, z) exists in the octree
bool find(int x, int y, int z)
{
// If point is out of bound
if (x < topLeftFront->x
|| x > bottomRightBack->x
|| y < topLeftFront->y
|| y > bottomRightBack->y
|| z < topLeftFront->z
|| z > bottomRightBack->z)
return 0;
// Otherwise perform binary search
// for each ordinate
int midx = (topLeftFront->x
+ bottomRightBack->x)
/ 2;
int midy = (topLeftFront->y
+ bottomRightBack->y)
/ 2;
int midz = (topLeftFront->z
+ bottomRightBack->z)
/ 2;
int pos = -1;
// Deciding the position
// where to move
if (x <= midx) {
if (y <= midy) {
if (z <= midz)
pos = TopLeftFront;
else
pos = TopLeftBottom;
}
else {
if (z <= midz)
pos = BottomLeftFront;
else
pos = BottomLeftBack;
}
}
else {
if (y <= midy) {
if (z <= midz)
pos = TopRightFront;
else
pos = TopRightBottom;
}
else {
if (z <= midz)
pos = BottomRightFront;
else
pos = BottomRightBack;
}
}
// If an internal node is encountered
if (children[pos]->point == nullptr) {
return children[pos]->find(x, y, z);
}
// If an empty node is encountered
else if (children[pos]->point->x == -1) {
return 0;
}
else {
// If node is found with
// the given value
if (x == children[pos]->point->x
&& y == children[pos]->point->y
&& z == children[pos]->point->z)
return 1;
}
return 0;
}
};
// Driver code
int main()
{
Octree tree(1, 1, 1, 5, 5, 5);
tree.insert(1, 2, 3);
tree.insert(1, 2, 3);
tree.insert(6, 5, 5);
cout << (tree.find(1, 2, 3)
? "Found\n"
: "Not Found\n");
cout << (tree.find(3, 4, 4)
? "Found\n"
: "Not Found\n");
tree.insert(3, 4, 4);
cout << (tree.find(3, 4, 4)
? "Found\n"
: "Not Found\n");
return 0;
}
Producción:
Point already exist in the tree Point is out of bound found not found found
Aplicaciones:
- Se utiliza en juegos de gráficos de computadora en 3D.
- También se utiliza para encontrar objetos vecinos más cercanos en el espacio 3D.
- También se utiliza para la cuantificación del color.
Publicación traducida automáticamente
Artículo escrito por ParthManiyar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA