Алгоритм переноса строк: жадный подход

Question

Мне был нужен простой алгоритм переноса строк, поэтому я обратился к Википедии:

http://en.wikipedia.org/wiki/Line_wrap_and_word_wrap

Жадный алгоритм:

1. | SpaceLeft: = LineWidth
2. | для каждого слова в тексте
3. |      if (Width(Word) + SpaceWidth) > SpaceLeft
4. | вставить разрыв строки перед словом в тексте
5. |         SpaceLeft:= LineWidth - Width(Word)
6. | еще
7. |         SpaceLeft:= SpaceLeft - (Width(Word) + SpaceWidth)

В строке № 5, когда мы начинаем новую строку и вычитаем ширину слова из доступной ширины, не должны ли мы также вычесть ширину пробела?

5. | SpaceLeft: = LineWidth - (Width (Word) + SpaceWidth)

Почему ширина строки не учитывается в строке № 5?

-- ОБНОВИТЬ --

Некоторое простое тестирование.

В каждом из изображений первый абзац создается с помощью JavaScript с использованием описанного выше алгоритма обтекания (оранжевая линия), а второй абзац отображается в браузере в естественной форме (синий контур).

Интересно, что этот чрезвычайно простой алгоритм действительно дает те же результаты, что и в браузере, для текста без краевых случаев.

Это первое изображение показывает, что когда мы используем

SpaceLeft := LineWidth - Width(Word)

Рендеринг JS и рендеринг в браузере абсолютно одинаковы.

Но следующие изображения (с разной шириной линии) показывают тонкие различия между визуализацией JS и браузера при использовании:

SpaceLeft := LineWidth - (Width(Word) + SpaceWidth)

Код

// функция getWidth () использует canvas для вычисления ширины
// http://stackru.com/questions/118241/calculate-text-width-with-javascript

var wrap = function(container, text, lineWidth) {
        var words = text.split(' ');
        var w, x, i, l;
        var spaceWidth = getWidth(' ');
        var spaceLeft = lineWidth;

        var arr = [], line = [];
        arr.push(линия);

        для ( i = 0, l = words.length; i  spaceLeft) {
                линия = [];
                arr.push (линия);
                line.push (ш);

                // это случай для алгоритма Википедии
                // spaceLeft = lineWidth - getWidth(w);

                spaceLeft = lineWidth - x;
            }
            еще {
                spaceLeft = spaceLeft - x;
                line.push(ш);
            }
        }

        для (i = 0, l = длина строки; i '). text (arr [i].join ('')));
        }
    };

Answer 1

Алгоритм, вероятно, будет "более" правильным, если строка 5

5. |         SpaceLeft := LineWidth - (Width(Word) + SpaceWidth)

как вы предлагаете.

В любом случае, вопрос немного философский, так как алгоритм слишком упрощен для любой конкретной реализации, учитывая, что реальная реализация должна учитывать тот факт, что текст может уже содержать новые строки, что слова не обязательно разделяются пробелами (например, дефисами) и / или множественными пробелами.

Использование существующей реализации, вероятно, является наилучшим решением, например, для Java: перенос строки после количества символов в слова в Java