Algorithm for Text Wrapping Within a Shape

Question

I am looking for an algorithm to wrap text within a non-rectangular shape, preferably based on the Knuth and Plass algorithm. The hardest part of this is that the lines may have different heights due to differing font sizes in the text. The image below is an example of what the algorithm should be able to generate.

Thompkins

It's me or the image is too tiny? – Doorman

my image isn't loading. go to tutorialsroom.com/tutorials/images/text_in_shape_04.gif – Thompkins

Interesting question. The TeXBook has some examples of this; you should look it up. (Or maybe it was in Knuth's Digital Typography book.) – Pejoration

The website seems to disable (and not want) hot-linking; I've uploaded it elsewhere and updated your question. – Pejoration

By "different height", do you want to fill the text line by line like your pic or have no fixed lines like a tag cloud (but without overlap)? – Kuenlun

The shapepar package for LaTeX is capable of such things. Maybe its source can help you (package description and sources: ctan.org/pkg/shapepar, example usage: tex.stackexchange.com/a/139744). – Splashdown

Answer 1

For a simple algorithm, let's assume that you can compute a bounding box around each word, and that you have an image with a mask of the shape that you want to fill.

Sweep down from the top of the image mask until you find a line that is as long as the first word. See if you can extend it downward into a rectangle the size of the bounding box. If so, drop the first word there. If not, keep sweeping.

Once you drop a word, see if you can extend the bounding box to be the width of (first box + second box + space) and the height of max(first box,second box). If so, drop the second word there. If not, center the first word left-to-right within the bounding box that will fit within your image mask (left to right), remove that bounding box from the mask, and keep going.

You can make this slightly fancier by insisting that lines have the same baseline even if broken by the shape (e.g. lines across the top nubs of the heart); you then need to have an alternate "continue along this baseline" condition. But the basic idea above, with an image mask that you use to try to fit rectangles inside which are removed when you're done, will do the job.

(It is faster to use geometric operations than pixel-based ones described here, but then one has to worry about all the cases for figuring out how a bounding box fits within an arbitrary polygon, and that's a bit long to explain here.)

Posture

Answer 2

Edit, Updated

Try

text / html

    
        gggggggggggggg              gggggggggggggg 
     gggggggggggggggggggg         gggggggggggggggggg
   gggggggggggggggggggggggg     gggggggggggggggggggggg
 ggggggggggggggggggggggggggg   ggggggggggggggggggggggggg
ggggggggggggggggggggggggggggggggggggggggggggggggggggggggg
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggg
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggg
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggg
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggg
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggg
 gggggggggggggggggggggggggggggggggggggggggggggggggggggggg
  gggggggggggggggggggggggggggggggggggggggggggggggggggggg
   gggggggggggggggggggggggggggggggggggggggggggggggggggg
     ggggggggggggggggggggggggggggggggggggggggggggggggg
      gggggggggggggggggggggggggggggggggggggggggggggg
        gggggggggggggggggggggggggggggggggggggggggg
           ggggggggggggggggggggggggggggggggggggg
              gggggggggggggggggggggggggggggg
                 gggggggggggggggggggggggg
                    gggggggggggggggggg
                       gggggggggggg
                         gggggggg
                           ggggg
                            ggg
                             g

js

var text =  "Lorem ipsum dolor sit amet," // `string` , `array` 
, i = -1
, elem = document.querySelector("pre");
elem.innerText = elem.innerText.replace(/[^\n|\r|\t|\s+]/g, function() {
                   return text[++i] 
                 });

        Lorem ipsum do              lor sit amet,  
     consectetur adipisci         ng elit. Vivamus b
   landit nisl eu posuere s     uscipit. Etiam at quam
  sed nulla consequat finibu   s et eget ligula. Nam sit
 amet imperdiet eros. Ut a congue nibh. Sed ac arcu non r
isus commodo lobortis et at lorem. Pellentesque pulvinar v
enenatis pellentesque. Praesent sed pulvinar justo. Ut nec
 turpis lectus. Suspendisse porta ipsum orci, nec vestibul
um tellus luctus quis. Morbi eleifend vel nibh sed rutrum.
 Etiam feugiat, nunc et efficitur accumsan, quam magna lac
 inia neque, eu ullamcorper purus turpis eget urna. Etiam
   lacus mi, gravida vel mollis ut, viverra sed ipsum. M
   auris in augue turpis.Nulla facilisi. In tristique t
     ortor sit amet leo cursus, sit amet varius ligula
       sollicitudin. Mauris commodo et sapien id sce
        lerisque. Integer et diam eget arcu bibend
           um ornare a in tortor. Lorem ipsum do
              lor sit amet, consectetur adip
                 iscing elit. Aliquam veh
                    icula diam ac laor
                       eet tincidun
                         t. Integ
                           er se
                            d t
                             e

var text = "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Vivamus blandit nisl eu posuere suscipit. Etiam at quam sed nulla consequat finibus et eget ligula. Nam sit amet imperdiet eros. Ut a congue nibh. Sed ac arcu non risus commodo lobortis et at lorem. Pellentesque pulvinar venenatis pellentesque. Praesent sed pulvinar justo. Ut nec turpis lectus. Suspendisse porta ipsum orci, nec vestibulum tellus luctus quis. Morbi eleifend vel nibh sed rutrum. Etiam feugiat, nunc et efficitur accumsan, quam magna lacinia neque, eu ullamcorper purus turpis eget urna. Etiam lacus mi, gravida vel mollis ut, viverra sed ipsum. Mauris in augue turpis."

+ "Nulla facilisi. In tristique tortor sit amet leo cursus, sit amet varius ligula sollicitudin. Mauris commodo et sapien id scelerisque. Integer et diam eget arcu bibendum ornare a in tortor. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Aliquam vehicula diam ac laoreet tincidunt. Integer sed tellus sit amet lacus bibendum tristique a a nulla. Quisque venenatis suscipit est eget ultricies. Quisque ac orci convallis, interdum enim quis, dictum justo. Phasellus tincidunt nisi vitae justo fringilla, sit amet pellentesque enim dictum. Duis porttitor convallis feugiat. Sed lectus massa, consectetur et vestibulum a, egestas ac eros. Proin mollis ligula tellus, a dignissim eros placerat sed. Donec vel blandit magna. Etiam quis tortor rhoncus, porta ante et, pretium mi."

+ "Vestibulum ut risus convallis, sagittis orci sed, faucibus erat. Aliquam maximus suscipit lectus, vel pellentesque enim dictum nec. Sed et ex id mauris finibus molestie. Aliquam erat volutpat. Etiam nec ultricies est. Aenean vitae mi id neque vulputate suscipit vel vitae ante. Nam sit amet mi diam. Phasellus efficitur faucibus viverra. Proin cursus purus et tortor dictum elementum. Nunc vehicula erat volutpat, rutrum metus bibendum, blandit sem."

+ "Nam eu ante eros. Sed pellentesque accumsan neque, eu vulputate lectus luctus ac. In hac habitasse platea dictumst. Nulla vitae dictum diam. Sed eget mauris in felis luctus luctus. Mauris volutpat lacus in est dignissim, sit amet venenatis ipsum laoreet. Phasellus semper id velit ut tristique. Proin dictum erat at mauris lacinia blandit. Ut scelerisque mi ex, ut pretium elit commodo sit amet. Praesent faucibus turpis tellus, ac vulputate felis aliquet eget. Ut est urna, dignissim nec risus sit amet, eleifend lacinia enim. Donec non massa in purus efficitur placerat. Donec accumsan neque elit, eget vulputate metus finibus quis. Ut interdum sem vel felis imperdiet pretium. Integer erat neque, bibendum id egestas nec, facilisis sed massa."

+ "Curabitur sit amet mattis odio. Mauris mattis turpis eu lectus eleifend, semper ultrices elit malesuada. Mauris fringilla arcu sed sem vehicula vulputate. Donec semper nisl ut urna bibendum, quis eleifend tortor commodo. Pellentesque vehicula est et neque vulputate accumsan. Duis faucibus sodales lacus et suscipit. Pellentesque tortor enim, pulvinar scelerisque pretium non, aliquam sed risus. Vestibulum aliquam dolor ipsum, eget pretium ante fermentum a. Donec semper lectus pulvinar tellus hendrerit sagittis. Nunc blandit sed ligula vel consequat. Etiam sed est quis nulla blandit blandit. Sed in enim pulvinar elit accumsan faucibus sed sodales lorem. Aenean ac efficitur arcu, sed fringilla lectus."

, i = -1;
var elem = document.querySelector("pre");
elem.innerText = elem.innerText.replace(/[^\n|\r|\t|\s+]/g, function() {
                   return text[++i] 
                 });

<pre>    
        gggggggggggggg              gggggggggggggg 
     gggggggggggggggggggg         gggggggggggggggggg
   gggggggggggggggggggggggg     gggggggggggggggggggggg
 ggggggggggggggggggggggggggg   ggggggggggggggggggggggggg
ggggggggggggggggggggggggggggggggggggggggggggggggggggggggg
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggg
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggg
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggg
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggg
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggg
 gggggggggggggggggggggggggggggggggggggggggggggggggggggggg
  gggggggggggggggggggggggggggggggggggggggggggggggggggggg
   gggggggggggggggggggggggggggggggggggggggggggggggggggg
     ggggggggggggggggggggggggggggggggggggggggggggggggg
      gggggggggggggggggggggggggggggggggggggggggggggg
        gggggggggggggggggggggggggggggggggggggggggg
           ggggggggggggggggggggggggggggggggggggg
              gggggggggggggggggggggggggggggg
                 gggggggggggggggggggggggg
                    gggggggggggggggggg
                       gggggggggggg
                         gggggggg
                           ggggg
                            ggg
                             g
</pre>

Unrighteous

interesting but doesn't answer the question. the question is about 'non-rectangular' shapes so even if you manage to create a css heart (which your suggestion only partially achieves), it does not provide an algorithm to arrange text. – Hasheem

I'm not the OP so will leave future exchanges to him/her but this doesn't seem to fit either. it doesn't deal with shapes and it doesn't preserve words. – Hasheem

This is an elegant way to go, +1 – Adept

It's an elegant way to go if you've already got a heart full of g's and you want to replace it with text. It does not keep words together, it does not work with variable width fonts, etc.... – Reyesreykjavik

Answer 3

Let's say each letter has a specific size(width and height, in this case we probably only care about width because all letters have the same height). Then we need the following:

1. Wrapped objects of each word - to make sure there's no fragmentation of the word
2. given width of each word.
3. Partition the polygon into chunks that are the heights of the word. So you have x horizontal strips that make up the image.
4. Then, find the width of the inside polygon if you were to inscribe words inside. This means you're removing the round edges of the heart. Where a vertical line can intersect the edge of the heart on the strip is where you remove the round edge.

Now that we have the size of each strip of the image, let's say we have this (i'm using arbitary unit for width):

[_________] [__________]  <-- 10 width (5 each)
  [__________________] <-- 9 width
    [_____________] <-- 7 width   
       [_______] <-- 5 width
         [___] <-- 3 width
          [_] <-- 2 width

EDIT: Just realized how ugly the heart is, my bad.

Now we need the size of each word, and insert them sequentially. Each block has x width, and each word object has y width. If y width > x width, we move to the next line and check there

considering we already have widths
while(image.hasNextChunk()){
    currentChunk = image.nextChunk();
    if(currentWord.width < currentChunk.width) //insert here and then change currentWord to nextWord
    ...
}

I think this is what you want, but I'm not completely sure. Let me know if this helped! :)

Tessellation