How does QuadTree work for non-square areas?

Question

I understand how square trees work on square images (dividing the image until the section has one color, which is stored in the node sheet).

What happens if the image has one size longer than the other, you can get a 2x1 area as the smallest subunit, which makes it difficult to use Quadtree split methods to store one color. How would you solve this problem?

Answer 1

You can place an image until it is equal and has two sizes. Although this may add some additional memory requirements, the increase should not be so large.

The 2x1 example will be complemented by the standard 2x2 and store the actual size or use a special value for the added nodes so that you can restore the original size.

I know this is an old question, but I hope I helped anyway.

Answer 2

Why don't you allow empty leaves in your tree? Edit: Maybe I do not understand the question ^^. Your problem is that you get non-square images like 2x1 and want to represent them as quadtreenode?

If you have a 2x2 square, for example

12
3 4

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

I suggest passing a 2x1 square e.g.

12

with something like the “new QuadNode (1,2, null, null)” When you have the big missing parts, you can use the same system. When you have a 4x2 image like

1 2 3 4
5 6 7 8

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

This should also work with parts with the same color instead of pixels.

I understood your problem and made it clear?

Answer 3

A square is a special rectangle; square trees also work on rectangles. You just need a split method that gives 4 rectangles for the given.

In case the top big square cell is a rectangle, just divide the width and height by 2.

In the case of pixels, this only makes sense if the width and height of the root cell are 2.

So, if the root cell = 2048 * 1024 Separation just divides the width and height by 2.