Sort points by angle from given axis?

Question

How can I sort an array of points/vectors by counter-clockwise increasing angle from a given axis vector?

For example:

If 0 is the axis vector I would expect the sorted array to be in the order 2, 3, 1.

I'm reasonably sure it's possible to do this with cross products, a custom comparator, and std::sort().

Answer 1

I know this question is quite old, and the accepted answer helped me get to this, still I think I have a more elegant solution which also covers equality (so returns -1 for lowerThan, 0 for equals, and 1 for greaterThan).

It is based on the division of the plane to 2 halves, one from the positive ref axis (inclusive) to the negative ref axis (exclusive), and the other is its complement.

Inside each half, comparison can be done by right hand rule (cross product sign), or in other words - sign of sine of angle between the 2 vectors. If the 2 points come from different halves, then the comparison is trivial and is done between the halves themselves.

For an adequately uniform distribution, this test should perform on average 4 comparisons, 1 subtraction, and 1 multiplication, besides the 4 subtractions done with ref, that in my opinion should be precalculated.

int compareAngles(Point const & A, Point const & B, Point const & ref = Point(0,0)) {
  typedef decltype(Point::x) T;  // for generality. this would not appear in real code.
  const T sinA = A.y - ref.y; // |A-ref|.sin(angle between A and positive ref-axis)
  const T sinB = B.y - ref.y; // |B-ref|.sin(angle between B and positive ref-axis)
  const T cosA = A.x - ref.x; // |A-ref|.cos(angle between A and positive ref-axis)
  const T cosB = B.x - ref.x; // |B-ref|.cos(angle between B and positive ref-axis)

  bool hA = ( (sinA < 0) || ((sinA == 0) && (cosA < 0)) ); // 0 for [0,180). 1 for [180,360).
  bool hB = ( (sinB < 0) || ((sinB == 0) && (cosB < 0)) ); // 0 for [0,180). 1 for [180,360).

  if (hA == hB) {
    // |A-ref|.|B-ref|.sin(angle going from (B-ref) to (A-ref))
    T sinBA = sinA * cosB - sinB * cosA;
    // if T is int, or return value is changed to T, it can be just "return sinBA;"
    return ((sinBA > 0) ? 1 : ((sinBA < 0) ? (-1) : 0));
  }
  return (hA - hB);
}

Answer 2

Most straightforward, but possibly not the optimal way is to shift the cartesian coordinates to be relative to center point and then convert them to polar coordinates. Then just subtract the angle of the "starting vector" modulo 360, and finally sort by angle.

Or, you could make a custom comparator for just handling all the possible slopes and configurations, but I think the polar coordinates are little more transparent.

Answer 3

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

struct Point {
    static double base_angle;
    static void set_base_angle(double angle){
        base_angle = angle;
    }
    double x;
    double y;
    Point(double x, double y):x(x),y(y){}
    double Angle(Point o = Point(0.0, 0.0)){
        double dx = x - o.x;
        double dy = y - o.y;
        double r = sqrt(dx * dx + dy * dy);
        double angle = atan2(dy , dx);
        angle -= base_angle;
        if(angle < 0) angle += M_PI * 2;
        return angle;
    }
};
double Point::base_angle = 0;

ostream& operator<<(ostream& os, Point& p){
    return os << "Point(" << p.x << "," << p.y << ")";
}

bool comp(Point a, Point b){
    return a.Angle() < b.Angle();
}

int main(){
    Point p[] = { Point(-4., -4.), Point(-6., 3.), Point(2., -4.), Point(1., 5.) };
    Point::set_base_angle(p[0].Angle());
    sort(p, p + 4, comp);
    Point::set_base_angle(0.0);
    for(int i = 0;i< 4;++i){
        cout << p[i] << " angle:" << p[i].Angle() << endl;
    }
}

DEMO

Point(-4,-4) angle:3.92699
Point(2,-4) angle:5.17604
Point(1,5) angle:1.3734
Point(-6,3) angle:2.67795

Answer 4

Assuming they are all the same length and have the same origin, you can sort on

struct sorter { 
    operator()(point a, point b) const {  
        if (a.y > 0) { //a between 0 and 180
            if (b.y < 0)  //b between 180 and 360
                return false;
            return a.x < b.x; 
        } else { // a between 180 and 360
            if (b.y > 0) //b between 0 and 180
                return true;
            return a.x > b.x;
        }
    }
    //for comparison you don't need exact angles, simply relative.
}

This will quickly sort them from 0->360 degress. Then you find your vector 0 (at position N), and std::rotate the results left N elements. (Thanks TomSirgedas!)

Answer 5

You should first normalize each vector, so each point is in (cos(t_n), sin(t_n)) format. Then calculating the cos and sin of the angles between each points and you reference point. Of course:

cos(t_n-t_0)=cos(t_n)cos(t_0)+sin(t_n)sin(t_0)  (this is equivalent to dot product)
sin(t_n-t_0)=sin(t_n)cos(t_0)-cos(t_n)sin(t_0)

Only based on both values, you can determine the exact angles (-pi to pi) between points and reference point. If just using dot product, clockwise and counter-clockwise of same angle have same values. One you determine the angle, sort them.

Answer 6

If S is an array of PointF, and mid is the PointF in the centre:

S = S.OrderBy(s => -Math.Atan2((s.Y - mid.Y), (s.X - mid.X))).ToArray();

will sort the list in order of rotation around mid, starting at the point closest to (-inf,0) and go ccw (clockwise if you leave out the negative sign before Math).