Data structures for arranging rectangles

Say you were writing a program that would take a bunch of rectangles and try arranging them in different ways. (An example of where this is relevant is in designing computer chips with many components.) How would you keep track of where each rectangle is, and when you move of one of them, how would you know where the others end up?

If you think about physically laying out blocks and moving them around, it doesn’t seem like a difficult problem. You can see where every block is, and physics keeps you from putting one in the same space as another. Surely it’s not that hard to model in a program. You just have to know where the corners of each block are and place the others in spaces outside of what’s already occupied.

If the way you’re describing a layout is by the coordinates of the corners of each block, then changing the position of one block is going to take a good bit of calculation to adjust the positions of nearby blocks so the layout is valid again. And when you’re iterating over lots of possible layouts, that’s not what you want. If we could describe where the blocks are relative to each other, maybe we could speed things up a bit.

The O-tree

Nine blocks of varying sizes placed next to each other, roughly forming a square with some gaps between blocks.

If you were to describe this layout without giving the exact coordinates of any of the blocks, where would you start? Well, first it would help to label each block.

The same blocks, but now each block has been labeled with a different number 0 through 8. A list to the right says what the width and height of each block is.

From layout to O-tree

Something you might do next is describe which blocks are furthest to the left. (Or furthest to any of the four sides, but conventionally the left is chosen.) So, at the very left of this layout, from bottom to top, there’s 3, then 6, then 8. That’s the first level of the tree. Any blocks immediately to the right of one of those is a child to that block, and so on. [1]

The same blocks, now with a tree diagram overlaid on it. The root is to the left of the blocks; its children are 3, 6, and 8. Since 1 is touching 6 on the right, it's a child of 6, and so on.

Now, this should theoretically be all you need to unambiguously describe this particular layout of this set of blocks:

On the left, the tree diagram that was previously overlaid on the blocks, now displayed in a compact form. On the right, the list of block heights and widths from before.

It looks a lot easier to manipulate than what we were imagining before, but does it really work?

From O-tree to layout

First, if you gave the O-tree and list of block sizes to someone else, could they accurately recreate your layout?

Todo

  • Finish O-tree section

    • How does the contour get generated and help find y positions?

    • Compact representation of the tree with 0s and 1s

    • How to perturb a layout

  • Write sequence pair section

  • Compare the representations–can a sequence pair ever be more efficient than an O-tree?

References