[HN Gopher] Knuth-Plass Thoughts
___________________________________________________________________
Knuth-Plass Thoughts
Author : creata
Score : 71 points
Date : 2023-02-07 05:48 UTC (1 days ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| ysleepy wrote:
| The second example breaking has a long river.
|
| https://en.wikipedia.org/wiki/River_(typography)
|
| I love typography rabbit holes.
| bloak wrote:
| There's no mention of widows or orphans on that page. But
| presumably the Knuth-Plass algorithm is aware of those and take
| them into account when breaking lines?
|
| One thing I've often wondered is whether these algorithms treat a
| page break from even to odd differently from a page break from
| odd to even: it could make sense to do so, I think, in the case
| of an ordinary book, particularly when it comes to placing an
| illustration or table, but perhaps also for widows and orphans.
| thechao wrote:
| It's been a while since I wrote this, but I seem to remember
| that widows are NP-hard _at least_ : fitting them to pages maps
| onto box-packing.
|
| I really implemented this algorithm so that I could nicely
| "flow" images in a GUI window. I was working with Sean Parent &
| Jaakko Jarvi on Adam/Eve. My assertion was that there were
| layout principles (Adam?) for UI similar to the constraint
| properties for the object model (Eve?). The "other" layout
| principle was the grid-bag (CSS's box model for grids).
| dhosek wrote:
| One thought that was proposed back in the 80s was that just as
| line breaks are considered in the paragraph as a whole, page
| breaks could be considered in the document as a whole (TeX
| can't do this--easily--being Turing complete, in _theory_ it
| can do anything computable, but the speed would be atrocious).
| This could be managed by doing things like lengthening or
| shortening pairs of facing pages by a line or trying to tighten
| or loosen an individual paragraph to change the number of lines
| in it. A document formatter which comes at page breaks with the
| right level of abstraction of the data would be able to manage
| this with minimal or no human intervention (when I was
| typesetting _Serif_ magazine with TeX in the 90s, I just went
| through and fixed page breaks manually which is a typical
| modern workflow as well).
| gjm11 wrote:
| TeX treats the problems of (1) choosing line breaks to turn a
| stream of words into a stream of lines, and (2) choosing page
| breaks to turn a stream of lines into a stream of pages,
| separately; it does #1 and then #2. The Knuth-Plass algorithms
| addresses #1. I think #2 is done by simpler means; there is
| some support in it for penalizing widow and orphan lines, but
| no way for that to feed back to the line-breaking process.
|
| In the common case where your pages are just text with a fixed
| spacing between lines, the only way for #2 to prevent widows
| and orphans is to make the page one line taller or shorter,
| making the margins look weird, which typically _also_ gets
| penalized, and the only question is which penalty is larger.
| But if there are any variable spacings on the page, there will
| be the option of making them slightly larger or smaller in
| order to push a stray line from one page to another.
| bloak wrote:
| Thanks for the interesting replies to my question.
|
| It sounds as though TeX cannot do anything about widows and
| orphans in the boring "simple" case of a long prose text with a
| fixed number of lines per page, because the only way[ _] to
| improve page breaks in that case would be to change the line
| breaks, which have already been decided. Mixing up the line-
| break and page-break stages presumably gives you an NP-hard
| optimisation problem, and perhaps Knuth was less interested in
| working on messy heuristic algorithms.
|
| I've just found a couple of references to work in this area:
|
| https://mirrors.mit.edu/CTAN/macros/luatex/generic/lua-widow...
|
| https://onlinelibrary.wiley.com/doi/10.1111/coin.12165
|
| --------
|
| [_] I'm assuming that moving the margins or changing the line
| spacing would be unacceptable because it would make the pages
| of a book look obviously different from each other. So it turns
| out that the "simple" case is in some ways harder to handle
| than the "complex" case in which there are figures and
| footnotes and so on.
| Someone wrote:
| There's a similar problem with paragraphs ending with a very
| short line. IIRC, nothing special needs to be done about that
| because the squaring in the formula of the penalty makes the
| penalty of such a line very high.
|
| If so, nothing special needs to be done about widows and
| orphans either because TeX first uses essentially the same
| algorithm to decide where to put page breaks between lines
| (with page breaks between paragraphs getting lower penalties
| than page breaks within paragraphs), and having a single line
| of a paragraph on the top or bottom of a page leads to a fairly
| high penalty.
| raphlinus wrote:
| The standard TeX algorithm doesn't penalize the length of the
| last line, so doesn't solve this. The implementation in
| Android, based on Minikin[1], applies _some_ penalty to the
| last line by default, as it 's especially unpleasant on
| mobile. It also has a "balanced" setting[2] which applies the
| full penalty, as that's often more aesthetically pleasing in
| UI contexts, though it would not be a good choice for a
| running text, as it would result in paragraphs of uneven
| width.
|
| [1]: https://raphlinus.github.io/text/2022/11/08/minikin.html
|
| [2]: https://developer.android.com/reference/android/widget/T
| extV...
| a_e_k wrote:
| Last month, I submitted a patch to GNU Emacs with an
| implementation of line breaking inspired by Knuth-Plass and
| an option to enable it for paragraph filling. (I'm still
| iterating on the patch.)
|
| My approach to runts was to apply the full penalty to the
| last line, but only if the number of words was below a
| threshold (by default, only if it's a single word).
___________________________________________________________________
(page generated 2023-02-08 23:02 UTC)