答William──關於凸包的映射問題

網友William留言:

老師,您好!我不是您的學生,但是又有一個問題苦無解決辦法,因此想向老師尋求協助。問題是這樣的:群組A內有 A_i(x_i,y_i)1\le i\le 5,五個點。其中 A_1A_2A_3A_4 為一矩形的四個端點,而 A_5 位於矩形的範圍內或邊線上。群組B內有 B_i(\hat{x}_i,\hat{y}_i)1\le i\le 5,五個點。現在假設存在一張對應表:A_i(x_i,y_i) 查表後的值為 B_i(\hat{x}_i,\hat{y}_i)1\le i\le 4,求 A_5(x_5,y_5) 查表後的值 B_5(\hat{x}_5,\hat{y}_5),並以 (x_i,y_i)1\le i\le 5,和 (\hat{x}_j,\hat{y}_j)1\le j\le 4,表示。我不知道這個問題是否適合由線性代數解決,也不曉得應該從那裡下手。懇請老師提供意見。謝謝。

 
答曰:

我將問題改寫如下:令 \mathbf{v}_i=(x_i,y_i)\in\mathbb{R}^21\le i\le 4,為一矩形的四個端點。設 T:\mathbb{R}^2\to\mathbb{R}^2 為一映射使得 T(\mathbf{v}_i)=\mathbf{u}_i=(\hat{x}_i,\hat{y}_i)1\le i\le 4。給定位於矩形的範圍內或邊線上一點 \mathbf{p},求 T(\mathbf{p})

 
矩形內 (含邊線) 的任一點 \mathbf{p} 可表示為端點 \mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3,\mathbf{v}_4 的凸組合 (convex combination),如下:

\displaystyle \mathbf{p}=c_1\mathbf{v}_1+c_2\mathbf{v}_2+c_3\mathbf{v}_3+c_4\mathbf{v}_4

其中 c_1+c_2+c_3+c_4=1 且每一 c_i\ge 0,我們稱此矩形是四個端點構成的凸包 (convex hull),詳細討論見“凸組合、凸包與凸集”。注意,凸包內點 \mathbf{p} 的凸組合表達式並不唯一。如果 \mathbf{p} 為於三個端點,譬如,\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3,所形成的三角形內,則有唯一凸組合式 \mathbf{p}=c_1\mathbf{v}_1+c_2\mathbf{v}_2+c_3\mathbf{v}_3 (c_4=0),理由如下:因為 \{\mathbf{v}_2-\mathbf{v}_1,\mathbf{v}_3-\mathbf{v}_1\} 是線性獨立集,存在唯一數組 d_1,d_2 使得

\displaystyle\begin{aligned} \mathbf{p}&=\mathbf{v}_1+d_1(\mathbf{v}_2-\mathbf{v}_1)+d_2(\mathbf{v}_3-\mathbf{v}_1)\\ &=(1-d_1-d_2)\mathbf{v}_1+d_1\mathbf{v}_2+d_2\mathbf{v}_3, \end{aligned}

其中 1-d_1-d_2\ge 0d_1,d_2\ge 0,否則 \mathbf{p} 將位於三角形之外。

 
既然你期待此問題可用線性代數解決,那麼我們必須對映射 T 加入限制。下面舉兩個常見的例子。若 T 是一線性變換,滿足 T(\mathbf{x}+\mathbf{y})=T(\mathbf{x})+T(\mathbf{y})T(c\mathbf{x})=cT(\mathbf{x}),其中 \mathbf{x},\mathbf{y}\in\mathbb{R}^2c\in\mathbb{R},則

\displaystyle\begin{aligned} T(\mathbf{p})&=T(c_1\mathbf{v}_1+c_2\mathbf{v}_2+c_3\mathbf{v}_3+c_4\mathbf{v}_4)\\ &=c_1T(\mathbf{v}_1)+c_2T(\mathbf{v}_2)+c_3T(\mathbf{v}_3)+c_4T(\mathbf{v}_4)\\ &=c_1\mathbf{u}_1+c_2\mathbf{u}_2+c_3\mathbf{u}_3+c_4\mathbf{u}_4. \end{aligned}

T 是一仿射變換 (affine transformation),表示為 T(\mathbf{x})=L(\mathbf{x})+\mathbf{b},其中 L 是一線性變換,\mathbf{b} 是二維向量 (見“仿射變換”),則

\displaystyle\begin{aligned} T(\mathbf{p})&=T(c_1\mathbf{v}_1+c_2\mathbf{v}_2+c_3\mathbf{v}_3+c_4\mathbf{v}_4)\\ &=L(c_1\mathbf{v}_1+c_2\mathbf{v}_2+c_3\mathbf{v}_3+c_4\mathbf{v}_4)+\mathbf{b}\\ &=c_1L(\mathbf{v}_1)+c_2L(\mathbf{v}_2)+c_3L(\mathbf{v}_3)+c_4L(\mathbf{v}_4)+(c_1+c_2+c_3+c_4)\mathbf{b}\\ &=c_1(L(\mathbf{v}_1)+\mathbf{b})+c_2(L(\mathbf{v}_2)+\mathbf{b})+c_3(L(\mathbf{v}_3)+\mathbf{b})+c_4(L(\mathbf{v}_4)+\mathbf{b})\\ &=c_1T(\mathbf{v}_1)+c_2T(\mathbf{v}_2)+c_3T(\mathbf{v}_3)+c_4T(\mathbf{v}_4)\\ &=c_1\mathbf{u}_1+c_2\mathbf{u}_2+c_3\mathbf{u}_3+c_4\mathbf{u}_4. \end{aligned}

不論 T 是線性變換或仿射變換,T(\mathbf{p}) 皆可表示為 \mathbf{u}_1,\mathbf{u}_2,\mathbf{u}_3,\mathbf{u}_4 的凸組合,組合係數即為 \mathbf{p} 以矩形端點 \mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3,\mathbf{v}_4 表達的凸組合係數。

 
最後以一例說明凸組合係數的算法。若一矩形包含頂點 (1,3)(3,3)(1,7)(3,7),求 (2,4) 表示為此四點的凸組合式。使用齊次座標,即 (x,y) 改成 (x,y,1),凸組合與條件式 c_1+c_2+c_3+c_4=1 可合併如下:

\displaystyle \begin{bmatrix} 2\\ 4\\ 1 \end{bmatrix}=c_1\begin{bmatrix} 1\\ 3\\ 1 \end{bmatrix}+c_2\begin{bmatrix} 3\\ 3\\ 1 \end{bmatrix}+c_3\begin{bmatrix} 1\\ 7\\ 1 \end{bmatrix}+c_4\begin{bmatrix} 3\\ 7\\ 1 \end{bmatrix}

欲解出未知數 c_1,c_2,c_3,c_4,寫出增廣矩陣並以基本列運算化簡:

\displaystyle \begin{bmatrix} 1&3&1&3&\vert&2\\ 3&3&7&7&\vert&4\\ 1&1&1&1&\vert&1 \end{bmatrix}\to\left[\!\!\begin{array}{cccrcc} 1&0&0&-1&\vert&1/4\\ 0&1&0&1&\vert&1/2\\ 0&0&1&1&\vert&1/4 \end{array}\!\!\right]

故通解為

\displaystyle\begin{aligned} c_1&=\frac{1}{4}+\alpha\\ c_2&=\frac{1}{2}-\alpha\\ c_3&=\frac{1}{4}-\alpha\\ c_4&=\alpha, \end{aligned}

其中 0\le \alpha\le 1/4 保證每一 c_i\ge 0

This entry was posted in 答讀者問, 仿射幾何 and tagged , , , , . Bookmark the permalink.

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s