Algorithm for fitting text into an irregular shape

[Kasyan Servetsky]

Dear forum,

I am attempting to write a script for a company that prints hoodies for school leavers. Currently, they just paste the list of names into the number box and then adjust the text manually moving things around, adjusting font size, line spacing, kerning, manually adding in spaces or line breaks until it looks ok, but it is quite difficult and time-consuming, and annoying!

The trickiest part is filling an irregular shape (a text frame) with names.

At the moment, they can be in three variants:

1. First name only
2. First name and initial
3. First name and surname

In fact, I think, there will be needed two algorithms: one for 1 and 2 and another for 3.

The requirements are just to fit the children’s names in the outline of the “23” (for this year) and look neat and correct. All names need to be the same size as each other (no names bigger than others). Initial/surname would need to not be split from the first name by a line break. The shape should be filled with 1 or 2 times the name of each child (1 or 2 times depending on if we need to fill up more space when there aren’t many children, for instance).

The text frame is converted from text with the ‘create outlines’ command and adjusted manually. Now they want “23”, “24”, but in the future, they might need any word, like “Ski Trip” or “PE”.

My customers have looked on InDesign forums and other design forums and googled everything but they couldn’t find any software that will do this automatically for them with good results, or a way to easily do this in InDesign.

They could find wordcloud type software but often that makes lots of repetition and also makes some words bigger than others, which they don’t want as they don’t want one child to appear more ‘important’ than others, they all need to be the same size.

I am experimenting with this trying to find the right approach. Here on my site, I’m writing my thoughts aloud posting code snippets. (They’re constantly changing so I want to update them on the fly).

I’ve got a feeling that I’m reinventing the wheel and similar algorithms have been already developed, so any pointers would be greatly appreciated. I googled for this info, but couldn’t find what I need.

[Rene Andritsch]

One thing I would consider from a design stand point of view is the justification. If the letters get torn apart it always looks ugly and it is harder to read. Maybe this could be solved with using different point sizes for the names? Kind of a word cloud inside a shape. But I’m not a programmer so this is definitely tricky. 

[m1b]

Apologies in advance for not addressing your actual question, but I agree with @Rene Andritsch about the justification—it looks weird and makes some names look "special" anyway, which client doesn't want. I wonder about using a variable-width font?

Otherwise I'll have a think about a solution. Have you looked at one-dimensional bin-packing algorithms? Each line is basically a one-dimensional (width) bin.

- Mark

[Kasyan Servetsky]

Thanks for the quick replies, Rene and Mark!

Different point sizes for the names are not an option: it is required that the size should be the same for all names. I agree it doesn’t look good, but hyphenation is not allowed as well and the script should somehow put all this text into the shape.

I will try to play with variable-width fonts. Great idea! As for me, it looks better with Acumin Variable Concept than with Arial. Also, it seems if I change adjustment to center and rework the shape — make a chain of rectangular text frames instead of one irregular shape — it would look visually more pleasing.

I will look into one-dimensional bin-packing algorithms but this might be beyond my level: I’m not a programmer by background. At first glance, it looks scary to me.

[Loic.Aigon]

Hi Kasyan,

I have been thinking to your challenge since you posted it. I don't have anything to propose that could help apart this reasoning. If I had to do this, I would probably take distance from the idea of finding a typesetting algorithm in an irregular shape given all the troubles that is even manually.

I would probably try to segment the shape into a series of individual textFrames (pathfinder or some intersecting algorithms if any exist). Then I would take names by characters length in descending order and would try to fit them in the smallest textframes at first (so I can avoid kerning if possible). And I would go upwards with larger text frames filling with other names. 

Of course, that's worth if customer doesn't want to preserve alphabetical order. Otherwise, it will become quite complex.

It's quite a bit of work so sorry for not providing code here. And I am not even sure it's a good idea but this is how I would try to tackle it.

HTH

Loic

[Kasyan Servetsky]

Hi Loic,

Thanks for your tip!

I was about to move in this direction. In my previous post, I wrote: “… rework the shape — make a chain of rectangular text frames instead of one irregular shape…”. Now after your explanation, I see it clearer. I will try to make individual text frames, as you suggested, and number them by labels so the script would know from which frame to start and where to go next. (The names will be repeated —  twice, or more — if not enough children in the class to fill the whole year number). The script is going to create an InDesign document from a template, fill the shape text frames with names, and finally export a PDF file to be printed. So, preparing such a template manually once a year won’t be hard.

Alphabetical order doesn’t matter at all: names can be shuffled if necessary.

— Kasyan

[Marc Autret · Accepted solution]

Hi Kasyan,

Very interesting problem! That's not a pure one-dimensional bin-packing algorithm because you want to distribute the items so that they use as many lines as possible (so we don't expect an optimal packing).

I found a simple and fast approach that may help you get closer to a solution. Here is a proof of concept:

1. BEFORE RUNNING THE SCRIPT

2. AFTER

If a solution is found, the result is almost instant (say 500 ms). My code has some tricks for speeding up width calculations of both the destination lines and the source items. Using centered-aligned dots (without line breaks) in the destination area allows us to calculate line widths with accuracy, and we can detect splitted-line cases and manage them.

But the important part is outside the InDesign DOM, that's the packing algo 🙂 The idea is very simple:

• Sort widths in source lines and destination bins.

• Pack as many lines as possible in the bins (from largest to lowest values).

• Update the capacities of the bins and resort.

• Loop until all source lines are placed.

(I have a JSX to share but didn't find your email address in my contacts [!], let me know where I could send you the script).

Best,

Marc

[Loic.Aigon]

Very educational, thanks @Marc Autret for this demonstration.

[Kasyan Servetsky]

Hi Marc,

Thank you very much for your reply! I'm looking forward to see your code.
My e-mail: askoldich [at] yahoo [dot] com

Regards,
Kasyan

[Marc Autret]

Hi @Kasyan Servetsky 

Just sent you the sample code.

HTH.

Best

M

[Kasyan Servetsky]

Thank you, Marc!

[Robert at ID-Tasker]

I've done something similar long time ago - but for filling poems (written by kids) on pages without splitting contents between pages / spreads - kind of @Marc Autret's solution - but more "brute force" 😉

Script was copying longest poem first, then trying to paste next poem that would fit - then checking if it fits without splitting - if it splits then Undo and copy next, shorter poem. 

Relying on the length of the text when each phrase is one-per-line won't take into account situations when phrase will fit because of how line/paragraph composer works - will squeeze it a bit - but then, it depends on used font and Character spacing. 

[m1b]

Hi @Kasyan Servetsky, if it would be appropriate, could you post a screenshot of the result? It's an interesting project and I'm curious to see how the final product turned out. No stress if not possible though. 🙂

- Mark

[Kasyan Servetsky]

Hi Mark,

I haven't completed it yet since I have to work on two projects in parallel.

— Kas

[m1b]

Thanks for reply. Of course! there is no hurry for my perspective. 🙂

[Kasyan Servetsky]

Here I just posted the first version of my Leavers hoodie script plus test files and short videos for everyone who is interested. It is still an unfinished project: I'm going to put it on pause since the 2023 campaign is done (without the script 😞 ).

[m1b]

Thanks @Kasyan Servetsky. Cool project!

[MishoStoev]

Hi Kasyan. Me and my friend are trying to make the same type of desing to make hoodies for our teachers. We have found everything exect how to make the names of the students form the year of the graduation (25). Can you help us, we can pay if needed. Also it will be very great if its possible to make in cyrilic, because we are from Bulgaria. Thank you.

[Kasyan Servetsky]

Hi MishoStoev,

The latest version of the script and 'step-by-step' sample files are posted on my site: see the link above.

To create a shape (text frame) just choose a font, type 25, and convert it to outlines. Finally, edit the shape: set the text inset, move nodes with the white arrow, etc.

It should work with Cyrillic: make sure to save the list of names as plain text (Unicode) e.g. in Notepad/TextEdit.

To get the best possible result, you will have to experiment with settings in InDesign, such as font size and leading, and probably fine-tune it manually after running the script.

I can't help you with this because I'm busy with my daily work.

Hope it helps!
— Kasyan