换行文本算法(换行文本以适应 'page' )

Question

我开发了一些面向 GUI 的应用程序，它们实现了自己的文本换行算法。例如，考虑一下我的应用程序由典型的 GUI“小部件”组成，这些小部件可以布置在屏幕上。诸如复选框、文本字段、简单标签等小部件非常容易绘制。然而，诸如“段落”(任意数量的多行文本，应适合指定的框，必要时会发生换行)之类的小部件要困难得多，因为好吧，换行部分。

每次我实现这样的算法时，我都使用了一种有效但效率很低的方法。我的一般方法(将字符串装入宽度为 w 的框)是迭代地获取字符串 s，使用字体度量来测量其像素长度 l，并逐渐减少直到 l <= w。然后将余数分配给 s，我重复该过程，直到剩下值 s> 小于或等于 w。

底部是一个 Javascript 示例(不可否认，这可能不是执行此类操作的最佳环境)。此代码将成为上述“段落”小部件的一部分，并且是为 HTML5 Canvas API 编写的(ctx 是 Canvas 的图形上下文)。显然，这种方法的 Big-O 分析非常糟糕。但是......有没有更好的方法来做这种事情？我假设这在某种程度上取决于我们工作的环境。但我还假设，考虑到现有的文本编辑工具的数量，存在一个有效的解决方案。

    // the paragraph widgets' main drawing function
    this.drawText = function(ctx) {
        ... 

        var lines = this.text.split("\n"); // here we account for user-entered line breaks
        var y = this.y;

        for (var i=0; i<lines.length; i++) {
            var currTxt = lines[i]; // a chunk of text in between user-entered line breaks
            var miniLines = this.breakToLines(currTxt, this.textWidth(), ctx);
            for (var j = 0; j < miniLines.length; j++) {
                var miniTxt = miniLines[j];

                var x = this.x + ( (this.round) ? this.cornerRadius : 0 );

                x += this.textOffset();
                y += this.fontSize;

                ctx.save();
                ctx.rect(this.x, this.y, this.width, this.height);
                ctx.clip();

                ctx.fillText(miniTxt, x, y);
                ctx.restore();
            }

        };
    };

    // take a chunk of text and break it into lines that fit within width 'w'
    this.breakToLines = function(txt, w, ctx) {
        var arr = [];
        while (true) {
            var txt2 = this.popLine(txt, w, ctx);
            if (txt2 == null)
                break;
            arr.push(txt2);
            if (txt.length <= txt2.length)
                break;
            txt = txt.substring(txt2.length);
        }
        return arr;
    };

    this.popLine = function(txt, w, ctx) {
        var m = ctx.measureText(txt); // 'm' represents the size of the text
        if (m.length == 0)
            return null;  // 'm' is empty, so we're done
        while (m.width > w) {
            // remove a word from txt and re-measure it
            txt = txt.substring(0, txt.lastIndexOf(' '));
            m = ctx.measureText(txt);
        }
        return txt;
    };

Answer 1

我想知道文本指标在测量单词后跟空格的大小时是否会给出可靠的结果。例如，是否 width( "aaa ") + width( "bbb") = width( "aaa bbb")？如果是这样，你可以测量文本中的每个单词，后面有没有空格，然后从那里算出其余的。 B 计划(假设一个单词后跟一个空格的文本度量不能给出精确的结果)是测量没有空格的每个单词，并使用一个固定值来估计单词之间的空格。

在我看来，当前算法的低效率在于您调用了 measureText 方法 O(n^2) 次，并且您测量长弦的宽度。通过将文本分解为单词并测量每个单词，您只需调用 measureText O(n) 次，并且您将在相对较短的字符串上调用它。

建议的算法是从每行的开头开始添加单词，直到达到换行限制。这种解决问题的附加方法减少了必须测量的字符串的数量，并减少了必须测量的字符串的长度。