डेटा स्ट्रक्चर में कन्वेक्स हल उदाहरण

यहां हम कन्वेक्स हल पर एक उदाहरण देखेंगे। मान लीजिए हमारे पास पॉइंट्स का एक सेट है। हमें कम मात्रा में पॉइंट्स लेकर एक पॉलीगॉन बनाना है जो सभी दिए गए पॉइंट्स को कवर करे। इस खंड में हम जार्विस मार्च एल्गोरिदम देखेंगे ताकि कन्वेक्स हल प्राप्त किया जा सके।

जार्विस मार्च एल्गोरिदम का उपयोग दिए गए डेटा पॉइंट्स के सेट से कन्वेक्स हल के कॉर्नर पॉइंट्स का पता लगाने के लिए किया जाता है।

डेटा सेट के सबसे बाएं पॉइंट से शुरू करके, हम पॉइंट्स को कन्वेक्स हल में एंटी-क्लॉकवाइज रोटेशन द्वारा रखते हैं। वर्तमान पॉइंट से, हम उन पॉइंट्स के ओरिएंटेशन की जांच करके अगला पॉइंट चुन सकते हैं। जब कोण सबसे बड़ा होता है, तो पॉइंट चुना जाता है। सभी पॉइंट्स पूरे होने पर, जब अगला पॉइंट शुरुआती पॉइंट होता है, तो एल्गोरिदम रोक दें।

इनपुट - पॉइंट्स का सेट: {(-7,8), (-4,6), (2,6), (6,4), (8,6), (7,-2), (4,-6), (8,-7),(0,0), (3,-2),(6,-10),(0,-6),(-9,-5),(-8,-2),(-8,0),(-10,3),(-2,2),(-10,4)}

आउटपुट - कन्वेक्स हल के बाउंड्री पॉइंट्स हैं:

(-9, -5) (6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3)

एल्गोरिदम

findConvexHull(points, n) इनपुट: पॉइंट्स, पॉइंट्स की संख्या। आउटपुट: कन्वेक्स हल के कॉर्नर पॉइंट्स। Begin    start := points[0]    for each point i, do       if points[i].x < start.x, then // बाएं सबसे पॉइंट प्राप्त करें          start := points[i]    done    current := start    start पॉइंट को रिजल्ट सेट में जोड़ें।    colPts सेट को परिभाषित करें कोलिनियर पॉइंट्स स्टोर करने के लिए    while true, do // अनंत लूप शुरू करें       next := points[i]       0th पॉइंट को छोड़कर सभी पॉइंट्स i के लिए, do          if points[i] = current, then             अगले भाग को छोड़ें, अगले इटरेशन के लिए जाएं          val := current, next, points[i] का क्रॉस प्रोडक्ट          if val > 0, then             next := points[i]             colPts सरणी को क्लियर करें          else if val = 0, then             if next, current की तुलना में points[i] के करीब है, then                next को colPts में जोड़ें                next := points[i]             else                points[i] को colPts में जोड़ें       done       colPts में सभी आइटम्स को रिजल्ट में जोड़ें       if next = start, then          लूप तोड़ें       next को रिजल्ट में इन्सर्ट करें       current := next    done    return result End

उदाहरण

#include<iostream> #include<set> #include<vector> using namespace std; struct point{ //2d प्लेन के लिए पॉइंट्स परिभाषित करें    int x, y;    bool operator==(point p2){       if(x == p2.x && y == p2.y)          return 1;       return 0;    }    bool operator<(const point &p2)const{ //सेट में सॉर्ट करने के लिए डमी तुलना फ़ंक्शन       return true;    } }; int crossProduct(point a, point b, point c){ //ab वेक्टर से c का स्थान ढूंढता है    int y1 = a.y - b.y;    int y2 = a.y - c.y;    int x1 = a.x - b.x;    int x2 = a.x - c.x;    return y2*x1 - y1*x2; //यदि परिणाम < 0, c बाएं में, > 0, c दाएं में, = 0, a,b,c कोलिनियर हैं } int distance(point a, point b, point c){    int y1 = a.y - b.y;    int y2 = a.y - c.y;    int x1 = a.x - b.x;    int x2 = a.x - c.x;    int item1 = (y1*y1 + x1*x1);    int item2 = (y2*y2 + x2*x2);    if(item1 == item2)       return 0; //जब b और c, a से समान दूरी पर हैं    else if(item1 < item2)       return -1; //जब b, a के करीब है    return 1; //जब c, a के करीब है } set<point> findConvexHull(point points[], int n){    point start = points[0];    for(int i = 1; i 0){ //जब ith पॉइंट बाएं तरफ है             nextTarget = points[i];             collinearPoints = new vector<point>; //कोलिनियर पॉइंट्स रीसेट करें           }else if(val == 0){ //यदि तीन पॉइंट्स कोलिनियर हैं             if(distance(current, nextTarget, points[i]) < 0){ //करीब वाले को कोलिनियर लिस्ट में जोड़ें                collinearPoints->push_back(nextTarget);                nextTarget = points[i];             }else{                collinearPoints->push_back(points[i]); //जब ith पॉइंट nextTarget के करीब या समान है             }          }       }       vector<point>::iterator it;       for(it = collinearPoints->begin(); it != collinearPoints->end(); it++){          result.insert(*it); //कोलिनियर पॉइंट्स में सभी पॉइंट्स को रिजल्ट सेट में जोड़ें       }       if(nextTarget == start) //जब अगला पॉइंट शुरू है तो इसका मतलब है, क्षेत्र कवर हो गया          break;       result.insert(nextTarget);       current = nextTarget;    }    return result; } int main(){    point points[] = {       {-7,8},{-4,6},{2,6},{6,4},{8,6},{7,-2},{4,-6},{8,-7},{0,0},       {3,-2},{6,-10},{0,-6},{-9,-5},{-8,-2},{-8,0},{-10,3},{-2,2},{-10,4}};       int n = 18;       set<point> result;       result = findConvexHull(points, n);       cout << "Boundary points of convex hull are: "<<endl;       set<point>::iterator it;       for(it = result.begin(); it!=result.end(); it++)          cout << "(" << it->x << ", " <<it->y <<") "; }

आउटपुट

Boundary points of convex hull are: (-9, -5) (6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3)