दिए गए अक्ष से कोण द्वारा क्रमबद्ध अंक?

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

सबसे सरल, लेकिन संभावित रूप से इष्टतम तरीका नहीं है कि कार्टेसियन निर्देशांक केंद्र बिंदु से संबंधित हो और फिर 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 degress सॉर्ट होगा। फिर आप अपने वेक्टर 0 (स्थिति एन पर), और std::rotate परिणाम एन तत्वों को छोड़ दिया। (धन्यवाद TomSirgedas!)

Answer 4

आपको पहले प्रत्येक वेक्टर को सामान्य बनाना चाहिए, इसलिए प्रत्येक बिंदु (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) निर्धारित कर सकते हैं। यदि केवल डॉट उत्पाद का उपयोग करते हैं, तो घड़ी के समान और समान कोण के विपरीत दिशा में समान मान होते हैं। एक आप कोण निर्धारित करते हैं, उन्हें सॉर्ट करें।

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

डेमो

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। एम केंद्र बिंदु होगा। यदि आप किसी प्रकार के त्रिभुज प्रशंसक को आकर्षित करना चाहते हैं तो यह बहुत अच्छा काम करता है।

Answer 7

मुझे पता है कि यह प्रश्न काफी पुराना है, और स्वीकार्य उत्तर ने मुझे यह करने में मदद की, फिर भी मुझे लगता है कि मेरे पास एक और अधिक सुरुचिपूर्ण समाधान है जो समानता को कवर करता है (इसलिए लोअरहान के लिए रिटर्न -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); 
}