Algo - Graham scan

最近遇到一個難題，就是在研究上我必須算出wiifit的xy資料包絡線。我曾經試著想自己搞出演算法，可是這比較麻煩，而且最重要的是我沒有時間這樣搞...

所以，任務可以簡化成為，我要在一個xy平面上尋找可以包圍這些所有點的最小多邊形。這是一個convex hull的問題，在wiki上這樣描述這演算法：
The Graham scan is a method of computing the convex hull of a finite set of points in the plane with time complexity O(n log n)
這演算法的命名是繼承提出者 Ronald Graham而命名，並且在1972年提出最初版本。


以下流程翻譯自wiki：
1.Graham scan在xy平面上先找出y值最小的點，如果存在多個y值相同的點，則取x最小的點，並稱這點為P
點，時間複雜度為O(n)。
2.剩餘的點，會根據與 "P點的x軸夾角大小"，由小到大sort。為了加速計算的過程，並不需要計算出他真正的夾角，取而代之，我們計算他的cosin值，這過程是一個單調遞減函數(monotonically decreasing function)，因為cosin值從0~180。
3.接著，從第 i=2 個點開始取，每次取連接 i 、 i-1、i-2三點的向量，看看他們是不是所謂的"left turn"? 如果是"right turn"則表示第 i-1 個點並不是我們要的點，則將他捨去。此時會有一個例外，若是三點共線(colinear)，則其中一個點可以考慮捨去，但是若有特別要求必須找出所有包圍的點，則不能捨棄( since in some applications it is required to find all points on the boundary of the convex hull)。
4.again，持續不斷的尋找直到找到最一開始的點。


tips：
所謂的"left turn" , "right turn"，有個快速的判斷方法，就是取他們兩個向量的外積。假設有 (x1,y1), (x2,y2),(x3,y3)三點，會形成兩線段A,B，A,B線段的外積值會因為夾角而不同，就是所謂的右手定則，若值=0表共線。


input : pooints[] 記錄所有的點
output : after[] 記錄所有convex hull的點

program；


vector<struct point> points;
vector<struct point> after;



oid Graham_scan()
{
after.push_back(points[0]);

int m=1;
bool end = false;

for(unsigned int i=2; i<points.size();i++)
{
m = i-1;
int bm = m-1;
while( (ccw(points[m-1], points[m], points[i])<=0) )
{
i++;
m = i-1;
if(i >= points.size()){
i=0;
m = points.size()-1;
end = true;
}
}
if((ccw(points[bm], points[m], points[i])>0))
after.push_back(points[m]);
if(end)
break;
}
after.push_back(points[points.size()-1]);
}


int main(int argc, char** argv)
{
int lowesty;

//讀檔
readfile();

//找尋最小的y
lowesty = find_lowest_y();

cout <<"最小y在:" <<lowesty<<" y值:"<< points[lowesty].y << endl;
//將y插入第一個位置 & 計算每個point的角度
insert_and_caltheta(lowesty);

cout << endl << "做排序" << endl;

int high=points.size()-1;
int low=1;
Quick_sort(low,high);

//執行Graham scan
Graham_scan();

system("pause");
return 0;
}