版本 a18796642b976f38de0ab7269a506bc90f0f9f17
Changes from a18796642b976f38de0ab7269a506bc90f0f9f17 to current
定義
=============
在散所有散佈點中，找出一個凸多邊形可以剛好包含所有的點<br>
像下圖所示
<br>
演算法介紹
=============
有三種方法來找出凸多邊形
Brute Force
-------------
說明：<br>
此方法為暴力解，先選擇任意兩個點構成線 <br>
假設其他的點都在那條線的左邊（or右邊, 固定一邊）<br>
則此邊為我們要的邊<br>
<br><br><br>
pseudo code: <br>
```c++
Algorithm CH(P)
E←∅(* edge-list of CH(P) *)
for all ordered pairs (p,q) ∈ p×p, p≠q do
supporting ← true
for all points r ∈ P-{p,q} do
if r is on the right side of pq then supporting ← false
if supporting then add directed edge pq to E
From the (un-ordered) edge-list E, construct the list of vertices of CH(P) in CCW order in O(n) time. (How?)
end
```
<br>
複雜度：Ｏ(n³)
Graham-Scan
-------------
說明：<br>
1.選定起始點，利用起始點跟其他點連線所構成的角度，去sort各個點<br><br>
<br><br>
Compare Function:<br>
```c++
bool compare_angle(Point& a, Point& b)
{
// 角度相同時,距離長度的判斷。
int c = cross(P[0], a, b);
return c > 0 ||
(c == 0 && length2(P[0], a) < length2(P[0], b));
}
```
<br>2.再開始一個一個點連線，假設有依照順序連到了P3, 就要檢查往前數的第二點P1<br>
，此點與p2, 和p3的外積，如果外積小於0，p3就要連回p1（如下圖所示），如果大於0，就不變
<br>
<br>3.完成後的圖形<br><br>
<br>
<br>4.Pseudo code<br>
```c++
Graham-Scan(Q)
void Graham_scan() {
//將最左下的點移到起點
swap(P[0], min_element);
// 其餘各點依角度排序。O(NlogN)
sort(P+1, P+N, compare_angle);
// 直接把中心點作為起點,開始包覆,逆時針方向。
O(N)P[N] = P[0]; // 讓程式方便處理包至最後一點的情況。
for (int i=0; i<=N; ++i){
// 掃除凹陷的點
// 添加新的點 // 扣掉最後一個點
}
```
Andrew's Monotone Chain
----------------------------
>step1:將所有點按座標大小排序
<br>
>step2:將下半部圍起來
<br>
>step3:維持下半部不動，將上半部圍起來
<br>
>step4:刪去重複的起點
------------------------------
STEP1: 依照每個點的x座標進行排序
<br>
STEP2:
```c++
int m=0;
for(int i=0; i<N; i++)
{
while(m>=2 &&
cross(CH[m-2], CH[m-1], P[i] <= 0) m--;
CH[m++] = P[i];
}
```
<br>
STEP3:
```c++
for(int i=N-2, t=m+1; i>=0; --i)
{
while(m>=t &&
cross(CH[m-2], CH[m-1], P[i] <= 0) m--;
CH[m++] = P[i];
}
```
<br>
STEP4:刪除最後一個點
<br> 
