Longer post
I'd like to introduce you my long-term task which I wish to see solved one day.
Let's have two glyphs (any fonts, glyphs, location, transformation), one fixed, one moveable and some (randomly selected) direction. How to find a position of the second glyph where those two glyphs touch?
I'm using manual positioning and it cannot be used for tasks of word cloud magnitude or other optimization tasks (filling a glyph by smaller glyphs like the shapepar package can handle within basic shapes etc.).
I haven't done extensive research on word cloud (also known as tag cloud) methods and algorithms, but my first impression was that the algorithms use bounding box of the words or of the glyphs. But I might be mistaken (I'm), please see this example from Wikipedia. We can clearly see there are words inside letters, so they are using some complex algorithms. This is a fine starting point: http://www.jasondavies.com/wordcloud/about/. More about algorithms.
A note to computer scientists. This task belongs under collision detection (processing images). It has a wide area of use not only in visualization. I enclose a word cloud example and filling (any) space/glyph examples:
Let me illustrate this situation. Let's choose letters a and b from the Latin Modern family, left-right direction, no transformation. We are getting (in this example I'm using \kern):
Update: From mathematical point of view, there might be and often are more solutions when we move the second glyph further to the left. For instance, when we typeset ab in the first example we are getting the second solution:
Let's try another example with some transformation of letter b and direction of 20 degrees (I'm using TikZ for glyph movement):
After finding an intersection point we could move the second glyph backwards to get a certain amount of white space reserve between two glyphs in that direction.
This is one more example, which could be used for two-step optimization. First step would be finding an intersection point and after setting up an anchor we could scale (or we could rotate) the second glyph and we would find next intersection point. It's rather complex example:
What are our options?
I'm using manual transformation (location, rotation, scale) of the second glyph. That's not practical way.
My first (poor) idea was to get a series of raster graphics where I would compute number of non-white pixels. If a number of pixels of letter a and b typeset separately would be the same as number of pixels of both letters typeset together, that would be the proof they are not touching yet. It would be computationally ineffective. Update: When we try to move letters in How the Word Cloud Generator Works, it looks they use rasterization and this technique. They use spiral path to find the best spot for placing the next word. It's possible it isn't that poor idea. It would be an interesting problem at TeX.SX if we are able to raster a vector graphics on-the-fly and process it at the pixel level. I'm thinking of Lua(TeX) and its tools (or TikZ and a new externalization library, perhaps?). I enclose an example from Jason Davies's website. His main website and those examples are inspiring, http://www.jasondavies.com/. Red means the glyphs are not touching, yet, the orange means they are overlapping.
I was hoping that I could turn off kerning and move the second glyph by its left bearing. But that's not enough as we try to consider also glyph transformation.
I started to believe I'm getting closer when I noticed that the glyph consists of Bézier curves which are stored in the font file (PFB, TTF, OTF) in a form of control points. We can get Bézier curves from the font files then.
I enclose a small example from the Metapost manual, see page 50 for further details, where the control points can be seen. The native output format of Metapost is PostScript, we can get SVG and PNG by Metapost or by other conversion tools easily. We could use pstoedit to export the PostScript format to some more vector formats.
We run the following lines:
The content of mal-mpost.mp is this:
Another way would be to use FontForge and export glyphs to a single SVG file or to a series of the SVG files (one file per glyph). Our input would look like this (cut version):
The SVG format is using M for move, L for a straight line and C for Bézier curve. As we can see from the above example to have the control points is not enough for us, we need to reconstruct the Bézier curve(s).
There is a small potential improvement. We could use svg2tikz script to convert it to the TikZ code. The TikZ code would look like this (cut version):
I was thinking that it might be a way. Once we have a series of curves we can find intersection points. I enclose a snippet of what I think might work. That's an intersection of two paths, I've chosen left-right direction. The variable \t in TikZ holds information about number of points (0, 1, 2, ...). When \t=0 that means the paths are not touching, any other value means they are. We can get position of the intersection points, please see the TikZ manual and section about the intersections library, please see pages 139+ or 987+ in the TikZ3 manual.
I'm sure that finding intersection points would be than easy in other programs (Metapost, PSTricks, Asymptote, ...). My idea is to prepare two sets of paths, one set for each glyph, and compare all paths from one set with paths in the second set. In theory, that should assure that we won't miss any intersection point. This will require some experimenting.
LuaTeX is preprocessing font files and store information about glyphs in the Lua file, e.g. please see lmroman10-regular.lua (cut version). We can find bounding box and other information, but not the control points of the Bézier curves. That would increase size of Lua file significantly. We may use FontForge and its native SFD format or we could convert TTF/OTF font files to XML by other tools, e.g. by TTX (tested), or to SVG, e.g. by ttftosvg (http://everythingfonts.com/ttf-to-svg) (untested). We would get the control points but it leaves the glyphs transformation unprocessed.
I enclose the TeX code of the snippets mentioned in the post. We can run xelatex and lualatex engines which can handle loading of the OTF file directly.
My humble proposals
1. True/False
After \checkme{glyphs}{glyphs} we might get:
True, if glyphs have some intersection points. Subquestion: How many we have got?
False, if they don't. Subanswer: We have got 0 intersection points.
2. Distance
After \checkdistance{glyphs}{glyphs}{angle} we might get:
Some dimension, e.g. 2.3cm, which measure minimum distance between those glyphs in that direction.
We should get all the solutions, e.g. when glyphs are inside glyphs, the touching point will be get from the opposite side of the glyphs etc.
We should get warning or \dimenmax if there is no solution and no intersection can be found. The subquestion could be what's the nearest change in angle to get some intersection point.
3. Graphical representation
If the glyphs are already overlapping we should get marks at those points (the intersection points of the Bézier curves).
We might get that overlapping region in different color.
We should get a list of intersection points as a list of coordinates in a log file and/or at the terminal.
The subquestion could be what's the minimum distance (and its angle) to get no intersection points (we would be separating overlapping glyphs).
4. Filling space
How to fill some empty space with a glyph (using location, rotation, and/or scale) to get the biggest glyph.
We should be able to fix some of the parameters, e.g. location, and let the optimization works with other two parameters (rotation, scale).
5. Rasterization
Until now, I have written down some ideas using vector form, but it might be possible to raster our glyphs first and then to do some calculations as algorithms in word/tag clouds do. Outside the TeX we use GhostScript (or some backend tools like ImageMagick or GraphicsMagick) to handle this task.
We might be able to use TikZ and its externalization library to get raster graphics (or shall we use PDF -> Metapost conversion with help of the pstoedit tool, perhaps?), but how to process those pictures on-the-fly? With the help of ImageMagick and \write18, perhaps?