D.V.D
Make a wish
- Reaction score
- 73
Hey guys, Im working on generating a quadtree by using a bottom up traversal. The idea is that I first make all my leaf nodes, add in the color value of the image I want to store inside my quadtree, then I start making higher and higher levels by using the nodes before it as a basis to create the tree. If the 4 children making up a node have the same color, then they are deleted since the structure is supposed to be sparse. The thing I want to check to see is if this is how I should code my builder and if it doesn't leak a whole bunch.
The quadtree itself is simple, here is the class and its constructor:
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:
The way its done is a pointer to a list of Quadtree nodes is generated. It begins with the leaf nodes which are outside of the loop. Each pixel is inserted into these leaf nodes and then when the loop runs, a new pointer to a list of Quadtrees is created. This one is one level higher and in the for loop, we merge together the nodes before it to generate the next node using the constructor above. The list to the leaf nodes (prev_nodes) is then set to the newly created level and the loop continues until we reach either level 0 (the root) or we only have one node left which is in any case, the root.
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).
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).
. You should try and code a bit more tidy and make sure that you're always consistent in your usage of pointers (*), addresses (&) and allocation with malloc / calloc / new.
