Сортировать точки по углу от заданной оси?

Question

Как можно отсортировать массив точек / векторов по возрастанию угла против часовой стрелки от заданного вектора оси?

Например:

Если0 - это вектор оси. Я ожидаю, что отсортированный массив будет иметь порядок 2, 3, 1.

Я вполне уверен, что это можно сделать с помощью перекрестных продуктов, пользовательского компаратора и std::sort().

Answer 1

Да, вы можете сделать это с помощью специального компаратора на основе перекрестного продукта.Единственная проблема заключается в том, что наивный компаратор не будет обладать свойством транзитивности.Таким образом, необходим дополнительный шаг, чтобы не допустить, чтобы углы по обе стороны от эталона считались близкими.

Это будет НАМНОГО быстрее, чем что-либо, включающее триггер.Нет даже необходимости сначала нормализовать.

Вот компаратор:

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

Демо: http://ideone.com/YjmaN

Answer 2

Самый простой, но, возможно, не оптимальный способ - сдвинуть декартовы координаты относительно центральной точки, а затем преобразовать их в полярные координаты . Затем просто вычтите угол «начального вектора» по модулю 360 и, наконец, отсортируйте по углу.

Или вы можете создать собственный компаратор для обработки всех возможных уклонов и конфигураций, но я думаю, что полярные координаты немного прозрачнее.

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

ДЕМО

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

Предполагая, что они все одинаковой длины и имеют одинаковое происхождение, вы можете отсортировать по

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

Это быстро отсортирует их от 0 до> 360 градусов. Затем вы найдете ваш вектор 0 (в позиции N), а std::rotate в результате осталось N элементов. (Спасибо, ТомСиргедас!)

Answer 5

Я знаю, что этот вопрос довольно старый, и принятый ответ помог мне в этом разобраться, но я думаю, что у меня есть более элегантное решение, которое также охватывает равенство (поэтому возвращает -1 для lowerThan, 0 для equals и 1 для большееThan).

Он основан на делении плоскости на две половины, одну от положительной оси отсчета (включительно) до отрицательной оси отсчета (исключая), а другая является ее дополнением.

Внутри каждой половины сравнение может быть выполнено по правилу правой руки (знак перекрестного произведения) или, другими словами, по знаку синуса угла между двумя векторами.Если 2 точки получены из разных половин, то сравнение является тривиальным и проводится между самими половинами.

Для достаточно равномерного распределения этот тест должен выполнить в среднем 4 сравнения, 1 вычитание и 1 умножение,кроме 4 вычитаний, сделанных с помощью ref, которые, по моему мнению, должны быть рассчитаны заранее.

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 6

Это пример того, как я решил эту проблему.Он преобразуется в полярный, чтобы получить угол, а затем используется для их сравнения.Вы должны иметь возможность использовать это в функции сортировки следующим образом:

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

Ниже приведен код для сравнения

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

Он использует библиотеку sfml, но вы можете переключать любой вектор / точкукласс вместо sf :: Vector2f.М будет центральной точкой.Это прекрасно работает, если вы хотите нарисовать какой-нибудь треугольник веера.

Answer 7

Сначала необходимо нормализовать каждый вектор, чтобы каждая точка имела формат (cos (t_n), sin (t_n)).Тогда вычисление соз и грех углов между каждыми точками и вы ссылаетесь точкой.Конечно:

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)

Только на основе обоих значений, вы можете определить точные углы (-pi пи) между точками и точкой отсчета.Если просто использовать точечное произведение, то по часовой стрелке и против часовой стрелки одинаковый угол имеют одинаковые значения.Один вы определяете угол, сортируйте их.