I have now bumped into several geometry problems that require clockwise 2D point sorting relative to a specific center, here is an example. The key to solving this task is to implement a comparator function, with this header:

bool operator<(const Point &a, const Point &b);

The function should return true iff Point a goes before Point b in counter-clockwise order. If we correctly implement this function, we can do countless things, such as sorting points, handling sets and maps of points, applying binary search, etc.

I have researched and found out there is not really a simple, short, easy-to-remember implementation for this function out there. That's why I decided to share mine in this blog.

First of all, you obviously need a Point template. If you aren't familiar with this, read this blog.

I only included dot product and z-coordinate of cross product, since that's the only two functions we will be needing.

struct Point{
    ll x, y;
    Point(){}
    Point(ll x, ll y): x(x), y(y){}
};

ll operator%(const Point &a, const Point &b){//z-coordinate of cross product
    return a.x * b.y - a.y * b.x;
}
ll operator*(const Point &a, const Point &b){//dot product
    return a.x * b.x + a.y * b.y;

These functions are basic in geometry. Now, without loss of generality, suppose our center is the origin (0, 0) (if not, just make points relative to your center). We also need a starting reference, since points could be all around the center. Let's call this point u, and suppose it's value is (0, 1) (again, without loss of generality).

This is what you need:

const Point u(0, 1);
bool A(const Point &p){
    return u % p > 0 || (u % p == 0 && u * p > 0);
}
bool operator<(const Point &a, const Point &b){
    return (A(a) == A(b) && a % b > 0) || (A(a) && !A(b));
}

That's it. Those two one-liners will work correctly for any two points different than the origin.

Hope it was helpful. Happy coding!

Conceptual notes

First of all, let's define ($S) as the set of points to be sorted counter-clockwisely. Without loss of generality, let's suppose we are to sort them with respect to the origin ($O(0, 0)). Now, since points can be all around ($O), we need a starting reference ($u). This can be any point other than the origin. Again, without loss of generality, assume ($u=(0, 1)).

Now, let's divide the plane into two segments ($A) and ($B) in the following way:

($A) includes points on the left side of ($u), and also those which are collinear to and pointing in the same direction as ($u). On the other hand, ($B) includes points on the right side of ($u) and those collinear to ($u) but pointing in the opposite direction.

Also note ($A) and ($B) are excluding and exhaustive. That is, any point other than the origin will belong to exactly one of them.

So given a point ($p, p ≠ (0, 0)), it belongs to ($A) only if one of the following condition is met:

• ($u x p) > 0
• ($u x p = 0) and ($u · p > 0)

The first condition is true if ($p) is on the left side of ($u). The second is true if it is collinear to and points in the same direction as ($u).

This can be easily coded. Here is my Vector class with all the methods needed right now. % operator is for magnitude of cross product and * is for dot product.

struct Vector{
    ll x, y;
    Vector(){}
    Vector(ll x, ll y): x(x), y(y){}
};

ll operator%(const Vector & a, const Vector & b){
    return a.x * b.y - a.y * b.x;
}
ll operator*(const Vector &a, const Vector &b){
    return a.x * b.x + a.y * b.y;
}
const Vector u(0, 1);

//Here is the function:

bool A(const Vector &p){
    return u % p > 0 || (u % p == 0 && u * p > 0);
}

We don't need a function for ($B), if it doesn't belong to ($A) it consequently belongs to ($B).

So going back to our comparing function, we must tell if for two given points ($c) and ($d), ($c < d). This happens only if one of the following is true:

• ($c) is in segment ($A) and ($d) is in segment ($B)
• ($c) and ($d) are in the same segment, and ($c x d > 0).

First condition is obvious, since we are sorting in counter-clockwise order. The second condition holds because if they are in the same segment, the smallest angle between them is also inside that segment. So just check with simple cross product if ($c) is before ($d). The final code will look like this:

struct Vector{
    ll x, y;
    Vector(){}
    Vector(ll x, ll y): x(x), y(y){}
};

ll operator%(const Vector & a, const Vector & b){
    return a.x * b.y - a.y * b.x;
}
ll operator*(const Vector &a, const Vector &b){
    return a.x * b.x + a.y * b.y;
}
const Vector u(0, 1);
bool A(const Vector &p){
    return u % p > 0 || (u % p == 0 && u * p > 0);
}
bool operator<(const Vector &a, const Vector &b){
    return (A(a) == A(b) && a % b > 0) || (A(a) && !A(b));
}

That's it. This one-liner function will not only help sort a point array, it can be used for binary searching, for sets and maps of points, and countless other data structures. Furthermore, if we want to sort by a center which is not the origin, we can subtract the center and then apply algorithm. If we want our starting point ($u) to be a specific point, just change the value in the code. If we want to sort in clockwise direction rather than counter-clockwise, just sort and then reverse.