Re: [csswg-drafts] [css-text-4] Suggest algorithm for multi-line

An algorithm i've used in the past is
1. put as much text as will fit on the line as possible, using a preferred (not minimum) space between words;
2. if the line is tighter (less space left over) than the previous line, move the first word or word fragment on this line back to the end of the previous line, as long as that won't make the spaces on the previous line smaller than than the minimum or the spaces on this line larger than the maximum.
Generalizing this to n lines brings an incremental improvement at the cost of not being able to render until you've got n lines; i've usually stuck with n being 2 or 3, but i've heard of systems going as high as nine. Note that as long as you only ever move words backwards, the algorithm is stable and is much faster than Knuth-Plass.
It does assume a model of absolute-min/preferred/max-preferred word spaces. Two further refinements seen in many for-paper systems is (1) an option to use the preferred space and set the line unjustified if the word space exeeds the maximium, and (2) semi-justiication, in which you only justify lines whose length with preferred space is within a set distance (usually 25%) of the line length (and where doing so doesn't exceed the max preferred space) and others are set unjustified (e.g. left-aligned, or right-aligned for Hebrew, or whatever). Again, these two options work fine with an n-line window.

The Knuth-Plass algorithm tends to have some nasty edge cases (e.g. when TeX says "overfull hbox" at you) making it less than ideal for formatting where the author isn't reviewing the results. E.g. sometimes it decides to put only two words or word fragments on a line, one at each end with a huge gap, rather than have several hyphens in a row. It's also NP-complete in performance (on the number of potential word fragements after hyphenation in th paragraph). where the "move lumps back" compromise is either linear or at worst n^2 if you do it recursively, with n being the number of lines.

-- 
GitHub Notification of comment by liamquin
Please view or discuss this issue at https://github.com/w3c/csswg-drafts/issues/803#issuecomment-379852231 using your GitHub account

Received on Monday, 9 April 2018 18:40:08 UTC