歡迎光臨本網頁。在這個網頁中，你可以學習到計算幾何(Computational Geometry)中的「凸包」(Convex Hull)概念，以及求凸包的基本原理。你亦可試用本人編寫的用來求凸包的應用程式。
在了解凸包之前，須先認識何謂「凸多邊形」(Convex Polygon)。從直觀上說，一個凸多邊形就是沒有任何凹陷位的多邊形。我們在低年級數學所學習的三角形、正方形、長方形、平行四邊形、正五邊形、正六邊形等等，都是凸多邊形的例子。但是以下這個「凸」字形卻並非凸多邊形，因為箭頭指著的地方實際是一個凹陷位。
可是上述這一定義很不嚴密，究竟何謂「凹陷位」？實在難以說清楚。因此在數學上，凸多邊形有另一個嚴格的定義。假設我們在一個多邊形上(包括多邊形的邊界及邊界圍封的範圍)任意取兩點並以一條線段連結該兩點，如果線段上的每一點均在該多邊形上，那麼我們便說這個多邊形是凸的。根據以上定義，我們便可判斷「凸」字形的確不是凸的。例如，在下圖中，連結A、B兩點的線段有一部分並不在該多邊形上。
認識了凸多邊形後，我們便可了解何謂凸包。給定平面上的一個(有限)點集(即一組點)，這個點集的凸包就是包含點集中所有點的最小面積的凸多邊形。例如，下圖的點集共包含9個點，圖中的六邊形便是該點集的凸包。其中構成六邊形的6個點稱為「凸包上的點」(Hull Point)，其餘3個點則並非「凸包上的點」。請注意上述定義中「最小面積」這個限制條件，因為除了凸包以外，還有無限多個包含點集中所有點的凸多邊形。例如，只要畫一個面積足夠大的四邊形，便可包圍任意給定的點集。因此假如沒有這個限制條件，求凸包就變成非常容易但卻沒有唯一解的運算。
本人編寫了三個求凸包的應用程式，包括一個Visual Basic版和兩個Flash版。Visual Basic版為EXE檔，請點擊下列連結，下載有關檔案(該EXE檔連同其他必要檔案已壓縮在一個ZIP檔案中，下載後必須解壓縮)，然後便可在你的電腦上執行。兩個Flash版分別為SWF和EXE檔，你只需點擊下列有關連結，便可執行程式。上述程式都包含「使用說明」或"Instructions"，瀏覽者只需依照說明上的指示便可使用該程式，請選擇適合你電腦的程式。
連結：
本程式採用循序漸進的方式求取給定點集的凸包，首先把使用者最初輸入的3個不共線(Non-collinear)的點按逆時針方向構成一個三角形(註1)，這就是這3點的凸包。接著程式便會考察第4點，看看這個點是否位於前述三角形之內或三角形的邊上。若是，則這第4點並非凸包上的點，前述三角形保持不變。若否，則把這前述的三角形擴大為一個四邊形，並把不適用的邊擦去。這個四邊形便是這首4點的凸包。接著程式又會考察第5點，如此類推，直至所有點均已被考察為止。使用者在使用本程式時可以清楚看到上述從最初的三角形逐步擴大為最終的凸包的過程。
這裡涉及到判斷一點是否被包圍在某一多邊形內的問題，人類憑肉眼很容易便能作出此一判斷。可是電腦沒有眼睛，它所具備的資訊只有給定點的坐標，我們應如何「教」電腦作出上述判斷呢？其實方法並不太複雜。且來看看一個簡單的例子。
在上圖中，A、B、C是最初輸入的三點，這三點按逆時針方向構成了一個三角形。接著讓我們考察第4個點D。這一點有甚麼特點？假如我們循著逆時針方向在三角形的邊上走一周，我們便會發現D點總是位於我們的左方。事實上，在三角形範圍內的任何一點都具有此一特點。
接著讓我們來考察第5點E，這一點的情況跟D點很不一樣。假如我們循著逆時針方向在三角形的邊上走一周，我們便會發現E點有時出現在我們的左邊，有時出現在右邊。事實上，在三角形範圍外的任何一點都具有此一特點。而且，上述方向改變還可幫助我們判斷應把哪一點連到E點以及應擦去哪一條線。例如，當我們從CA線走到AB線上時，E點的位置從我們的左邊變為右邊(註2)，此一轉向告訴我們應把A點連向E點。同樣，當我們從AB線走到BC線上時，E點的位置從我們的右邊變為左邊，此一轉向告訴我們應把B點連向E點。此外，在上述分析中，E點總是位於AB線的右邊，因此AB線必不能包住E點，因此應將AB線擦去。最後，當我們從BC線走到CA線上時，E點總是位於我們的左邊，因此我們無須把C點連向E點。經過上述分析後，我們便得一個新的四邊形AEBC，這個四邊形就是圖中5點的凸包。
看到這裡，讀者不禁要問，電腦如何判斷某一點是位於某條直線的左邊還是右邊呢？其實只要看看上圖，我們容易發現，左轉相當於逆時針方向，右轉則相當於順時針方向。因此我們可以利用逆時針和順時針這一組概念來代替左、右這兩個概念。這裡我們可以用向量代數中一條有關平面三角形面積的公式。給定平面上3點P1、P2、P3的坐標(x1, y1)、(x2, y2)和(x3, y3)，這3點所構成三角形的面積可表達為一個名為Area的函數：
| Area(P1, P2, P3)= |
 |
此一公式使用行列式(Determinant)來定義三角形面積，可以展開並化簡為：
但請注意，上式並非單純計算三角形的面積，而是「有向面積」(Signed Area)，它不僅告訴我們給定3點所構成三角形的大小，而且告訴我們這3點的相對方向。當Area(P1, P2, P3)的值是負數時，這代表P1->P2->P3的走向是逆時針方向。反之，若Area(P1, P2, P3)的值是正數，則代表這3點的走向是順時針方向。若Area(P1, P2, P3)為零，則代表這3點共線。因此Area這個函數在求凸包的運算中有極大的用途，可用來判斷哪些點是凸包上的點，以及應用直線連結哪些點。事實上，本程式亦廣泛運用這個函數。
