#### D.V.D

##### Make a wish

- Reaction score
- 73

The quadtree itself is simple, here is the class and its constructor:

Code:

```
struct Quadtree
{
uint32_t average;
uint16_t length_x;
uint16_t length_y;
uint8_t level;
Quadtree * parent;
Quadtree * children;
Quadtree () {}
Quadtree (Quadtree * children);
~Quadtree ();
};
Quadtree::Quadtree (Quadtree * _children)
{
children = new Quadtree [4];
children = _children;
level = children[0].level--;
length_x = children[0].length_x << 1; // multiply by 2 (2*1)
length_y = children[0].length_y << 1;
if ( children[0].average == children[1].average && // If all children nodes are the same, delete them (sparse quadtree)
children[1].average == children[2].average &&
children[2].average == children[3].average )
{
average = children[0].average;
delete[] children;
}
else
{
average = (children[0].average + children[1].average + children[2].average + children[3].average) >> 2; // divide by 4 (2*2)
}
}
Quadtree::~Quadtree ()
{
delete[] children;
}
```

Since a quadtree grows exponentially, I can always multiply my side lengths by 2 (left shit by 1) to get the next node above its side lengths. The if statement simply checks to see if all children are the same and the else simply gets the average color.

The part Im worried about is the building function. I made it as a normal function outside the class since I don't start from the root of the quadtree so I don't have the master class until the whole building process is done. Here's the code:

Code:

```
Quadtree* build (unsigned int * Image_Pixels)
{
uint8_t level = 15;
uint32_t count = sizeof(*Image_Pixels);
Quadtree * prev_nodes = new Quadtree [count];
for ( uint32_t i = 0; i < count; i++ )
{
prev_nodes->average = Image_Pixels[i];
}
while (level < QT_N_LEVELS)
{
level --;
count >> 1; // Divide by 2
Quadtree * nodes = new Quadtree [count];
count <<= 2;
for ( uint32_t i, j = 0; j < count << 2; i++, j+=4 )
{
Quadtree * children = new Quadtree [4];
children[0] = &prev_nodes[j];
children[1] = &prev_nodes[j+1];
children[2] = &prev_nodes[j+2];
children[3] = &prev_nodes[j+3];
nodes[i] = Quadtree (children);
}
if ( count == 1 )
{
return nodes;
}
prev_nodes = nodes;
}
}
```

The Quadtree root would keep the pointers to the all these newly created node lists but would I leak significantly by approaching this problem this way? It seems viable since I transfer the addresses of the newly created nodes to the Quadtree structure itself so although the list of pointers to these nodes are gone, the Quadtree keeps its own pointers to that I don't leak. Would that be correct however, with how I wrote my program right now?

(BTW sorry for all the right/left shifts, just learned the bit operators so I want to use them as much as possible to get more used to their concept).