Quadtree issue - storing redundant info

Question

I have an image which is not a square (m x n dimension). Also its dimensions are not to the base 2 (i.e m not = 2^k & n not = 2^k). I have dealt with this by placing the image in a larger square (the next power of two) using the following:

int width = (int)Math.ceil(Math.pow(2, Math.log(img.width)/Math.log(2)));
int height = (int)Math.ceil(Math.pow(2, Math.log(img.height)/Math.log(2)));

Depending on which yields the biggest dimension, I set the square to be drawn at the max dimension, that is:

if (img.width > img.height) {
    // draw width * width square
}

if (img.height > img.width) {
    // draw height * height square
}

Issue:

The quadtree now looks completely different as it is storing all the non-image nodes in the tree. This obviously affects the supposed image data (i.e. min/max depths) and the entire tree shape itself. My question is, am I doing this in an efficient way and if so, how do I not store the data that doesn't belong to the image? If it isn't the best way to draw a non-square image could someone point me in the right direction? All articles on google seem to be far too in depth for my purposes.

Answer 1

The nice thing about quadtrees is they will store large chunks of identical data. Your extra blank image data should only be adding a little to your overall storage size. I suggest, you add an extra bit of information with your data structure that stores the actual original dimensions of the image. When deserializing your quadtree, you can "cut" off the extra part based on the actual dimensions to produce your original.

Answer 2

Perhaps instead of having your tree terminate in (notional) individual pixels, it could store small blocks of p pixels by o pixels, for some p x o which would make the number of blocks per side a power of two. That would make your tree behave nicely, at the expense of introducing another concept into the structure.