rectangle layout algorithm?

[Michael Chermside]

Richard Taylor writes:
> I need an algorithm to layout a collection of rectangles (images) within a
> bounding rectangle (sheet of paper).

Diez Roggisch replies:
> That smells like a 2d-instance of the  knapsack-problem, also called
> cuttingstock-problem - which is np-hard. In other words: There is no such
> thing like a general solution to this.

Diez, I believe you are mistaken about what it means to be np-hard. It
has nothing to do with whether the problem can be solved, just about
how long it may take for large input sizes. All of which may be
completely irrelevent if the number of rectangles to be laid out is
reasonably small (as it would be for creating a photo layout or
something like that).

Richard, I don't think that you meant to say what you said, but the
actual answer is exactly what you said. Your words were "I need an
algorithm to...". I suspect that you meant "I need some code to...".
But really, before you can code it, you need to define what algorithm
you want the code to implement!

For example, one common way of laying things out is to line them up
horizantally, shrinking things so they fit. This is what the BoxLayout
class in Java does. This algorithm would be easy to express in Python:

    # untested pseudo-code follows
    def layout(bounds, images):
        totalImageWidth = sum([i.width for i in images])
        hScaleFactor = float(totalImageWidth) / bounds.width
        xPos = 0
        for image in images:
            image.setXPos(xPos)
            image.setYPos(0)
            image.setWidth(int(image.width * hScaleFactor))
            if image.height > bounds.height:
                image.setHeight(bounds.height)
            xPos += image.width

Of course, I'm guessing that this isn't what you meant at all... if
you'd wanted something this simple you wouldn't have needed to ask.
But without knowing what algorithm you DO need, there's no way to
answer the question. So you are correct after all: you DO need an
algorithm to...

-- Michael Chermside