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

Answer 3

(B)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?

I suggest you avoid messy floating point arithmetic. As exercise 33.1-3 of the same book points out, you can simply sort by polar angle using cross products. Here is how to do it:

struct Point {int x,y;}

int operator^(Point p1, Point p2) {return p1.x*p2.y - p1.y*p2.x;}

Point p0; //set this separately

bool operator<(Point p1, Point p2) 
{
    p1=p1-p0; p2=p2-p0; 
    if(p1.y==0&&p1.x>0) return true; //angle of p1 is 0, thus p2>p1
    if(p2.y==0&&p2.x>0) return false; //angle of p2 is 0 , thus p1>p2
    if(p1.y>0&&p2.y<0) return true; //p1 is between 0 and 180, p2 between 180 and 360
    if(p1.y<0&&p2.y>0) return false;
    return (p1^p2)>0; //return true if p1 is clockwise from p2
}

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

If p0, pi and pj are collinear, only the farthest one from p0, may be part of the convex hull. Thus, we should remove the other points. We can do this in C++. Start by defining the dot product,

int operator*(Point p1, Point p2) {return p1.x*p2.x + p1.y*p2.y;}

and adding this line to the comparator:

if((p1^p2)==0&&p1*p2>0) return p1*p1<p2*p2;

Now in case of same angle, the points will be sorted by distance from p0. Now we can use the unique function from the STL to remove the points as required from vector<Point> P:

sort(P.begin(),P.end());
P.erase(unique(P.begin(),P.end(),eq),P.end());

Here, the eq function returns true if the points have the same angle.

bool eq(Point p1, Point p2) 
{
    p1=p1-p0; p2=p2-p0;
    return ((p1^p2)==0&&p1*p2>0); 
}