Hi All,
I'm trying to implement Graham Scan method for building a Convex
Hull. I've tried to solve some problems from online problem-sets, but
I've got wrong answers. So I'm not sure my implementation is
correct. Can anyone help me to find a bug?
Here's my source code in C++.
// Convex Hull - Graham Scan
#include <vector>
#include <algorithm>
using namespace std ;
struct P { int x, y; P() {}; P( int q, int w ) : x( q ), y( w )
{} };
P operator + ( const P p, const P q ) { P u( p.x + q.x, p.y + q.y );
return u; }
P operator - ( const P p, const P q ) { P u( p.x - q.x, p.y - q.y );
return u; }
bool operator < ( const P p, const P q )
{
return p.x == 0 && p.y == 0 ? 1 : p.x * q.y - p.y * q.x < 0;
}
void Sort ( vector<P> &p, P q )
{
int i, n = p.size() ;
for ( i=0; i<n; i++) p[i] = p[i] - q;
sort ( p.begin(), p.end() );
for ( i=0; i<n; i++) p[i] = p[i] + q;
}
vector<P> GrahamScan ( vector<P> Q )
{
vector<P> S;
P m, u, v, p;
int i, n = Q.size();
m = Q[0];
for ( i=1; i<n; i++ )
if ( Q[i].y < m.y )
m = Q[i];
else if ( Q[i].y == m.y )
if ( Q[i].x < m.x )
m = Q[i];
Sort ( Q, m );
S.push_back ( Q[0] );
S.push_back ( Q[1] );
S.push_back ( Q[2] );
for ( i=3; i<n; i++ )
{
u = S [ S.size () - 2 ];
v = S [ S.size () - 1 ];
p = Q [ i ];
while ( ( p - u ).x * ( v - u ).y - ( p - u ).y * ( v - u ).x
<= 0 )
{
S.pop_back ( );
u = S [ S.size () - 2 ];
v = S [ S.size () - 1 ];
}
S.push_back ( p );
}
return S;
}
Btw, I've read this method from "Introduction to Algorithms" by
Cormen, Leiserson, Rivest (chapter 33). So, if you have this book, I
think you'll understand my code momentarily.
Thanks in advance,
Narek Saribekyan
College "Quantum", Yerevan, Armenia
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
