Sortowanie punktów według kąta z danej osi?

Question

Jak mogę posortować tablicę punktów/wektorów pod kątem zwiększającym kąt przeciwny do ruchu wskazówek zegara z danego wektora osi?

Na przykład

Jeśli 0 jest wektorem osi byłoby oczekiwać, posortowanej tablicy być rzędu 2, 3, 1.

Jestem dość pewny, że można to zrobić z produktami krzyżowymi, niestandardowym komparatorem i std::sort().

Answer 1

Tak, można to zrobić za pomocą niestandardowego komparatora opartego na produkcie krzyżowym. Jedynym problemem jest to, że naiwny komparator nie będzie miał własności przechodniości. Konieczny jest więc dodatkowy krok, aby zapobiec uważaniu kątów po obu stronach odniesienia za uważanych za bliskie.

To będzie DUŻO szybsze niż wszystko, co dotyczy trig. Najpierw nie ma potrzeby normalizacji.

Oto komparator:

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

Answer 2

Najprostszym, ale prawdopodobnie nie optymalnym sposobem jest przesunięcie współrzędnych kartezjańskich w stosunku do punktu środkowego, a następnie convert them to polar coordinates. Następnie odejmij kąt "wektora startowego" modulo 360, a na końcu sortuj według kąta.

Można też utworzyć niestandardowy komparator do obsługi wszystkich możliwych nachyleń i konfiguracji, ale myślę, że współrzędne biegunowe są trochę bardziej przezroczyste.

Answer 3

Zakładając, że wszystkie są tej samej długości i mają to samo pochodzenie można sortować na

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

Ten szybko posortować je od 0-> 360 degress. Następnie znajdujesz swój wektor 0 (w pozycji N) i std::rotate, wyniki pozostawiły N elementów. (Dzięki TomSirgedas!)

Answer 4

Powinieneś najpierw normalizować każdy wektor, aby każdy punkt był w formacie (cos (t_n), sin (t_n)). Następnie oblicza się kąty między punktami i punktem odniesienia. Przedmiotu:

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) 

Tylko w oparciu o obie wartości, można określić dokładne kąty (PI PI) pomiędzy punktami i punktu odniesienia. Jeśli używasz tylko produktu kropkowego, to zgodnie z ruchem wskazówek zegara i przeciwnie do tego samego kąta mają te same wartości. Jeden określasz kąt, sortuj je.

Answer 5

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

Jest to przykład tego, jak pojechałem na temat rozwiązywania tego. Konwertuje się na biegunowy, aby uzyskać kąt, a następnie służy do ich porównania.Powinieneś być w stanie wykorzystać to w funkcji sortowania tak:

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

Poniżej znajduje się kod do porównywania

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

Wykorzystuje SFML bibliotekę, ale można przełączyć każdą klasę wektor/punkt zamiast sf :: Vector2f. M będzie punktem centralnym. Działa świetnie, jeśli chcesz narysować jakiegoś wentylatora trójkąta.

Answer 7

Wiem, że to pytanie jest dość stare, a zaakceptowana odpowiedź pomogła mi to osiągnąć, wciąż myślę, że mam bardziej eleganckie rozwiązanie, które obejmuje również równość (tak zwraca -1 dla niższegoTana, 0 dla równych i 1 dla Lepszy niż).

Oparta jest na podziale płaszczyzny na 2 połówki, jedną z dodatniej osi refowania (włącznie) na ujemną oś ref (wyłącznie), a druga jest jej dopełnieniem.

Wewnątrz każdej połówki porównania można dokonać za pomocą reguły prawej ręki (znak krzyża produktu) lub innymi słowy - znaku sinusa kąta między 2 wektorami. Jeśli 2 punkty pochodzą z różnych połówek, porównanie jest proste i odbywa się między samymi połówkami.

Dla odpowiednio jednolitej dystrybucji, test ten powinien wykonywać średnio 4 porównania, 1 odejmowanie i 1 mnożenie, oprócz 4 odejmowań wykonanych przy pomocy ref, które według mnie powinny być wstępnie obliczone.

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