Convex Hull Sorting Step

Question

I was Reading the Graham Scan Algorithm to Find the convex Hull From CLRS. The algorithm given in CLRS for Convex hull is ::

I am not able to understand this line (step 2 of the algorithm):

If two or more points have the same polar angle relative to p0, all but the farthest such point are convex combinations of p0 and the farthest point, and so we remove them entirely from consideration.

1. What does this mean? What should I do if more than one points have the same polar angle with respect to Po?

Also Lets say, I had made a structure

struct points
{
    int x, y;
} P[10000];

2. How should I implement the sorting step using the C++ STL library? I mean, how should I define the comparator function in sort(P+1, P+N, comparator)?

Answer 1

What does this mean,what should i do if more than one points have the same polar angle with respect to Po?

Let's say P₀ is (0,0), P₁ is (1,1) and P₂ is (2,2). Now P₁ and P₂ have the same angle relative to P₀, in which case you discard P₁. If there are more point between P₀ and P₂ with the same angle, discard all except P₂ (and P₀ of course).

How should i implement the sorting step using C++ STL (sort function in Algorithm ) Library?Especially i mean sort(P+1,P+N,comparator). How should I define the comparator function?

Not really familiar with C++ (STL), but check if it has a atan2 function you can use. Also see: Find angle between two points, respective to horizontal axis? and How to calculate the angle between a line and the horizontal axis?

Answer 2

Here is my implementation for gharam scan algorithm for convex hull in C++

struct vert
{
    int x,y;
    float rad;
    int idx;
};    
bool operator<(const vert &a,const vert &b)//this is the function u are looking for
{
    if(a.rad<b.rad)
        return true;
    if(a.rad==b.rad)
    {
        if(a.y>b.y)
            return true;
        else if(a.y==b.y&&a.x>b.x)
            return true;
        else
            return false;
    }
    return false;
}    
vert operator-(vert x,vert y)
{
    vert tmp;
    tmp.x=x.x-y.x;
    tmp.y=x.y-y.y;
    return tmp;
}
double dist(vert a,vert b)
{
    vert ab=b-a;
    return sqrt(ab.x*ab.x+ab.y*ab.y);
}
int cross(vert a,vert b,vert c)
{
    vert ab,bc;
    ab=b-a;
    bc=c-b;
    return ab.x*bc.y-ab.y*bc.x;
}
int main()
{
    int t,i,j,k,n;
    //("example.txt","r",stdin);
    scanf("%d",&t);
    vert a[100009],point[100009];
    int kx,ky;
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&a[i].x,&a[i].y);
            a[i].idx=i+1;
        }
        vert d;
        d=a[0];
        for(i=1;i<n;i++)
        {
            if(a[i].y<d.y)
                d=a[i];
            else if(a[i].y==d.y&&a[i].x<d.x)
                d=a[i];
        }
        vector<vert> v;
        for(i=0;i<n;i++)
        {
            kx=a[i].x-d.x;
            ky=a[i].y-d.y;
            if(kx==0&&ky==0)
                continue;
            a[i].rad=atan2(kx,ky)*-1.00;
            v.push_back(a[i]);
        }
        sort(v.begin(),v.end());
        float rad=-10000;
        j=0;
        for(i=0;i<v.size();i++)
        {
            if(v[i].rad!=rad)
            {
                a[j++]=v[i];
                rad=v[i].rad;
            }
        }
        k=0;
        point[k++]=d;
        for(i=0;i<j;i++)
        {
            if(k<=1)
                point[k++]=a[i];
            if(cross(point[k-2],point[k-1],a[i])>0)
            {
                point[k++]=a[i];
            }
            else
            {
                do
                {
                    k--;
                    if(cross(point[k-2],point[k-1],a[i])>0)
                        break;
                }while(k>1);
                point[k++]=a[i];
            }
        }
        double dis=0;
        for(i=1;i<k;i++)
            dis+=dist(point[i],point[i-1]);
        dis+=dist(point[0],point[k-1]);
        printf("%0.2f\n",dis);
        for(i=0;i<k;i++)
            printf("%d ",point[i].idx);
        cout<<endl<<endl;;
    }
    return 0;
}

either u can use the comparator function or u can overload the operator< as I have done here. This will work similarly but now u dont have to pass any comparator function as the third argument in sort() function

I hope this helps