Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote -2 down vote favorite

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
Why those downvotes? Seems like a perfectly valid and correctly explained question. – MainMa Oct 14 '12 at 22:04
1  
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

closed as not constructive by mattnz, ElYusubov, 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 specific 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, see the FAQ for guidance.

1 Answer

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.