Number of max. Rectangles that can be placed inside a symbol
I need a solution for a rather complex problem. Exactly, I need to calculate the number of rectangles that can be placed inside a letter / character with a given size, given that all rectangles are the same size, but it (size) and the character of the letter / character (of a certain regular font) can be changed by the user (this will be used as a web-based signage price calculator). If you describe it graphically, it looks like this:
alt text http://habreffect.ru/files/319/aab0644b9/img.png
Any ideas or helpful links would be much appreciated. thanks in advance
a source to share
This is 2D packaging. This page might clarify it a bit: http://users.cs.cf.ac.uk/CLMumford/heidi/Background.html
The wiki page on bin-packing: en.wikipedia.org/wiki/Bin_packing_problem has a link to a software package that might come in handy: http://code.google.com/p/caparf/
You're out of luck this is NP-Hard. You are in luck that this is a widely researched topic and has many approximation algorithms. The most up-to-date bin-packaging literature should contain information that should help.