file

很明顯地,BPS 最核心的程式都跟圖形界面區域裡面發生的事情有關。可想而知地,這個區域是用 <canvas> 元件畫出來的;該元件可以說是 HTML5 最強大的發明、沒有之一,因為正是這個能允許網頁繪製出任何東西的能力、使得它可以被用來製作任何類型的應用程式。

跟 canvas 有關的主題、即便侷限在 BPS 之上都仍舊太過龐大,所以這篇文章中我先從一個我最近解決的排版計算難題開始講起。這個問題,簡單來說就是「在排版的過程中發現一些條件出現了循環相依」的時候要怎麼辦。

問題

我先精簡地說明一下 BPS 的主要視圖區(即偏左下角的最大一塊白色底色區域)裡面畫了些什麼。BPS 因為是用來輔助摺紙設計,所以它的編輯對象就是一張紙(通常是正方形的,即粗黑框的區域),而紙張上可以讓設計者安排各種元件的分佈。紙張具有寬度和高度的設定,分別都是 8 以上的整數,而元件則是分佈在對應的格子之上。

這些元件之中,有些會帶有文字標籤以方便識別。雖然我個人並不建議用太長的文字,但是在規格上、BPS 是允許使用者在文字標籤中使用任意長度的字串的。

BPS 的視圖區域是以一個相對的「縮放」概念來決定顯示大小的,預設的縮放是 100%,也就是要恰好顯示出全部的東西(包括文字標籤在內)。然而,這是對使用者來說是如此,而對 BPS 內部來說,基於繪製上的需要,必須採用絕對的「尺度」來計算繪製的位置,其定義就是「紙張每一個格子實際上是多少(浮點數,底下以 s 表示)的像素」而言。BPS 在內部會把「縮放」的相對概念、根據當前視圖區域的大小來換算成「尺度」的絕對概念,然後再根據尺度進行實際的繪製動作。

然而,因為「100% 的縮放」如我剛才所說的,指的是恰好顯示出包括文字標籤在內的全部東西而言,也就是說「它實際上對應的尺度為何」這件事不光只是相依於「紙張的寬度高度設定」,同時也相依於「哪些元件有文字標籤、以及其中的字串有多長」這件事。這是第一個重點。

再來,文字標籤的字體大小一般來說是固定的:就是 14px 那麼大(這邊的 px 指的是 CSS 像素而非裝置像素,以提供一致的使用體驗)。不過這邊有個例外是當當前的顯示尺度實在太小了的時候;如果尺度小於 10px,那麼文字標籤很容易擠成一團,看起來並不舒服,所以我規定如果尺度 s<10 的話,那麼就要稍微把字體也縮小一點。我曾經試過線性的縮放(亦即使用字體大小 =14\times (s/10)),但是我發現這樣做的話字體又很容易小過頭了,經過實驗之後我發現採用 14\times\sqrt{s/10} 這樣的大小是最舒服的。總之簡單來說,「文字標籤的大小」相依於「尺度」。

結果我們就發現不對勁了:

  • 「尺度」相依於:當前縮放設定、視圖區域大小、紙張寬度高度、文字標籤的分佈與大小。
  • 「文字標籤的大小」相依於:文字標籤的字串內容、字體大小。
  • 「字體大小」相依於:尺度。

這樣一來就出現了「尺度 → 文字標籤大小 → 字體大小 → 尺度」的循環相依,也就是說我根本沒有一個起點可以去計算它們(要計算其中任何一個,我都必須先計算出另外一個的值,而這又要再先計算另外一個的值……如此無窮循環)。這麼一來怎麼辦?

寫出方程組

從數學上的角度來看,任何這種有若干個變數彼此以不同條件相依的結構,其實就是一個由這些變數所形成的聯立方程組(其中的方程式從簡單的線性方程、到複雜的非多項式條件方程都有可能),而聯立方程組的解答就會是我們要的排版方案。因此解決原本的排版問題的不同演算法,其實都可以對應到數學上的某種解決聯立方程組的技巧。

為了簡化問題的描述,我們可以先考慮只有一個文字標籤的情況、去計算出這種情況下適合的尺度;而當畫面上有多個文字標籤的時候,我們只要取個別文字標籤對應的尺度中的最小值,就可以保證畫面上能容納下所有的文字標籤了。

除此之外,也是簡單起見,底下也假設文字標籤的左端緊靠著紙張範圍的最右邊(一般的情況只是再多增加一些參數,但是解法都類似)。基於對稱性,我會希望當紙張的右邊保留了多少距離給文字標籤的時候、左邊也一樣要保留同樣的距離。所以在這些假設之下,我們可以列出如下的方程組:

\begin{aligned}
    v & = ws+2tf \\
    f & = \begin{cases}
        \sqrt{s/10}, & s<10\\
        1, & s\ge 10
    \end{cases}
\end{aligned}

其中 v 是縮放之後的視圖區域寬度(即視圖區域寬度乘以使用者指定的縮放百分比,方便起見用單一變數表示),w 是紙張的寬度,t 是文字標籤的參考寬度,f 是字體相對大小。除了 fs 之外,其它的幾個變數都是常數。

或問:這個文字標籤的參考寬度 t 是怎麼得到的?它當然並不是「去看文字標籤的字串內容有幾個字元來計算」那麼簡單,因為我們輸出到畫面的時候採用的並不是等寬字型,沒辦法那麼簡單計算。幸好,canvas 元件提供了 measureText() 方法可以讓我們取得文字輸出到畫面上的寬度;每次當文字標籤的內容改變的時候,我們可以先設定字體大小為 14、用這個方法預先測量結果的寬度、儲存成上述的常數 t,解完方程式之後再用真正的大小(14f)去繪製文字。1

解方程組

那麼上面的方程組要怎麼解呢?先考慮 s \ge 10 的情況。此時代入 f 會得到 v=ws+2t,因此解得 s=(v-2t)/w,而這只有在右式真的大於等於 10 的時候才成立。

再來考慮 s<10 的情況。此時代入 f 會得到

\tag{1} v=ws+\frac{2t}{\sqrt{10}}\sqrt{s}\text{,}

移項然後兩邊平方之後會得到

(v-ws)^2=\frac{4t^2}{10}s\text{,}

整理之後得到

w^2s^2-\left(2vw+(2/5)t^2\right)s+v^2=0\text{,}

這對 s 來說是一個二次方程,套用公式可知其解為

\displaystyle
s=\frac{2vw+(2/5)t^2\pm \sqrt{(2vw+(2/5)t^2)^2-4w^2v^2}}{2w^2}\text{。}

但是必須小心,因為前面的步驟中我們曾經把方程式兩邊同時取平方,這會導致根的增加;這個解裡面只有當正負號取負號的時候才是我們原本方程式 (1) 的解(另外一個根是 v=ws-\frac{2t}{\sqrt 10}\sqrt s 的解)。所以再加以化簡並整理起來之後,我們就得到:

s=\begin{cases}
    (v-2t)/w, & (v-2t)/w\ge 10 \\
    \displaystyle\frac{5vw+t^2- t\sqrt{t^2+10vw}}{5w^2}, & (v-2t)/w\le 10
\end{cases}

而可以驗證,當 (v-2t)/w=10 的時候,第二列的算式確實也是等於 10 2,所以這兩列相容且合起來給出了 s 的一個連續函數。有了 s 之後,我們的循環相依問題也就跟著解決了,因為其它的數值就可以從它開始來推算了。

順便一提,上面的推導過程我們是代入 f 去解 s,而各位也可以反過來代入 s 來先解 f,最後會得到一樣的答案;過程中需要注意的重點一樣,其中「等式兩側同取平方導致增根」的問題可能會比較上面的解法中要容易處理,但是反過來分段定義的處理就可能比較需要轉一下腦筋了。

更一般的情況

是否覺得這些數學看上去有點頭昏眼花?其實說真的這個例子已經算是比較幸運的了,因為這邊出現的方程組是可以用代數方法來求解的,所以其實從頭到尾我們都只有用到(稍微難一點的)國中數學就把問題解決了,根本不需要用到什麼演算法。但是,更一般的排版問題有可能會比這個要複雜上很多倍,以至於根本無法以代數方法求解,或者即便可以、解起來也太過於艱難而不切實際。這種時候,一些數值解的演算法就可以派上用場了。這個主題很深,我底下點到為止就好。

先假設我們完全忘記二次方程要怎麼解了。我們可以把 (1) 改寫成:

\tag{2} s=\frac{1}{w}\left(v-\frac{2t}{\sqrt{10}}\sqrt{s}\right),

然後我們來做個實驗吧。我們先取一些具體的數字,例如 w=64t=40v=400 好了。然後我們先隨便猜一個 s,例如 10 好了,然後我們就把 s 代入到 (2) 式的右邊,再把得到的結果再次代入……如此反覆操作。如果各位實際試試,則前十次迭代的數字會是這樣的:

\begin{align*}
& 5\\
& 5.366116523516816\\
& 5.334327729589073\\
& 5.3370439727192265\\
& 5.336811563401409\\
& 5.336831446675111\\
& 5.33682974558794\\
& 5.336829891122078\\
& 5.336829878671107\\
& 5.3368298797363325\\
\end{align*}

各位會發現這個收斂得還滿快的,迭代到第五次就已經精確到小數點第四位,對於我們的應用來說已經足夠了。這樣的操作是所謂的「固定點迭代」演算法的一種特例;各位可以試著從別的數字開始看看,讀者將會發現,只要一開始的數字不要太離譜,迭代幾次之後都會收斂到 5.3368... 附近。

那麼是不是只要我們能夠把方程式改寫成 x=f(x) 的形式、隨便猜一個不要差太多的數字去反覆迭代就能逼近答案?當然天底下也沒有那麼好的事啦,比方說 (1) 的另外一種改寫法會是:

s=\frac{5(v-ws)^2}{2t^2}

注意到這個的右式恰好是 (2) 的右式的反函數,所以既然 (2) 的右式迭代之後會收斂,那麼這個就是恰好反過來、迭代之後會發散了。

那麼一般來說怎樣把方程式改寫成 x=f(x) 的形式才是可行的?關鍵在於函數的微分絕對值 \left|f'(x)\right| 必須要小於 1(此時它的反函數的微分絕對值就會是大於 1 的,所以不行)。就算讀者不懂微積分也沒關係,實際實驗看看自然就知道哪一種寫法會收斂了。

對於數學背景較好的讀者,可以去了解效率更好的 Newton-Raphson 法等等的數值方法,以及它們的高維度版本(以對付沒有辦法化簡成單一變數方程的方程組),這邊基於篇幅與讀者設定,我就不解釋那麼多了。


  1. 值得注意的是,在 canvas 上繪製文字的時候,實際繪製出來的大小不會 100% 跟字體大小是成正比的,而會因為反鋸齒和字距微調等等的內部優化而導致很細微的差異。不過這基本上並不影響排版的正確性,所以可以直接假設繪製大小跟字體大小成正比來計算排版。 

  2. 最簡單的驗證方法是直接把 w=(v-2t)/10 代入一開始的 (1) 當中,並且直接驗證 s=10 確實就是其解。由於方程式 (1) 只有一個根,因此我們導出的複雜算式此時必然也等於 10。 


分享此頁至:
最後修改日期: 2021/06/25

留言

撰寫回覆或留言

發佈留言必須填寫的電子郵件地址不會公開。