一、動機
假設平面上有一個以格子點為頂點之凸多邊形, 則其面積為 $$ \frac{a}{2} + b - 1 $$ 其中 $a$ 為多邊形邊界上的格子點數, $b$ 為多邊形內部的格子點數。 上式就是著名的 Pick 公式, 由 Georg Alexander Pick (1859$-$1943) 於 1899 年首度提出。 關於 Pick 公式的論述與證明請見蔡聰明 (1994) 與楊惠后 (2007)。 我們用下例說明 Pick 公式的計算過程, 在圖一中有一個五邊形, $\bullet$ 點處代表頂點位置, 其邊界上共通過 6 個格子點, 內部包含 5 個格子點, Pick 公式告訴我們此五邊形的面積為 $$ \frac{6}{2} + 5 - 1 = 7 $$
由上例可知 Pick 公式是一個相當簡易的計算面積方法。 然而, 在使用Pick公式時, 通常是先以「目測」的方式逐點數出多邊形邊界上與內部所含的格子點數, 若是格線的繪製不精確, 則會造成格子點數的計算錯誤; 另一方面, 若格線的數目過多時, 計算格子點數也是很不輕鬆的方式。 為了讓使用者在使用 Pick 公式時沒有上述的困擾, 本文將引進一個新概念---「縮圖」, 透過縮圖的資訊讓使用者可以利用 Pick 公式來精確地計算多邊形的面積。
二、縮圖的繪製
縮圖的目的是要擷取原圖中足夠讓我們可以計算其面積的資訊, 使得在儲存圖形時較不佔空間。 繪製縮圖時僅需要保留多邊形頂點的相對位置、縱格線間與橫格線間的資訊即可。 接下來, 我們以圖二來說明縮圖的繪製過程。
- 步驟一: 確定圖形中多邊形的頂點位置, 如圖二中的 $\bullet$ 點。
- 步驟二: 保留通過 $\bullet$ 點的縱格線與橫格線, 刪除其他格線, 並標上格線間的間距, 如圖三。
- 步驟三: 移動格線讓整張圖不需佔據太大的空間, 如圖四, 圖四就是圖二的縮圖。
在圖四中, 數字的部分是縱格線間與橫格線間的資訊, 我們將利用這些資訊來計算 Pick 公式所需的格子點數。 很明顯的, 儲存圖四所需的資源 (如紙張的大小等) 遠比圖二來得少, 這是縮圖的貢獻之一。
三、利用縮圖計算格子點數
我們最終的目的是要使用 Pick 公式來計算圖二的面積, 本節將介紹如何利用圖四的資訊讓我們可以計算出圖二中圖形其邊界上與內部所含的格子點數。 值得注意的是, 在接下來的討論過程中, 我們會發現這個新的計算過程不再以目測的方式逐點數出圖形邊界上與內部所含的格子點數, 因此也就沒有第一節所述的困擾。我們將分兩個步驟說明。
步驟一: 首先我們先觀察如何由圖四的資訊獲取圖二的邊界上有幾個格子點。 由於圖形是五邊形, 因此有五個邊, 我們將其個別討論並用圖五來表示。
在圖五 (a) 中, 兩 $\bullet$ 點當然是落在格子點上, 但這兩 $\bullet$ 點間的連線是否還有其他格子點呢? 從數學的角度可使用最大公因數來獲得此資訊, 亦即落在兩 $\bullet$ 點間連線上的格子點數為 \begin{equation} %(1) \hbox{GCD}(m, n) - 1 \end{equation} 其中 $m$ 與 $n$ 分別是縱格線與橫格線的資訊, GCD 表示最大公因數。
公式 (1) 的證明: 若兩 $\bullet$ 點間的連線為橫線段或縱線段, 則 (1) 式成立。 若為斜線段, 不失一般性, 我們考慮圖六中的線段, 則我們的問題就轉換成在 $0\lt x\lt n$ 的範圍中, 直線 $y=\displaystyle\frac{m}{n}x$ 上有幾個 $(x, y)\in Z\times Z$, 其中 $Z$ 為整數集。 存在 $m_1, n_1\in Z$, 使得 $m=\hbox{GCD}(m, n)m_1$ 與 $n=\hbox{GCD}(m, n)n_1$, 其中 $\hbox{GCD}(m_1, n_1)=1$。 則直線方程式可改寫成 $y=\displaystyle\frac{m_1}{n_1}x$, 由於 $m_1$ 與 $n_1$ 互質, 因此使得 $y\in Z$ 的整數 $x$ 僅有 $kn_1$ 這種型式, 其中 $k\in Z$, 所以我們必須在 $0\lt x\lt n$ 的範圍下找到 $kn_1$ 這種型式的值。 由於 $n=\hbox{GCD}(m, n)n_1$, 因此 $k$ 值的集合為 $\{1, 2, \ldots, \hbox{GCD}(m, n)-1\}$, 也就是說落在兩 $\bullet$ 點間連線上的格子點數為 $\hbox{GCD}(m, n)-1$, 得證。
透過公式 (1), 我們可求得圖五中各圖之兩 $\bullet$ 點間連線上的格子點數分別為
- $\hbox{GCD}(3+2, 4)-1=0$;
- $\hbox{GCD}(3, 1+2)-1=2$;
- $\hbox{GCD}(2+3, 3)-1=0$;
- $\hbox{GCD}(3, 2+3)-1=0$;
- $\hbox{GCD}(0, 4+1)-1=4$
步驟二:
接下來, 我們要把五邊形內部的格子點數確定。首先, 我們將圖四用分割線 (僅用縱線或橫線, 在這種分割下, 只會分割出直角三角形與矩形) 作分解, 分解成四個直角三角形與兩矩形, 如圖七所示。 事實上, 我們使用了五條分割線來分解圖四。 接著, 我們先計算這五條分割線上有幾個格子點, 因為這五條分割線都是直線, 因此我們很容易可以透過圖七格線上的資訊來得到落在分割線上的格子點數, 依序 (逆時針方向) 為 $3+2-1=4$, $1+2-1=2$, $2+3-1=4$, $1+2+3-1=5$, $3-1=2$, 如圖九所示。
|
|
在圖七中我們將五邊形內部分成六個區域, 為方便起見, 我們命名為 I, II, III, IV, V, VI 區, 如圖八所示。 只要再把這六個區域內所含的格子點數算出, 那麼所有格子點數就可以完整得到。 那麼要如何要計算剩下的格子點數呢? 我們以 I 區為例, 圖十 (a) 是縮圖的資訊, 圖十 (b) 則是原始的圖形。
在圖十 (c) 中我們畫上一個矩形, 這個矩形含有 $(3+2-1)\times(4-1)=12$ 個格子點, 分別是 6 個實心小方形與 6 個空心小方形, 而這 6 個實心小方形正好是 I 區內的格子點, 因此從圖十 (a) 的縮圖資訊, 我們可計算 I 區內的格子點數為 $\displaystyle\frac{(3+2-1)\times(4-1)}{2}=6$ 個。 讓我們再看 II 區, 見圖十一, 仿照 I 區的作法, 我們畫出一個矩形, 這個矩形含有 $(3-1)\times(1+2-1)=4$ 個格子點, 分別是 1 個實心小方形、 1 個空心小方形與 2 個實心小圓, 然而這 2 個實心小圓已在步驟一算過了, 因此我們不能再考慮, 因此只剩下 2 個格子點, 除以 2 之後, 就得到 II 區只含 1 個格子點, 換言之, 從圖十一 (a) 的縮圖資訊, 我們可計算 II 區內的格子點數為 $$ \frac{(3-1)\times(1+2-1) - (\hbox{GCD}(3, 1+2)-1)}{2} = 1 $$ 其中 $\hbox{GCD}(3, 1+2)-1=2$ 是步驟一中計算邊界上的格子點數。 事實上, 由於 $\hbox{GCD}(3+2, 4)-1=0$, 因此之前在計算 I 區內的格子點數時, 沒有考慮到需要引入最大公因數的想法。
綜合以上對 I 與 II 區的討論, 我們觀察到一個公式為 \begin{equation} %(2) \frac{(m-1)\times(n-1) - (\hbox{GCD}(m, n)-1)}{2} \end{equation} 其中 $m$ 與 $n$ 分別是縱格線與橫格線的資訊。注意到公式 (2) 僅適用於當分割區為直角三角形時, 若分割區為矩形時, 不難看出其內部格子點數為 $(m-1)\times(n-1)$, 因此接下來我們僅證明公式 (2)。
公式 (2) 的證明: 假設我們想求在圖十二中 $A$ 內部的格子點數, 其中 $m$ 與 $n$ 分別是縱格線與橫格線的資訊。 作虛線使圖形成為一個矩形, 則粗線段為矩形的對角線, 由於對稱的性質, 矩形的對角線可使 $A$ 內部與 $B$ 內部具有相同的格子點數。 另一方面, 整個矩形內部具有 $(m-1)\times(n-1)$ 個格子點, 且粗線段上扣除兩端點後具有 $\hbox{GCD}(m, n)-1$ 個格子點 (見公式 (1)), 因此 $A$ 內部的格子點數可用公式 (2) 來計算, 得證。
現在, 我們可以計算其他區內的格子點數了, 分別是 \begin{eqnarray*} && \hbox{III 區 : } \frac{(2+3-1)\times(3-1) - (\hbox{GCD}(2+3, 3)-1)}{2} = 4 \hskip 5cm \\ && \hbox{IV 區 : } (2-1) \times (1+2-1) = 2 \\ && \hbox{V 區 : } \frac{(3-1)\times(2+3-1) - (\hbox{GCD}(3, 2+3)-1)}{2} = 4 \\ && \hbox{VI 區 : } (3-1) \times (1-1) = 0 \\ \end{eqnarray*} 因此圖七中六區內所含的格子點數為 $6+1+4+2+4+0=17$ 個, 而分割線上的格子點數為 $4+2+4+5+2=17$, 於是步驟二共計算出 $17+17=34$ 個格子點數。
在經過步驟一與步驟二的討論後, 我們已經透過圖四的縮圖資訊可以知道圖二的五邊形中, 邊界上共有 11 個格子點 (步驟一), 內部共有 34 個格子點 (步驟二), 代入 Pick 公式, 可得到此五邊形的面積為 $\displaystyle\frac{11}{2}+34-1=38.5$。
由上面的論述可知圖四所含計算面積的資訊與圖二是相同的, 然而繪製圖二需要較大的空間, 因此我們認為用圖四來儲存資訊較經濟, 再配合步驟一與步驟二的計算過程, 我們依然可以計算其面積。 最後, 有一點必須注意, 由於縮圖並非等比例縮小, 因此大部分的原圖與縮圖間沒有相似的關係, 舉例來說, 圖十三 (b) 為圖十三 (a) 的縮圖, 但圖十三 (a) 是凸多邊形, 圖十三 (b) 卻是凹多邊形。
四、Pick 公式的小推廣
傳統的 Pick 公式必須假設多邊形的頂點是若在格子點上, 在本節中, 我們稍微放寬這個限制。 考慮當縱格線間與橫格線間的資訊為有理數的情況, 如圖十四 (a) 所示, 而真實的圖形繪製在座標平面上就如圖十四 (b) 所示。 顯然, 計算圖十四 (b) 的面積已不能使用傳統的 Pick 公式, 因為多邊形的頂點有些不落在格子點上。
幸運的是, 我們可以作一些轉換來處理這個問題。 這個轉換的概念非常簡單, 就是將圖十四 (b) 的圖形放大至所有的頂點座標都變成整數, 如圖十五所示, 我們將圖形往水平方向 (正向) 放大 20 倍, 而垂直方向 (正向) 放大 10 倍, 因此我們就可用 Pick 公式來計算圖十五 (b) 的面積。 另一方面, 圖十五 (b) 的面積是圖十四 (b) 面積的 $20\times 10=200$ 倍, 因此, 將圖十五 (b) 的面積除以 200 就可以得到圖十四 (b) 的面積。 然而, 要用 Pick 公式來計算圖十五 (b) 的面積似乎不太容易, 幸好我們有圖十五 (b) 的縮圖 (圖十五 (a)), 讓我們再次用前一節的方法來計算圖十五 (b) 的面積。
步驟一:
邊界上的格子點數為 \begin{eqnarray*} && \hskip -25pt \hbox{GCD}(25+17, 0) + \hbox{GCD}(30, 16+40) + \hbox{GCD}(17+30, 65) + \hbox{GCD}(25, 40+65) \\ && + \hbox{GCD}(0, 16) = 66 \end{eqnarray*}
步驟二:
- 分割線上的格子點數為 $(25\!+\!17\!-\!1)+(16\!+\!40\!-\!1)+(17\!+\!30\!-\!1)+(40\!+\!65\!-\!1)=246$
- I 區內的格子點數為 $(25+17-1)\times(16-1)=615$
- II 區內的格子點數為 $\displaystyle\frac{(30\!-\!1)\times(16\!+\!40\!-\!1)-(\hbox{GCD}(30, 16\!+\!40)\!-\!1)}{2}=797$
- III 區內的格子點數為 $\displaystyle\frac{(17\!+\!30\!-\!1)\times(65\!-\!1)-(\hbox{GCD}(17\!+\!30, 65)\!-\!1)}{2}=1472$
- IV 區內的格子點數為 $(17-1)\times(40-1)=624$
- III 區內的格子點數為 $\displaystyle\frac{(25\!-\!1)\times(40\!+\!65\!-\!1)-(\hbox{GCD}(25, 40\!+\!65)\!-\!1)}{2}=1246$
將步驟一與步驟二所獲得的資訊代入 Pick 公式, 得到圖十五 (b) 的面積為 $$ \frac{66}{2} + (246+615+797+1472+624+1246) - 1 = 5032 $$ 由於圖十五 (b) 的面積是圖十四 (b) 面積的 200 倍, 因此圖十四 (b) 的面積為 $\displaystyle\frac{5032}{200}=25.16$。 最後我們使用測量師公式 (A surveyor's formula, 可見蔡聰明 (1994)) 來檢驗我們的答案是否正確, 由圖十四 (b) 可知圖形的頂點為 $(0, 3)$, $(2.8, 0)$, $(6.05, 4.7)$, $(0.8, 7.2)$, $(0, 7.2)$ 五點, 代入測量師公式, 可得圖十四 (b) 的面積為 $$ \frac{1}{2} \Bigg ( \left | \begin{array}{cc} 0 & \quad 3 \\ 2.8 & \quad 0 \end{array} \right | + \left | \begin{array}{cc} 2.8 & \quad 0 \\ 6.05 & \quad 4.7 \end{array} \right | + \left | \begin{array}{cc} 6.05 & \quad 4.7 \\ 0.8 & \quad 7.2 \end{array} \right | + \left | \begin{array}{cc} 0.8 & \quad 7.2 \\ 0 & \quad 7.2 \end{array} \right | + \left | \begin{array}{cc} 0 & \quad 7.2 \\ 0 & \quad 3 \end{array} \right | \Bigg ) = 25.16 $$ 果然與我們的方法所計算的結果一致。
五、結語
本文透過縮圖的概念提供一個避免目測計算格子點的方法, 此法的計算過程只引用了最大公因數這一個數學工具, 整體來說不難瞭解。 此外, 透過縮圖可讓使用者在利用 Pick 公式時更加便利。本文僅對凸多邊形進行討論, 至於凹多邊形就留給後續有興趣的讀者繼續論述。
誌謝
感謝審稿人提出的建言, 讓本文的內容更加豐富。
參考文獻
---------本文作者為中央研究院統計科學研究所博士後研究---------