查看“凸包”的源代码

[[File:ConvexHull.png|right|300px|thumb|凸包（Convex hull）：彈性繩帶的類比。]]
<!-- attention, the following is not correct!
在實[[向量空間]]中，若<math>S</math>是最小的[[凸集]]使得一個點集<math>X</math>屬於<math>S</math>，則S稱為X的'''凸包'''。
1. 屬於 is definitely wrong
2. if changed to 含于, it is also wrong.
We should conform to the standard defintion. Thanks. -->

<!-- the vector space is over a field of real numbers, but itself does not have to be real -->
在一个[[实数]][[向量空間]]<math>V</math>中，对于给定集合<math>X</math>，所有包含X的[[凸集]]的[[交集]]<math>S</math>被称为<math>X</math>的'''凸包'''。
:<math> S := \bigcap_{X \subseteq K \subseteq V \atop K\ \mathrm{is\ convex}} K.</math>
<!--兩個包含<math>X</math>的凸集的交集都包含<math>X</math>。-->

<math>X</math>的凸包可以用<math>X</math>内所有点<math>(x_1, \ldots, x_n)</math>的[[线性组合]]来构造。
:<math> S := \left\{ \left. \, \sum_{j=1}^n t_j x_j\, \right| x_j \in X,\, \sum_{j=1}^n t_j = 1,\, t_j \in \lbrack 0, 1 \rbrack \, \right\}.</math>

在二维[[欧几里得空间]]中，凸包可想象為一條剛好包著所有點的橡皮圈。

==演算法==
===增量式算法===
逐次將點加入，然後檢查之前的點是否在新的凸包上。由於每次都要檢查所有之前的點，時間複雜度為<math>O(n^2)</math>。

=== 包裹法（Jarvis步进法）===

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

===葛立恒（Graham）扫描法 ===
[[File:Graham scan.png|right]]

由最底的一點<math>A_1</math>開始（如果有多个这样的点，那么选择最左边的），計算它跟其他各點的連線和x軸正向的角度，按小至大將這些点排序，稱它們的對應點為<math>A_2,A_3,...,A_n</math>。這裡的時間複雜度可達<math>O(n \log{n})</math>。

考慮最小的角度對應的點<math>A_3</math>。若由<math>A_2</math>到<math>A_3</math>的路徑相對<math>A_1</math>到<math>A_2</math>的路徑是向右轉的（可以想象一個人沿<math>A_1</math>走到<math>A_2</math>，他站在<math>A_2</math>時，是向哪邊改變方向），表示<math>A_3</math>不可能是凸包上的一點，考慮下一點由<math>A_2</math>到<math>A_4</math>的路徑；否則就考慮<math>A_3</math>到<math>A_4</math>的路徑是否向右轉……直到回到<math>A_1</math>。

這個演算法的整體時間複雜度是<math>O(n \log{n})</math>，注意每點只會被考慮一次，而不像Jarvis步进法中會考慮多次。

這個演算法由[[葛立恆]]在1972年發明。<ref>Graham, R.L. (1972). [http://www.sciencedirect.com/science?_ob=IssueURL&_tockey=%23TOC%235645%231972%23999989995%23299179%23FLP%23&_auth=y&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=5d4861b6aa0cc6f286e142e7d22047c1 An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set]. Information Processing Letters 1, 132-133</ref>它的缺點是不能推廣到二維以上的情況。

===單調鏈===
將點按x坐標的值排列，再按y坐標的值排列。

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

時間複雜度是<math>O(n\log{n})</math>。

===[[分治法]]===
將點集X分成兩個不相交子集。求得兩者的凸包後，計算這兩個凸包的凸包，該凸包就是X的凸包。時間複雜度是<math>O(n\log{n})</math>。

===快包法（Akl-Toussaint启发式）===
選擇最左、最右、最上、最下的點，它們必組成一個凸[[四邊形]]（或三角形）。這個四邊形內的點必定不在凸包上。然後將其餘的點按最接近的邊分成四部分，再進行快包法（QuickHull）。

==各种[[星形多面体]]的凸包==
{| class="wikitable sortable"
|-
! [[多面体]]名称 !! 凸包
|-
| [[小星形十二面体]] || [[正二十面体]]
|-
| [[大十二面体]] || [[正二十面体]]
|-
| [[大星形十二面体]] || [[正十二面体]]
|-
| [[大二十面体]] || [[正十二面体]]
|}

==應用==
* [[圖象處理]]
* [[模式識別]]
* [[地理信息系統]]

==參考==
<references/>

* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Pages 955–956 of section 33.3: Finding the convex hull.
* [http://www.geometryalgorithms.com/Archive/algorithm_0109/algorithm_0109.htm The Convex Hull of a 2D Point Set or Polygon, by Dan Sunday]
==參見==
* [[Carathéodory定理]]
* [[Delaunay三角化]]
==外部連結==
* [https://web.archive.org/web/20070609032115/http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html 一個展示這些演算法如何運作的Java Applet]
* [https://web.archive.org/web/20101128202848/http://www.math.ust.hk/mathematical_excalibur/v12_n3.pdf Convex Hull, Kin Yin Li]
* [http://par.cse.nsysu.edu.tw/~homework/algo01/9037621/html/QuickHull.htm QuickHull 介紹：]
* [http://par.cse.nsysu.edu.tw/~homework/algo01/9037621/html/Incremental.htm Incremental(增量法) 介紹]
* [http://par.cse.nsysu.edu.tw/~homework/algo01/9037621/html/Gift_Wrapping.htm Jarvis March (Gift Wripping)介紹：]

[[Category:多胞形]]
[[Category:算法]]
[[Category:凸几何]]
[[Category:計算幾何]]