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

Ответ 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

Ответ 2

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

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

Ответ 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

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

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 degress. Затем вы найдете свой вектор 0 (в позиции N), а std::rotate результаты оставят N элементов. (Спасибо TomSirgedas!)

Ответ 5

Сначала вы должны нормализовать каждый вектор, поэтому каждая точка находится в формате (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)

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

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

Ответ 7

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

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

Внутри каждой половины сравнение может выполняться по правилу правой руки (знак перекрестного произведения), или, другими словами, знак синуса угла между двумя векторами. Если 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);
}

Ответ 8

Если S - это массив PointF, а mid - это PointF в центре:

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

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