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 used is in designing computer chips.) 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 two blocks in the same space. If you model that directly in a program, figuring out which blocks to move where when a collision would occur takes a good bit of calculation. And when you’re iterating over lots of possible layouts, that’s not what you want. Maybe describing where the blocks are relative to each other could make things easier.

The O-tree

Nine blocks of varying sizes placed next to each other, roughly forming a square. Each block is labeled with a different number 0 through 8. A list to the right gives the width and height of each block.

How could you describe this layout without giving the exact coordinates of any of the blocks? You could start by telling 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 be all you need to unambiguously describe this particular layout:

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, so let’s see if it works.

From O-tree to layout

If you gave the O-tree and list of block sizes to someone else, how could they accurately recreate your layout? First, they should know how to choose what block to place next: by a preorder traversal of the tree. [1]

The tree from before, with arrows pointing from the root to the first block to be placed, and from each block to the next one to be placed.

Next, they should know where to place it. The first block should be put in the lower left corner. Any block’s child goes immediately to the right of it, and each branch of the tree builds a layer on top of the previous one.

Going down the first branch of the tree, the blocks are placed from left to right, flat on the bottom. Going down the second branch of the tree, we start back at the very left and place the blocks from left to right again, this time stacked on top of the first layer of blocks.

This gives us an identical layout to what we started with! But the whole point of this was to make it easy to calculate, right? Let’s see how a program would do it.

The contour

Finding the x position of any block is easy: the root’s children are at the very left, and any block’s child is directly to its right. To find the y positions, we’ll keep a list of which blocks currently form the top layer. [1] Let’s build the list for the first three blocks, and see how to use it to find the next block’s height.

The first three blocks are laid in place, with a list giving the range of x positions each block spans and the y position of its top. The next block is about to be put down, but it's above two different blocks that are currently forming the top layer.

Since the new block is a child of 6 in the tree, let’s look at the block that currently comes after 6 in the list. It’s x range is from 0 to 3, and it has a height of 5. Since the new block’s x range goes past 3, let’s look at the next block in the list to see if it’s any taller. We see that the next block has a height of 3, and since our new block doesn’t go past it horizontally, our search is done. The tallest block the new one is going on top of has height 5. And since block 3 is completely covered now that we’ve placed the new one, we can remove it from the list.

The new block has been placed directly to the right of 6 and on top of 3. Block 3 has been removed from the list, since it's no longer part of the top layer of blocks, and the new block has been inserted after 6 in the list.

Generating alternate layouts

Now that we know how to place blocks according to an O-tree, moving a block to see if it improves the layout is just a matter of moving its node to another position in the tree. [2]

The sequence pair

The question of how to represent a layout for rectangle packing is very well researched, and several methods have been devised. Some are more similar than others; one that’s quite different on the surface from the O-tree is called a sequence pair.

Todo

  • Illustration for generating alternate O-tree layouts

  • Write sequence pair section

    • The creators of this method [3] describe it rather differently than I’ve heard elsewhere? But it is the nature of these things that you can think of it one way and then later find out that some simpler way is equivalent.

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

References