rectangle layout algorithm?

[Richard Taylor]

Hi

I need an algorithm to layout a collection of rectangles (images) within a
bounding rectangle (sheet of paper).

I feel sure that I am not the first person faced with this problem

Does anyone know of a Python library that provides such a capability?

(Actually building the composite image is not a problem, I am going to use
PIL to do that. It is knowing where to place the images that I need to
solve.)

Many thanks.

Richard

 

[Peter Maas]

I need an algorithm to layout a collection of rectangles (images) within a
bounding rectangle (sheet of paper).

I feel sure that I am not the first person faced with this problem

Does anyone know of a Python library that provides such a capability?

Not exactly but search for layout managers. wxPython/wxWindows has
a layout manager, Tcl/Tk also. pyUI (http://pyui.sourceforge.net/)
could be interesting.

Try http://www.google.com/search?q=python+"layout+manager"

Mit freundlichen Gruessen,

Peter Maas

 

[Diez B. Roggisch]

I need an algorithm to layout a collection of rectangles (images) within a
bounding rectangle (sheet of paper).

I feel sure that I am not the first person faced with this problem

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.

Some links I found:

http://www.inf.uos.de/papers_html/or_94/cutpaper.html

Maybe someone implemented a heuristic solvor for this in python - go google
for it

 

[Terry Reedy]

Hi

I need an algorithm to layout a collection of rectangles (images) within a
bounding rectangle (sheet of paper).
...
(Actually building the composite image is not a problem, I am going to use
PIL to do that. It is knowing where to place the images that I need to
solve.)

Among other things, the algorithm you want depends on the following:
Are the rectangles all the same size or different sizes?
Do you want to pack as tightly as possible or spread out over a background?
Are the images ordered or may they be placed randomly?
What is your criterion for a good versus poor layout?

Terry J. Reedy

 

[Richard Taylor]

Among other things, the algorithm you want depends on the following:
Are the rectangles all the same size or different sizes?

They are photographs, so they are generally all the same size.

Do you want to pack as tightly as possible or spread out over a
background?

I want to fit as many on a specified sheet of paper as possible. I would
like to be able to specify the paper size at run time e.g. A4, A3 etc.

Are the images ordered or may they be placed randomly?

They can be placed randomly. They can also be rotated in order cover more of
the page as they will be cut into separate pictures once printed.

What is your criterion for a good versus poor layout?

Maximum use of paper is the criteria. Photo paper is expensive

Regards

Richard