Laying out multiple images of diff to minimize wasted space

[jsavage]

I have dozens of images with different canvas sizes that I want to layout efficiently without changing their relative scale. Is there an alternative to montage that will pack the images together as best it can minimizing wasted space?

using ImageMagick 6.4.8 2009-01-06 within cygwin environment:

First I trim each as they all have excessive whitespace all around.

mogrify -trim *.gif This works great.

Now they are all different sizes. I dont want to resize as these images need to stay at their original scale.

If I use montage as in:
montage *.gif -geometry +10+10 montage_geom.gif

then the images are laid out in a regular grid with lots of wasted space between them.

Whereas what I want is for them to be laid out to minimize wastage. Eg of paper when printed or plastic if cut out using laser cutter.

I am sure this must have been done before. Has anyone round here solved this or got any alternative ideas?

Rgds,
James

[anthony]

I have dozens of images with different canvas sizes that I want to layout efficiently without changing their relative scale. Is there an alternative to montage that will pack the images together as best it can minimizing wasted space?

At this time montage is the only 'packing' method implemented.

I have proposed additions for -append expandsions to allow not only montage grid packing (with HTML link referencing) but also new methods such as line-by-line packing (with gravity, and justification) .

However you can DIY it (please submit what you come up with)
using a free form image placement technique...
See Image Layering, Examples of Image Laying
http://www.imagemagick.org/Usage/layers/#example

NOTE: the script form which can be used as a starting point.

The locations of the images relative to each other does NOT matter to the -layers merge operator,
they can be negative or extremally positive positions. The canvas will only be created large enough to show all the positioned images, so when +repage is used the canvas is fits the images, regardless of the calculated positions.

Whereas what I want is for them to be laid out to minimize wastage. Eg of paper when printed or plastic if cut out using laser cutter.

I am sure this must have been done before. Has anyone round here solved this or got any alternative ideas?

Oh it has been done before. It is a well known problem known as the knapsack, or packing problem. this can involve 1 dimention (weight limits) 2-D (fabric cutting) or even 3-D (volume packing).

The problem is that it is known to be a NP-complete problem That means no one has a solution, in reasonable time for large numbers of objects (and probably never will) that will always be the best solution for any type of object.

that does not mean there are no rough solutions, you just need to define how you like to 'pack' the images into a canvas. Is the canvas size fixed? how distributed you wnat the images and the left over space, in size order, original order, random order? you like to rotate or otherwise modify the images? slight overlaps acceptable?

You want to make a 'click' map too? Bonzo on his PHP magick pages has played with using a second image with solid colors marking the image areas. so that a 'click' location can lookup the index color from that second image and jump to the appropriate page, regardless of how images overlap or confuse each other.


Figure out what you want then how to layout your images.

And please submit your findings and solutions.