Sorting and comparing 2D points in counter-clockwise order

Revision en3, by eidan, 2018-03-31 01:55:54

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 (with a defined center-point). 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!

Tags #geometry

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English eidan 2018-03-31 01:55:54 3489 Tiny change: 'wise order.\nIf we c' -> 'wise order (with a defined center-point).\nIf we c' (published)
en2 English eidan 2018-03-31 01:51:02 1779 Tiny change: ' blog.\n\nTo explain my approach, you obvi' -> ' blog.\n\nFirst of all, you obvi'
en1 English eidan 2018-03-30 23:16:34 4952 Initial revision (saved to drafts)