How can I pack ordered text into an arbitrary 2D polygon?

Question

Problem

I am trying to find a solution to a variation on a classic 2D packing problem - something similar to this question.

Given an arbitrary polygon P, and a phrase W, I want to "pack" the letters of W into P, using translation, scaling and 90-degree rotation, such that:

• the letters of W cover P as much as possible;
• the letters of W stay generally in order (that is, while W may be broken up into smaller sequences, the letters in that sequence should remain readable).

Some examples of what I'm trying to achieve:

Current Approach

I've started to set up a genetic algorithm to attempt to solve this problem, which takes the following approach:

• Maps P inside a 256x256 grid;
• Creates a simplified bounding polygon for each letter in W;
• Uses the position, rotation and scale of each letter as the chromosome (as Gray-encoded binary strings with 8 bits for each of x-position, y-position and scale and 2 bits for rotation, resulting in chromosomes of size 26*length(W) bits);
• Uses a crossover strategy that takes n letters from A and length(W) - n letters from B;
• Uses a simple mutation strategy where the probability of each bit being mutated in an individual chosen for mutation is 1 / 26;
• Currently evaluates fitness based on the amount of P covered by the bounding letter polygons.

Currently, the algorithm is up and running and finding solutions, although they're not particularly pretty yet as the fitness function doesn't take into account overlap between letters or the readability constraint.

It's also pretty slow, as the fitness evaluation requires a lot of geometric calculations (I'm writing the algorithm in Ruby, but using a C extension for the geometry stuff). I'm looking at using a neural network (or perhaps a SVM) to generate fitness estimates in line with the ideas in this paper and this paper.

Questions

I have a couple of questions about what I've done so far:

• Firstly, does the overall approach make sense? Obviously, most of the work and computation time will be in tweaking the fitness function, but before I get into the nitty gritty of that I want to check I'm headed in the right direction, and there's not a different method that can solve this better.

• How can I formulate the fitness function to account for the letter ordering / readability constraint?

• Are there any optimisations I can make to the fitness function to improve the number of generations I can feasibly compute?

Any other ideas or advice would also be really appreciated. I've read through most of the existing SO questions on similar topics and have read a number of papers on the topic, but haven't come across anything specifically dealing with the packing of text.

Thanks!

Answer 1

Q: How can I formulate the fitness function to account for the letter ordering / readability constraint?

Text Readability is related to the flow, i.e. the subsequent letters of a word being in the same subsequent direction for eye movement. I think a simple technique like the following might work.

Steps:

1. Calculate the centers of each of the letters after they have been placed (these could simply be the arithmetic mean of the x and y extents of the letters). These are the red dots in the figure above.
2. Calculate values for absolute change in angle in the direction of eye movement. I have shown angles angle 1 to angle 5 above.
3. Choose a limit for the maximum acceptable change in angle to be counted in flow, for example we can choose 35 degrees as our value.
4. Count the number of angles with absolute values greater than the limit in previous step. In our figure above, two angles angle 3 and angle 4 fall in this category, so count = 2.
5. If the count obtained in the previous step is greater than a particular value, the text placement is not readable.

I hope I am able to explain the idea. A derivative of the same could be a good solution.