凸包

出自 MBA智库百科(http://wiki.mbalib.com/)

凸包(Convex hull)

目錄

什麼是凸包

  在瞭解凸包之前,須先認識何謂“凸多邊形”(Convex Polygon)。從直觀上說,一個凸多邊形就是沒有任何凹陷位的多邊形。我們在低年級數學所學習的三角形、正方形、長方形、平行四邊形、正五邊形、正六邊形等等,都是凸多邊形的例子。但是以下這個“凸”字形卻並非凸多邊形,因為箭頭指著的地方實際是一個凹陷位。

  凸包

  可是上述這一定義很不嚴密,究竟何謂“凹陷位”?實在難以說清楚。因此在數學上,凸多邊形有另一個嚴格的定義。假設我們在一個多邊形上(包括多邊形的邊界及邊界圍封的範圍)任意取兩點並以一條線段連結該兩點,如果線段上的每一點均在該多邊形上,那麼我們便說這個多邊形是凸的。根據以上定義,我們便可判斷“凸”字形的確不是凸的。例如,在下圖中,連結A、B兩點的線段有一部分並不在該多邊形上。

  凸包

  認識了凸多邊形後,我們便可瞭解何謂凸包。給定平面上的一個(有限)點集(即一組點),這個點集的凸包就是包含點集中所有點的最小面積的凸多邊形。例如,下圖的點集共包含9個點,圖中的六邊形便是該點集的凸包。其中構成六邊形的6個點稱為“凸包上的點”(Hull Point),其餘3個點則並非“凸包上的點”。請註意上述定義中“最小面積”這個限制條件,因為除了凸包以外,還有無限多個包含點集中所有點的凸多邊形。例如,只要畫一個面積足夠大的四邊形,便可包圍任意給定的點集。因此假如沒有這個限制條件,求凸包就變成非常容易但卻沒有唯一解的運算。

  凸包

凸包的表達方式

  在一個實數向量空間V中,對於給定集合X,所有包含X的凸集的交集S被稱為X的凸包。

  凸包

  X的凸包可以用X內所有點(x_1, \ldots, x_n)的線性組合來構造。

  S:=\begin{Bmatrix} \sum_{j=1}^nt_jx_j|x_j\in X,\sum_{j=1}^nt_j=1,t_j\in[0,1] \end{Bmatrix}

  在二維歐幾裡得空間中,凸包可想象為一條剛好包著所有點的橡皮圈。

  凸包

凸包的演算法

  增量式演算法1

  逐次再點加入,然後檢查之前的點是否在新的凸包上。由於每次都要檢查所有之前的點,時間複雜度為O(n2)

  包裹法(Jarvis步進法)

  首先由一點必定在凸包的點開始,例如最左的一點A1。然後選擇A2點使得所有點都在A1A2的右方,這步驟的時間複雜度是O(n),要比較所有點以A1為原點的極坐標角度。以A2為原點,重覆這個步驟,依次找到A_3,A_4,\ldots,A_k,A_1。這總共有k步。因此,時間複雜度為O(n2)
凸包

  葛立恆掃描法

  由最底的一點A1開始,計算它跟其他各點的連線和x軸的角度,按小至大將這些角度排序,稱它們的對應點為A_2,A_3,\ldots,A_n。這裡的時間複雜度可達O(nlogn)。

  考慮最小的角度對應的點A3。若由A2A3的路徑相對A1A2的路徑是向右轉的(可以想象一個人沿A1走到A2,他站在A2時,是向哪邊改變方向),表示A3不可能是凸包上的一點,考慮下一點由A2A4的路徑;否則就考慮A3A4的路徑是否向右轉……直到回到A1

  這個演算法的整體時間複雜度是O(nlogn),註意每點只會被考慮一次,而不像Jarvis步進法中會考慮多次。

  這個演算法由葛立恆在1972年發明。[1]它的缺點是不能推廣到二維以上的情況。

  單調鏈

  將點按x坐標的值排列,再按y坐標的值排列。

  選擇x坐標為最小值的點,在這些點中找出y坐標的值最大和y坐標的值最小的點。對於x坐標為最大值也是這樣處理。將兩組點中y坐標值較小的點連起。在這條線段下的點,找出它們之中y坐標值最大的點,又在它們之間找x坐標值再最小和最大的點……如此類推。

  時間複雜度是O(n log n)。

  分治法

  將點集X分成兩個不相交子集。求得兩者的凸包後,計算這兩個凸包的凸包,該凸包就是X的凸包。時間複雜度是O(n log n)。

  快包法(Akl-Toussaint啟髮式)

  選擇最左、最右、最上、最下的點,它們必組成一個凸四邊形(或三角形)。這個四邊形內的點必定不在凸包上。然後將其餘的點按最接近的邊分成四部分,再進行快包法(QuickHull)。

參考文獻

  1. Graham,R.L.(1972).An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set.Information Processing Letters 1,132-133
本條目對我有幫助10
分享到:
  如果您認為本條目還有待完善,需要補充新內容或修改錯誤內容,請編輯條目

本条目由以下用户参与贡献

Zfj3000.

評論(共0條)

提示:評論內容為網友針對條目"凸包"展開的討論,與本站觀點立場無關。

發表評論請文明上網,理性發言並遵守有關規定。

返回顶部