Take the 2-minute tour ×
TeX - LaTeX Stack Exchange is a question and answer site for users of TeX, LaTeX, ConTeXt, and related typesetting systems. It's 100% free, no registration required.

This question led to a new feature in a package:
impnattypo

The following quote is from James Felici, The Complete Manual of Typography (2003), p. 161:

Rivers occur when word spaces stack one above the other in successive lines of type, creating the appearance of fissures running through the text [...]. Rivers are accidents of composition, and software isn't yet smart enough to detect them, much less do anything about them.

On the following page, Felici shows an example of a "mighty river" running through a paragraph. Below, you'll find the LaTeX code and the pictured output of my (somewhat abridged) recreation of Felicis example. (The layout is chosen so that the effect also occurs if one uses the microtype package with its default settings.)

\documentclass{article}

\usepackage{mathptmx}
\usepackage{microtype}

\textwidth 247pt
\parindent 23pt
\frenchspacing

\begin{document}

Though the Pearl measures less than 50~miles in total length from its
modest source as a cool mountain spring to the screaming cascades and
steaming estuary of its downstream reaches, over those miles, the
river has in one place or another everything you could possibly ask
for. You can roam among lush temperate rain forests, turgid white
water canyons, contemplative meanders among aisles of staid aspens
(with trout leaping to slurp all the afternoon insects from its calm
surface), and forbidding swamp land as formidable as any that Humphrey
Bogart muddled through in \emph{The African Queen}.

\end{document}

alt text

So, was Felici right that "software isn't yet smart enough" to deal with rivers? Or is this something TeX can handle? And if not TeX, then possibly LuaTeX?

EDIT: As rassie pointed out that TeX is Turing-complete, let me clarify that I'm interested in solutions that either already exist or could be implemented with reasonable time and effort.

share|improve this question
3  
For what it's worth, osdir.com/ml/tex.context/2001-01/msg00057.html is a nice overview of some ideas. –  Pieter Oct 24 '10 at 17:14
5  
Also, FYI: you don't need all those %s. Consecutive white space is treated as a single space, unless it's two newlines in a row. –  Antal S-Z Oct 24 '10 at 19:18
9  
What a lovely example of a "river" in a text block. But I should note that even though I knew what to look for, the river didn't jump out at me for some time. I think the slight meandering of the spaces helps minimize the visual problems. I see rivers in fixed-width fonts more commonly than variable-width. (For instance I see one covering the first three lines of this text box, though I imagine it will be gone in the published comment.) –  Jon Ericson Jun 6 '11 at 23:11
    
@Jon: If you like it, upvote it. ;-) –  lockstep Jun 6 '11 at 23:14
1  
@Jens In the screenshot, there's a continuous line of whitespace from the first to the last line (starting to the right of "measures" and ending to the right of "through"). –  lockstep Jul 23 at 18:39

5 Answers 5

up vote 39 down vote accepted

I have added a first version of an algorithm to detect rivers using Lua to the impnattypo package on github. To use it, simply use the rivers option:

\usepackage[draft,rivers]{impnattypo}

Here is an example result:

rivers in lipsum

Beware that there might still be some bugs ;-)

share|improve this answer

I am not sure if the problem is solvable, and it may require a new generation of very fast computers (trials with different algorithms can take over six hours to iterate). The example below can produce rivers mightier than Felici's example.

\documentclass[11pt]{article} 
\begin{document}


\def\samplerivers{%
\hskip1em Repeated repeated repeated repeated
repeated repeated repeated repeated
repeated repeated repeated repeated
repeated repeated repeated repeated
repeated repeated repeated repeated
repeated repeated repeated repeated
repeated repeated repeated repeated
repeated repeated repeated repeated
repeated repeated repeated repeated
repeated repeated repeated repeated
repeated repeated repeated repeated
repeated repeated repeated repeated
repeated.}


\begin{minipage}{1.9in}
 \looseness=-1 \hyphenpenalty=0\samplerivers
\end{minipage}\hspace{.8cm}
\begin{minipage}{1.9in}
  \hyphenpenalty=100\samplerivers
\end{minipage}\hspace{.8cm}
\begin{minipage}{1.9in}
 \hyphenpenalty=100000 \samplerivers
\end{minipage}

\end{document}

One attempt at attacking the problem is that of Holkner. He attempted to optimize over multiple objectives but as he writes:

... performance degrades so badly that some of the tests had to be stopped when they took more than six hours to complete.

TeX's algorithm does not include for any parameters to minimize rivers.

share|improve this answer
    
Many thanks for the link - I've already started reading. –  lockstep Oct 24 '10 at 19:23

To expand a little on the answers already given: It is not merely a question of adding a new sort of penalty and having TeX magically optimize for the new penalty. The problem is that TeX's paragraph optimization algorithm utilizes the special structure of the problem given it: The problem is rephrased as a shortest path algorithm in a graph (whose nodes are the possible break points) and solved with Dijkstra's algorithm. Any new sort of penalty would have to fit into that framework, and a river penalty would in a sense be “too global” for that.

River detection, on the other hand, ought to be feasible. If we had a way of detecting rivers, it would be possible to tweak the offending paragraph manually to make the river go away.

share|improve this answer
4  
If river detection is possible, then why not consider nearby configurations of offending paragraphs? These nearby configurations can be found by keeping a heap of the "second-best" paths that were not taken by Dijkstra's algorithm and going "back in time" and trying those. (And when you try them you augment your heap of second-best paths.) This would add a linear factor to the run time equal to the number of alternate configurations you want to explore. –  Neil G Nov 1 '10 at 7:26
1  
@Neil G: Interesting thought. While it might not be feasible to find an optimal solution that way, perhaps it is at least possible to get something better. Maybe someone could give it to a student as a thesis problem … –  Harald Hanche-Olsen Nov 1 '10 at 7:37
    
@Harald: Raphink's answer has surpassed your answer. –  lockstep Sep 21 '11 at 14:58

Might not be a very helpful answer, but ANT (which is modelled after TeX) claims to have river detection, so may be some one could look at that and implement it in lua (Hans in a recent talk mentioned his effort to rewrite TeX paragraph builder in lua, so may be both can be combined.)

share|improve this answer
4  
I've tried to get ANT to avoid rivers, but never got any satisfying results, even the author of ANT couldn't help me. –  topskip Oct 24 '10 at 19:36
    
@Patrick: Didn't you do some experiments on avoiding rivers in plain luatex? –  Aditya Oct 24 '10 at 20:50
3  
@Aditya: Not LuaTeX, but I implemented my own Knuth & Plass total-fit line breaking algorithm and made experiments with that. Detecting rivers wasn't hard, but I have not found a good way to eliminate them (time complexity is a killer here). –  topskip Oct 25 '10 at 17:58

I think it's more of an algorithm problem than TeX's. Both TeX and Lua are Turing-complete programming languages, so it's possible to implement any algorithm in it provided enough time.

So let's assume you've got an algorithm which can tell whether a paragraph of text has a river inside it or not, e.g. by graphically putting vertical lines over the paragraph and checking whether all dots underneath are white. Then one could define a \riverpenalty variable bound to the output of that algorithm, which would, if set high enough, force TeX to select an another rendering of that particular paragraph.

However, if I'm not completely mistaken, classic TeX first builds lines and then paragraphs, i.e. a paragraph-bound penalty would not lead to a different rendering for a particular line. That would mean that river detection would be possible with classic TeX but not river correction.

On the other hand, many of PDFTeX's and XeTeX's algorithms, especially those dealing with microtypography, probably need ways to correct a line's rendering based on some paragraph penalty. In that case, implementing a river correction should be possible with one of those advanced engines, either in the engine itself or using its API -- and at that point it doesn't matter which language you take, either pure TeX or Lua or something completely different.

share|improve this answer
    
@rassie: Thanks for reminding me that TeX is Turing-complete. I've edited my question to clarify that I'm interested in solutions existing in the here and now, so to speak. ;-) –  lockstep Oct 24 '10 at 16:41
10  
"classic TeX first builds lines and then paragraphs" — you're either mistaken on this point or you've just worded this sentence poorly; the line breaks are chosen while taking the entire paragraph into account. –  Will Robertson Oct 25 '10 at 8:13
    
@Will: I'm far from TeXpert and you are probably right on that one -- on second thinking, it's pretty obvious that line-breaking can't actually be done without taking the paragraph into account. Gotta re-read TeXbook again :) –  Nikolai Prokoschenko Oct 25 '10 at 17:39
5  
@rassie: There's one more thing in your answer that is not quite OK: TeX being Turing complete doesn't necessarily help; you just can't check "whether all dots underneath [a vertical line] are white". TeX only sees the bounding boxes of the characters, not the characters itself. For this problem, the bounding boxes should be a close enough approximation, but for others it's a great obstacle. Here's an example where Turing completeness of TeX doesn't seem to help. –  Hendrik Vogt Oct 27 '10 at 9:50
3  
@rassie: It was clear to me that you wrote your answer before lockstep's edit. But my point was that Turing completeness does not imply "that the problem is generally solvable". There are obstacles that you just can't overcome! –  Hendrik Vogt Oct 27 '10 at 14:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.