Dynamically flowing images to a page

Question

Hope someone can help, this has been driving me crazy for the last 3 days.

I'm working on a component of a POS system that gets and prints photos. These photos can vary in physical size depending on what the operator selects (eg small keyring, big keyring, fridge magnet, wallet etc). If the operator could only choose one at a time this would not be a problem, but what we'd really like to do is have the option to choose, say, 3 large keyrings, 1 small keyring and a fridge magnet.

What I've been trying to work out is a sane way of taking the quantities the operator has requested and laying the photos out in an optimised way, without resizing (this already happened earlier in my code) but allowing rotation 90º at a time. Furthermore if more images are selected than will fit on the page, a way of adding the extra images to a new page.

I initially thought this would be easy given that the function seems to already exist in the windows built in photo printing wizard, but we can't just send the images to the wizard as we need to make this process as simple as possible and restrict the operator from accessing printer settings. (also this will be running on a touch screen so the photo printing wizard would be a little fiddly anyway)

What I've thought about is the ImageMagick montage function, which at first seamed like a winner, and I'm already using IM in my program anyway, but then I realised there is no way of setting the canvas size before the montage operation begins. Then I looked at the various PDF libraries but none seem to support this.

Coming originally from a web development (php/jscript) background I recalled a jquery plugin that demonstrates what I need (almost) perfectly:

http://masonry.desandro.com/demos/animating-jquery.html (view the demo and resize the browser window)

When I picture it in my head, I imagine it going something like "place first image > check if there is horizontal room for another > if true, place another to the right/left > if false, check if there is vertical room > if true place another above/below > if both = false, create a new canvas and add image there" which sounds simple enough when put like that but actually will end up becoming insanely complicated when taking into account that the operator could add one keyring, then a fridge magnet, then another keyring, then change their mind and remove one, and add a smaller keyring!

Is anyone aware of a good way of doing this? I don't really have any relevant sample code yet, I've just got as far as defining an array of differently sized images on the disk!

Answer 1

Don't know if it helps since it sounds like you might know this. This sounds like an example of the rectangle-packing problem (2D version of the knapsack problem). There might be something on Google that helps.

---

Regards David R
---------------------------------------------------------------
The great thing about Object Oriented code is that it can make small, simple problems look like large, complex ones.
Object-oriented programming offers a sustainable way to write spaghetti code. - Paul Graham.
Every program eventually becomes rococo, and then rubble. - Alan Perlis
The only valid measurement of code quality: WTFs/minute.

Answer 2

Your question is unclear.  What type of application are you having an issue with?  

Are we supposed to click on your link and allow a script to run? 

Rudy   =8^D

---

Mark the best replies as answers. "Fooling computers since 1971."

http://thesharpercoder.blogspot.com/

Answer 3

@Riced

Thanks, I thought there might be a popular mathematical problem related to this, a la "Travelling Salesman". It would appear I am in need of a 2D bin packing algorithm to work out a set of X,Y coordinates for each image.

This looks like a good start:

http://www.devx.com/dotnet/Article/36005/0/page/1

If anyone has any code snippets that deal with this sort of problem I'd love to see it as I'm a little out of my depth here!

Answer 4

bird_flu

That looks a useful site. The article looks pretty good on a quick scan - downloaded the code and will have a look at it (probably tomorrow). My only gripe is there is no pdf (or similar) download of the article itself - but that is minor and the way most sites operate. :)

Not something I have done before so I'd need to have a good look before I could offer more help.

I suggest trying to develop some code and if you hit a problem post a new question with the problem and any relevant code, rather than adding to this thread.

---

Regards David R
---------------------------------------------------------------
The great thing about Object Oriented code is that it can make small, simple problems look like large, complex ones.
Object-oriented programming offers a sustainable way to write spaghetti code. - Paul Graham.
Every program eventually becomes rococo, and then rubble. - Alan Perlis
The only valid measurement of code quality: WTFs/minute.