Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a rectangular board of height H and width W.
N colors are given and each color occupies Xi percentage of area on the board.
Sum of Xi's is 1.

The colors on the board must be placed in rectangles.
An optimal solution has the rectangles' aspect ratios as close to 1 as possible.
An ideal case has the board filled only with squares.

What's the best algorithm for laying out the rectangles?

share|improve this question

closed as not constructive by mattnz, Yusubov, Caleb, Walter, Thomas Owens Oct 15 '12 at 14:47

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.If this question can be reworded to fit the rules in the help center, please edit the question.

Why those downvotes? Seems like a perfectly valid and correctly explained question. – MainMa Oct 14 '12 at 22:04
The down votes are likely due to the question being both overly broad (help me solve this class of problem) and too narrow subject matter (i.e. who else benefits from the answers) - i.e. not really suitable for the Q/A Format. – mattnz Oct 14 '12 at 22:49
@MainMa - The downvotes may have also been due to the question being difficult to understand. Hopefully my edits will make it easier for others to weigh in with an answer. – GlenH7 Oct 14 '12 at 23:43
Without a measurable criterion for determining "best", the best algorithm depends on who you ask. You could sort by some value (hue, saturation, etc.), or arrange samples randomly, or let the user place the samples, etc. – Caleb Oct 15 '12 at 4:56
This is a perfect example problem for application of a genetic algorithm. You have already specified your evaluation algorithm (smallest changes in aspect ratio, board filled as much as possible etc). The only outstanding work to do, is to come up with a representation of your board layout based on a genetic gene. It wouldn't be hard to implement and you would get very impressive results and in a short timeframe. – z0mbi3 Nov 26 '14 at 14:22
up vote 0 down vote accepted

You could do it like this:

  • find the largest square place in the board
  • place a square of the largest colour left to place in there, subtract this Pi by the appropriate amount
  • repeat

Your question, however, is far from complete and unambiguous If you want to only have one rectangle per colour, things can get a bit more complicated. (brute force, not very elegant)

  • Factor all the areas for the colours into their prime factors, and get all possible two-element factorizations that will fit within the board. For most numbers up to reasonable amounts, this will be relatively manageable (if not, you could just scale down a factor ten, the visual result won't differ much).
  • for each possible combination of these two-element factorizations, try to fit them into the board (most will not succeed)
  • find the one with best ratios, weighted however you want

I can imagine a lot better approaches exist, but these might do the trick if your board is not too large, and the amount of colours is reasonable

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.