How to recursively pack rectangles into a square

Question

I'm writing a program at the moment that will display rectangles in PyGame according to the sizes of files. This is fully based on search trees, with the root being a folder, its subtrees being either folders or files, and files being the leaves, as they dont have any subtrees. I want my program to recursively fill the square with reectangles based on the sizes of the files in relation to the root folder. I.E: root folder has size 151, file1 has size 50, so file1 would take up roughly 33% of the whole square. I also need to make it such that I could make horizontal rectangles if need be (i.e if there isn't any space to do it vertically, do a horizontal rectangle). The function takes in a rect to use, which is different from self.rect defined in my object Filetree (described below)

So my program is based around an object named FileTree, which has self.rect, which is its rectangle size (with x, y being the startpoint, width, height, being its width and height). It has randomly assigned colors, and it has subtrees. Basically I just don't see where my program is going wrong, because when I call the function, I get a bunch of rectangles with the right ratios, just one on top of the other,so it doesn't space it properly. I was wondering if it was a problem with the recursion formula I'm using, since debugging it gives me multiple rectangles with the same starting point, when they're supposed to be one next to the other (i.e one starts where the other one ends)

 x, y, width, height = rect
#rect is a tuple (x, y, width, height)

        if self.is_empty():
            self.rect = (0, 0, 0, 0)

        if self._parent_tree is None:
            self.rect = rect

        else:
            p = self
            while p._parent_tree is not None:
                p = p._parent_tree
            percentsize = self.data_size / p.data_size
            newsize = math.floor(p.data_size * percentsize)
            if p.rect[2] >= newsize + x > y + newsize and percentsize != 1:
                self.rect = (x, y, width, newsize)
            elif p.rect[3] >= newsize + y >= newsize + x and percentsize != 1:
                self.rect = (x, y, newsize, height)
            elif percentsize == 1:
                self.rect = rect
            else:
                if newsize + width > height + newsize:
                    self.rect = (x, y, width, p.rect[3])
                elif newsize + height >= newsize + width:
                    self.rect = (x, y, p.rect[2], height)

        for sub in self._subtrees:
            sub.update_rectangles(self.rect)

Answer 1

You didn't ask a question. I will offer some advice, anyway.

Expressions like p.rect[3] are not especially clear, despite the helpful and informative comment you wrote. If you need to use tuples, then consider unpacking before using: x, y, w, h = p.rect, then use the height h. Even better, make rect a namedtuple.

I want my program to recursively fill the square with rectangles ...

Yes, this is fairly clear. But better to phrase it as "fill a rectangle with smaller rectangles ...". That sets you up nicely for recursion.

also need to make it such that I could make horizontal rectangles

Yes. Write a predicate, def is_vertical(rect), that returns true when height > width. Then your if statement for how to split a rectangle will be perfectly clear.

The percentsize != 1 tests seem a bit arbitrary. Doing everything in pixels ought to suffice.

space for files vs subdirs

There's a bigger design issue that seems missing, so far.

Space within a rectangle fundamentally goes to two different places:

1. immediate children
2. subtrees

At a minimum you probably want to assign them different colors.

For space allocation, you probably want to handle sum of immediate children all at once, finding a splitpoint that accommodates all of them before carving each one out, and then recursing on subtrees.

EDIT:

I know this will sound boring, but I'll say it anyway. Eat your vegetables! Show me your unit tests! Please.

Honestly, they're good for you. You're complaining that "it should be simple", "it should be working", yet "it isn't working". Whenever you're in that situation, always make it even simpler, always write down the dumbest unit test you can think of. Your claim is "this totally works", and the unit test will prove or disprove that.

Often the act of writing a test will convince you that "this is hard to test", which is good, Great even. Once a test offers you that insight, you may be motivated to refactor, to change the API so it is very very easy to test, easy even to test the "weird" cases. (Or you evict the weird cases so they're no longer part of the mainline API and are handled elsewhere.)

Show us a unit test, please, of a rectangle being subdivided. Hopefully at least one or two tests that work, along with a failing test. Also, it wouldn't hurt to show some numeric inputs and the graphical output.