How does a QuadTree work for non-square areas?

Question

I understand how quad trees work on square images (by splitting the image until the section is a single colour, which is stored in the leaf node).

What happens if the image has one dimension longer that the other, you may end up with a 2x1 pixel area as the smallest sub unit, making it difficult to use quadtree division methods to store a single colour. How would you solve this issue?

Answer 1

You could pad the image until it is an equal and power of two size. While it may add some extra memory requirements, the increase shouldn't be that large.

The 2x1 example would be padded to a standard 2x2 and store the real size or use a special value for padded nodes so you can restore the original size.

Answer 2

Why don't you allow empty leafes in your tree? Edit: Maybe i don't understand the question^^. Your problem is that you end up with a non square images like 2x1 and want to represent them as a quadtreenode?

When you have a 2x2 square like

1 2
3 4

you would create a Quadnode with something like "new QuadNode(1,2,3,4)"

I would suggest to handel a 2x1 square like

1 2

with something like "new QuadNode(1,2,null,null)" When you have bigger missing pieces you can use the same system. When you have a 4x2 picture like

1 2 3 4
5 6 7 8

you would get a "new QuadNode(new QuadNode(1,2,3,4),null,new QuadNode(5,6,7,8),null)"

This should also work with pieces with equal color instead of pixels.

Did i understand your problem and made myself clear?

Answer 3

A square is a special rectangle, Quad trees work on rectangles, too. You just need a split method which gives 4 rectangles for a given one.

In case the top most root quad cell is an rectangle, just divide the width and height by 2.

In case of pixels, it makes only sense if the root cell widthand height are both a power of 2.

So if root cell = 2048 * 1024 The split just divides both width and height by 2.