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

網友William留言：

老師，您好！我不是您的學生，但是又有一個問題苦無解決辦法，因此想向老師尋求協助。問題是這樣的：群組A內有 ，，五個點。其中 ，，， 為一矩形的四個端點，而 位於矩形的範圍內或邊線上。群組B內有 ，，五個點。現在假設存在一張對應表： 查表後的值為 ，，求 查表後的值 ，並以 ，，和 ，，表示。我不知道這個問題是否適合由線性代數解決，也不曉得應該從那裡下手。懇請老師提供意見。謝謝。

 
答曰：

我將問題改寫如下：令 ，，為一矩形的四個端點。設 為一映射使得 ，。給定位於矩形的範圍內或邊線上一點 ，求 。

 
矩形內 (含邊線) 的任一點 可表示為端點 的凸組合 (convex combination)，如下：

，

其中 且每一 ，我們稱此矩形是四個端點構成的凸包 (convex hull)，詳細討論見“凸組合、凸包與凸集”。注意，凸包內點 的凸組合表達式並不唯一。如果 為於三個端點，譬如，，所形成的三角形內，則有唯一凸組合式 ()，理由如下：因為 是線性獨立集，存在唯一數組 使得

其中 且 ，否則 將位於三角形之外。

 
既然你期待此問題可用線性代數解決，那麼我們必須對映射 加入限制。下面舉兩個常見的例子。若 是一線性變換，滿足 和 ，其中 ，，則

若 是一仿射變換 (affine transformation)，表示為 ，其中 是一線性變換， 是二維向量 (見“仿射變換”)，則

不論 是線性變換或仿射變換， 皆可表示為 的凸組合，組合係數即為 以矩形端點 表達的凸組合係數。

 
最後以一例說明凸組合係數的算法。若一矩形包含頂點 ，，，，求 表示為此四點的凸組合式。使用齊次座標，即 改成 ，凸組合與條件式 可合併如下：

。

欲解出未知數 ，寫出增廣矩陣並以基本列運算化簡：

故通解為

其中 保證每一 。

Advertisement