Databases
StackOverflow2013
Postsdbo
POHow can I pack ordered text into an arbitrary 2D polygon?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow can I pack ordered text into an arbitrary 2D polygon?
    primarykey
    data
    text
    <h2>Problem</h2> <p>I am trying to find a solution to a variation on a classic 2D packing problem - something similar to <a href="https://stackoverflow.com/questions/3516044/fill-arbitrary-2d-shape-with-given-set-of-rectangles">this question</a>.</p> <p>Given an arbitrary polygon <em>P</em>, and a phrase <em>W</em>, I want to "pack" the letters of <em>W</em> into <em>P</em>, using translation, scaling and 90-degree rotation, such that:</p> <ul> <li>the letters of <em>W</em> cover <em>P</em> as much as possible;</li> <li>the letters of <em>W</em> stay generally in order (that is, while <em>W</em> may be broken up into smaller sequences, the letters in that sequence should remain readable).</li> </ul> <p>Some examples of what I'm trying to achieve:</p> <p><img src="https://i.stack.imgur.com/ph9b1.png" alt="Example 1"> <img src="https://i.stack.imgur.com/2gCcn.png" alt="Example 2"></p> <h2>Current Approach</h2> <p>I've started to set up a genetic algorithm to attempt to solve this problem, which takes the following approach:</p> <ul> <li>Maps <em>P</em> inside a <code>256x256</code> grid;</li> <li>Creates a simplified bounding polygon for each letter in <em>W</em>;</li> <li>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 <code>26*length(W)</code> bits);</li> <li>Uses a crossover strategy that takes <code>n</code> letters from <em>A</em> and <code>length(W) - n</code> letters from <em>B</em>;</li> <li>Uses a simple mutation strategy where the probability of each bit being mutated in an individual chosen for mutation is <code>1 / 26</code>;</li> <li>Currently evaluates fitness based on the amount of <em>P</em> covered by the bounding letter polygons.</li> </ul> <p>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.</p> <p>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 <a href="http://www.stanford.edu/~bmorgan1/docs/AIAA-2009-1096-355.pdf" rel="nofollow noreferrer">this paper</a> and <a href="http://www.soft-computing.de/YJin_GECCO04.pdf" rel="nofollow noreferrer">this paper</a>.</p> <h2>Questions</h2> <p>I have a couple of questions about what I've done so far:</p> <ul> <li><p>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.</p></li> <li><p>How can I formulate the fitness function to account for the letter ordering / readability constraint?</p></li> <li><p>Are there any optimisations I can make to the fitness function to improve the number of generations I can feasibly compute?</p></li> </ul> <p>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.</p> <p>Thanks!</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USGavin Ballard
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow can I pack ordered text into an arbitrary 2D polygon?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POHow can I pack ordered text into an arbitrary 2D polygon?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POHow can I pack ordered text into an arbitrary 2D polygon?
      1. USGopal Nair
      1. VTFavorite
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload