CODEWITHSUNDEEP
algorithm
Kosmo零
Kosmo零

Reputation: 4151

Is there any known alg to fill certain area with rectangles of different size with most effective way?

By "effective way" I understand "with leaving more usable free areas for other rectangles".

I translating some game and I need to rebuild it's font. Font area is limited to certain size. I need to effectively fill that area with letters and letters combinations.

My current cycle increases X by 1 until we can place newly letter by that coords. If X hit font's right border, my cycle makes X = 0, Y++;

It leaves blank areas that is possible to use (marked with red): enter image description here

How to use free space more effective?

Like that (at least): enter image description here

Upvotes: 0

Views: 56

Answers (1)

Polish
Polish

Reputation: 466

I am assuming that the number of words in a row isn't very large(you said it's for some game). So you create a matrix say wordInfo[numberOfRowsInDisplay][maximumNumberOfColumnsForAnyRowInDisplay] you can calculate both of these variables by doing simple math like how many characters are in message(with width) and how many spaces(with width). It is filled as we go line by line and column by column for series of word/characters.

After that you for any wordInfo[row][column], represents width and height of that word/character. So if you populating some row you just see where this word/character ends(some number, say, pixel for example) and now check in previous row what was greatest height in this region including partial overlaps, and than set height of this word/character accordingly in wordInfo matrix, which will help in plotting next row. (It would be more efficient if you just only 2 rows in matrix, u got it?)

Note : if number of rows is large and there are man different height characters than in some cases might completely change.

Upvotes: 1

Related Questions