convex hull code of "competitive programming 1"

Question

I'm trying to understand the "convex hull" algorithm in Steven Halim and Felix Halim's book Competitive Programming. The "convex hull" problem is, given a collection P of n points in a plane, to find a subset CH(P) that forms the vertices of a convex polygon containing all the other points. Here's an image outlining their approach:

Their algorithm starts by sorting the points based on their angle with respect to a "pivot", namely, the bottommost and rightmost point in P.

I am having some problems understanding their angle_comp function — what it does, and what its purpose is. Can anyone help me to understand it?

typedef struct {
    double x, y ;
} point;

point pivot;

// A function to compute the distance between two points:
double dist2 (point a, point b) 
{
    double dx = a.x - b.x ;
    double dy = a.y - b.y ;
    return sqrt (dx *dx + dy * dy) ;
}

// A function to compare the angles of two points with respect to the pivot:
bool angle_comp (point a, point b)
{
    if (fabs(area2(pivot, a, b) - 0) < 10e-9)
        return dist2(pivot, a) < dist2(pivot, b);

    int d1x = a.x - pivot.x, d1y = a.y - pivot.y;
    int d2x = b.x - pivot.x, d2y = b.y - pivot.y; 
    return (atan2((double) d1y, (double) d1x)
               - atan2 ((double) d2y, (double)d2x))
             < 0;
}

Answer 1

If I understand your question correctly, you want to know why the sort function is important? It is because your code there uses Graham's scan, a method for finding the convex hull. In order for Graham's scan to be more efficient, the points must be sorted by their angle relative to a fixed point.

The angle_comp function compares the angles of the two points A and B relative to the pivot point. This function, when plugged into std::sort, allows us to sort all the points around the pivot based on their angle relative to or distance from the pivot.

For two points A and B around a pivot. If point A and B have the same angle, or if one of the other both are near the pivot, than we need an alternative way to sort the two points. We sort the points by their distance from the pivot instead.

Else, we find out where the point A and B are relative to our pivot. We do this by subtracting the pivot from our points. So if for instance, our pivot is (4, 3) and A is (5, 7), than A is 1 unit right and 4 units up from our pivot. If our pivot is (0, 0), than A would be (1, 4). Hopefully that's understandable.

After we have the relative point, which is D, we than calculate the angle of the point relative to our pivot, or origin. atan2 takes two parameters, the y-value of our point, and the x-value of our point, and spits out the angle of our point in radians. For atan2, 0 radians is defined as any point (N, 0) away from the origin, and as the radians increase, the point goes counter-clockwise around the pivot, or origin.

We then subtract the angle of D, away from the angle of D2. If the angle of D2 is greater than the angle of D1, we return with true, and std::sort can use that returned data to sort the angles counter-clockwise.