Блог

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

Например:

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

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

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

Это будет намного быстрее, чем все, что связано с тригонометрией. Сначала даже не нужно нормализовать.

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

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

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

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

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

ostreamamp; operator<<(ostreamamp; os, Pointamp; 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
  

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

 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 элементов. (Спасибо TomSirgedas!)

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

 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. M будет центральной точкой. Это отлично работает, если вы хотите нарисовать какой-то треугольный веер.

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

 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)
  

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

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

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

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

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

 int compareAngles(Point const amp; A, Point const amp; B, Point const amp; 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) amp;amp; (cosA < 0)) ); // 0 for [0,180). 1 for [180,360).
  bool hB = ( (sinB < 0) || ((sinB == 0) amp;amp; (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);
}
  

Если S — это массив точек, а mid — это точка в центре:

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

сортирует список в порядке поворота вокруг середины, начиная с точки, ближайшей к (-inf,0), и идет по часовой стрелке (по часовой стрелке, если вы не ставите отрицательный знак перед математикой).