My Weblog

Blog about programming and math

Convex Hull

In computational geometry, it is common to use the term “convex hull” for the boundary of the minimal convex set containing a given non-empty finite set of points in the plane. Unless the points are collinear, the convex hull in this sense is a simple closed polygonal chain.For convex hull we have lots of algorithm having different complexity.This code is implimentation of Graham scan.

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
vector<pair<int,int> >v;
void fun(vector<pair<int,int> > &v)
{
for(int i=1;i<v.size();i++)
{
if(v[i]<v[0])
swap(v[0],v[i]);

}
}
bool cmp(pair<int,int>p1,pair<int,int>p2)
{
int w=(p1.second-v[0].second)*(p2.first-v[0].first)-(p2.second-v[0].second)*(p1.first-v[0].first);
if(w<0)
return 1;
else if(w==0)
{
if( p1.first<p2.first)
return 1;
else if(p1.first==p2.first)
return p1.second<p2.second;
else
return 0;
}
else
return 0;
}
int cross(pair<int,int>p1,pair<int,int>p2,pair<int,int>p3)
{
return (p1.first-p2.first)*(p3.second-p2.second)-(p3.first-p2.first)*(p1.second-p2.second);
}
int main()
{
int t,n;
cin>>t;
while(t–)
{
int k1,k2;
cin>>n;
v.clear();
for(int i=0;i<n;i++)
{
cin>>k1>>k2;
v.push_back(make_pair(k1,k2));
}
fun(v);
sort(v.begin()+1,v.end(),cmp);
stack<pair<int,int> >S;
pair<int,int>p1,p2;
S.push(v[0]);
S.push(v[1]);
for(int i=2;i<n;i++)
{
p1=S.top();
S.pop();
p2=S.top();
S.push(p1);
int w=cross(p1,p2,v[i]);
if(w==0)
S.pop(),S.push(v[i]);//pop previous point and take next collinear point
else if(w>0)
S.push(v[i]);//left turn
else//right turn
{
while(w<=0 && S.size()>2)
{
S.pop();
p1=S.top();
S.pop();
p2=S.top();
S.push(p1);
w=cross(p1,p2,v[i]);
}
S.push(v[i]);
}

}
cout<<“points on hull are \n”;
while(!S.empty())
{
p1=S.top();
S.pop();
cout<<p1.first<<” “<<p1.second<<endl;
}
}
}

Advertisements

May 26, 2008 - Posted by | Uncategorized |

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: