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;
}