Knuth and Plass line breaking algorithm in JavaScript

http://www.bramstein.com/projects/typeset/flatland/

by apl • 16 years ago

138 42 16 years ago

sfvisser• 16 years ago

I must say this is a very pretty render for a web-based text. Too bad the justification breaks when zooming in/out.

Also, the computation takes a while. Is this a dynamic programming algorithm? Maybe browsers should support this natively.

adolph• 16 years ago

Oh, I was wondering if it was just me. A few lines seem to have hanging right margins. This is probably because my morning lean-back browsing is done at +2 zoom-factor in Safari.

bramstein8• 16 years ago

Zooming is problematic, I haven't quite figured out a reliable way of fixing it yet. The problem is most apparent in Webkit based browsers, Firefox seems to handle it much better (though there are still some small problems--most can be fixed though.)

Yes, this is an application of dynamic programming. The computation is actually quite fast, most of the time is spent in retrieving the text metrics (put each word in a span, retrieve width and move on to the next word.) If that can somehow be alleviated it would become a feasible solution.

I agree with you that browsers should support this natively (Internet Explorer actually does.) If you are interested, I've written a bit on this subject in this Typophile thread: http://typophile.com/node/71247

Groxx2• 16 years ago

I see no hyphens... breaks (eg: lines 3-4), but no markers for them.

edit: wait, they're there when I zoom out a couple levels. Weird.

bramstein8• 16 years ago

That's probably a bug, what browser and operating system are you using?

dchest2• 16 years ago

Same here, Chrome 8.0.552.215, Mac OS X 10.6.5.

Groxx2• 16 years ago

Similar to dchest, though Chrome 9.0.something. Up-to-date dev release.

nixy• 16 years ago

It looks really good in Firefox! However, I just tried printing the page and though it still looks decent, the justification is a lot worse than when rendered on-screen.

bramstein8• 16 years ago

I honestly hadn't thought about printing it out yet. I had a quick look, and I think the issues you are seeing can probably be fixed. My initial plan was to render PDFs server-side, instead of relying on the browser's print mode.

ugh4• 16 years ago

The web is now twenty and browsers are still incapable of something as basic and commonplace as hyphenation and justification. It’s a real shame that this problem has to be solved with JavaScript in 2010.

How old is TeX again?

tumult• 16 years ago

I've been asking for years why browsers do not have this. The only reply I've gotten is for performance considerations, which is a bad answer for several reasons.

bramstein8• 16 years ago

Internet Explorer actually has this through the (almost standardized) text-justify CSS property. It still doesn't do hyphenation, but Hyphenator.js (http://code.google.com/p/hyphenator/) fills that gap pretty nicely.

Performance isn't a good argument in my opinion. The algorithm isn't that expensive. The most expensive part right now is retrieving all the text metrics, but you would get that a lot cheaper in the browsers rendering engine.

I briefly looked at hacking it into Webkit, but then gave up due to a lack of time.

lhorie2• 16 years ago

Another reason I've heard before was internationalization. Not sure how many languages have draconian hyphenation rules like English though.

sjs• 16 years ago

It sounds like a difficult thing to do correctly for any given language. I'd probably procrastinate it too.

eegilbert2• 16 years ago

It's not only browsers. Look at Word, for god's sake.

ugh4• 16 years ago

Even hyphenation like in Word would be an improvement over the status quo.

eegilbert2• 16 years ago

This is beautiful. Fantastic work. Now, I'd love to see someone work this into WebKit or Gecko's core.

NathanKP• 16 years ago

Does anyone know if there is a good jQuery plugin for this, or do I need to take the code from this demo and make my own plugin?

bramstein8• 16 years ago

As far as I know, this is the only implementation in JavaScript. It might be possible to turn this into a jQuery plugin at some point, but there are probably quite a couple of bugfixes and changes needed to turn this from a tech demo into a drop-in plugin.

metageek• 16 years ago

For those who don't know the algorithm, here's a bunch of links about it in Wikipedia:

http://en.wikipedia.org/wiki/Word_wrap#Knuth.27s_algorithm

bramstein8• 16 years ago

I would also highly recommend "Digital Typography" by Knuth. It contains a more detailed description of the algorithm as well as many interesting historical and technical chapters on TeX, MetaFont and computer typesetting in general.

bhickey• 16 years ago

At the default zoom on my G1, the results are poor. Pull back a bit and everything looks swell.

elblanco• 16 years ago

Great work! The output is beautiful. Looking forward to this being a standard library in the future. Do you know how well it might handle cases of text that already has some formatting?

Also: It blows up in IE9 for me though, many of the lines go on for quite a ways.

tomkinstinch• 16 years ago

Looks great, but it would be nice if the hyphens were removed when copying text.

bodhi• 16 years ago

Looks very nice. The only annoying thing I can see is that copying the text ends up with word-breaks in the hyphenated words.

leif• 16 years ago

I recall the first interesting example usage my professor taught of dynamic programming was this example (well, described, not taught). He basically just said that all you do is take the L^2 or L^3 sum of extra space and minimize it using a DP. The fact that that yields great-looking text I thought was pretty cool.

Knuth and Plass line breaking algorithm in JavaScript

Related Stories