Hey everyone!

I have now bumped into several geometry problems that require clockwise 2D point sorting relative to a specific center, here is an example. It is not such a hard task, you just need to overload a comparator and use any kind of sort, like heapsort or quicksort. This comparator can be done with simple cross and dot product.

However, I noticed it can be a little more tedious than it seems. Since there can be a point straight above your center or straight underneath it, cross product isn't so reliable. Therefore, one might go on and start writing many if's in the comparator for such cases, making the code get annoyingly long.

I took my time to search on the internet for some short, clever comparator function for this problem, but all I found were long and ugly. This is why I decided to write this blog, to explain a powerful, yet simple and easy-to-remember way to solve this task.

To explain my approach, I will use my Vector template. Here it is. It only includes dot product and z-coordinate of cross product, since that's the only two functions we will be needing.

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

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.