按指定軸的角度排序？

Question

如何從給定的軸向量逆時針增加角度來排列點/向量的數組？

例如：

如果0是軸矢量我期望排序後的數組是在順序2, 3, 1。

我相當肯定可以用交叉產品，自定義比較器和std::sort()來做到這一點。

Answer 1

是的，您可以使用基於交叉產品的自定義比較器來實現。唯一的問題是一個天真的比較器不具備傳遞特性。因此需要額外的步驟，以防止參考的任何一側被視爲關閉。

這將比任何涉及trig更快。甚至沒有必要先進行標準化。

這裏的比較：

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

最直接的，但可能不是最佳的方式是將笛卡爾座標移到相對於中心點，然後convert them to polar coordinates。然後，減去「起始矢量」模數360的角度，最後按角度排序。或者，你可以製作一個自定義的比較器來處理所有可能的斜率和配置，但我認爲極座標稍微透明一些。

Answer 3

假設他們都是相同的長度，並且具有相同的起源，可以排序

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！）

Answer 4

您應該首先對每個向量進行歸一化，因此每個點都以（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到pi）。如果僅使用點積，則相同角度的順時針和逆時針具有相同的值。你可以確定角度，對它們進行分類。

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

這是我如何着手解決這樣的一個例子。它轉換爲極座標來獲得角度，然後用於比較它們。你應該能夠在一個排序函數使用這個像這樣：

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庫，但你可以切換任何矢量/點類，而不是科幻:: Vector2f。 M將是中心點。如果你想繪製某種三角形風扇，它會很好用。

Answer 7

我知道這個問題是相當古老的，接受的答案幫助我得到這個，我仍然認爲我有一個更優雅的解決方案，也涵蓋了平等（所以lowerThan返回-1，等於0返回1，比...更棒）。

它是基於平面的分割爲2半，一個從正參考軸線（含）到負參考軸線（不含），和另一種是它的互補物。

內部各佔一半，比較可以通過右手法則（叉積符號），或者換句話說做 - 2個矢量之間角度的正弦的跡象。 如果2點來自不同的一半，那麼比較是微不足道的，並在兩半之間完成。

對於充分均勻分佈，這種測試應在平均4個比較執行，1個減法和乘法1，除了用參考所做的4個減法，在我的意見，應預先計算。

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