Sort points by angle from given axis?

问题:

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().

回答1:

Yes, you can do it with a custom comparator based on the cross-product. The only problem is that a naive comparator won't have the transitivity property. So an extra step is needed, to prevent angles either side of the reference from being considered close.

This will be MUCH faster than anything involving trig. There's not even any need to normalize first.

Here's the comparator:

class angle_sort
{
    point m_origin;
    point m_dreference;

    // z-coordinate of cross-product, aka determinant
    static double xp(point a, point b) { return a.x * b.y - a.y * b.x; }
public:
    angle_sort(const point origin, const point reference) : m_origin(origin), m_dreference(reference - origin) {}
    bool operator()(const point a, const point b) const
    {
        const point da = a - m_origin, db = b - m_origin;
        const double detb = xp(m_dreference, db);

        // nothing is less than zero degrees
        if (detb == 0 && db.x * m_dreference.x + db.y * m_dreference.y >= 0) return false;

        const double deta = xp(m_dreference, da);

        // zero degrees is less than anything else
        if (deta == 0 && da.x * m_dreference.x + da.y * m_dreference.y >= 0) return true;

        if (deta * detb >= 0) {
            // both on same side of reference, compare to each other
            return xp(da, db) > 0;
        }

        // vectors "less than" zero degrees are actually large, near 2 pi
        return deta > 0;
    }
};

Demo: http://ideone.com/YjmaN

回答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.

回答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

回答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!)

回答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.

回答6:

This is an example of how I went about solving this. It converts to polar to get the angle and then is used to compare them. You should be able to use this in a sort function like so:

std::sort(vectors.begin(), vectors.end(), VectorComp(centerPoint));

Below is the code for comparing

struct VectorComp : std::binary_function<sf::Vector2f, sf::Vector2f, bool>
{

    sf::Vector2f M;
    IntersectComp(sf::Vector2f v) : M(v) {}

    bool operator() ( sf::Vector2f o1,  sf::Vector2f o2)
    {
        float ang1     = atan( ((o1.y - M.y)/(o1.x - M.x) ) * M_PI / 180);
        float ang2     = atan( (o2.y - M.y)/(o2.x - M.x) * M_PI / 180);
        if(ang1 < ang2) return true;
        else if (ang1 > ang2) return false;
        return true;
    }
};

It uses sfml library but you can switch any vector/point class instead of sf::Vector2f. M would be the center point. It works great if your looking to draw a triangle fan of some sort.

回答7:

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

回答8:

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).