इस ट्यूटोरियल में, हम दी गई बिंदुओं के सेट का कन्वेक्स हल ढूंढने के लिए एक प्रोग्राम पर चर्चा करेंगे।
कन्वेक्स हल सबसे छोटा बहुभुज उत्तल आकृति है जो सभी दिए गए बिंदुओं को या तो सीमा पर या आकृति के अंदर समाहित करता है।
ग्राहम स्कैन में, पहले बिंदुओं को सॉर्ट किया जाता है ताकि सबसे नीचे का बिंदु मिल सके। फिर बिंदुओं को क्रम में पार किया जाता है और उनके क्रम के आधार पर सीमा पर होने के लिए अस्वीकार या स्वीकार किया जाता है।
उदाहरण
#include <iostream> #include <stack> #include <stdlib.h> using namespace std; struct Point{ int x, y; }; //अन्य बिंदुओं को सॉर्ट करने के लिए संदर्भ बिंदु Point p0; //स्टैक में अगले टॉप पर जाना Point nextToTop(stack<Point> &S){ Point p = S.top(); S.pop(); Point res = S.top(); S.push(p); return res; } //दो बिंदुओं को स्वैप करना int swap(Point &p1, Point &p2){ Point temp = p1; p1 = p2; p2 = temp; } //अंतर के वर्ग की गणना int distSq(Point p1, Point p2){ return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y); } //बिंदुओं के ओरिएंटेशन की जांच int orientation(Point p, Point q, Point r){ int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y); if (val == 0) return 0; return (val > 0)? 1: 2; } //बिंदुओं को सॉर्ट और तुलना करना int compare(const void *vp1, const void *vp2){ Point *p1 = (Point *)vp1; Point *p2 = (Point *)vp2; int o = orientation(p0, *p1, *p2); if (o == 0) return (distSq(p0, *p2) >= distSq(p0, *p1))? -1 : 1; return (o == 2)? -1: 1; } //कन्वेक्स हल प्रिंट करना void convexHull(Point points[], int n){ int ymin = points[0].y, min = 0; for (int i = 1; i < n; i++){ int y = points[i].y; if ((y < ymin) || (ymin == y && points[i].x < points[min].x)) ymin = points[i].y, min = i; } swap(points[0], points[min]); p0 = points[0]; qsort(&points[1], n-1, sizeof(Point), compare); for (int i=1; i<n; i++){ while (i < n-1 && orientation(p0, points[i], points[i+1]) == 0) i++; points[m] = points[i]; m++; //संशोधित सरणी का आकार अपडेट करना } if (m < 3) return; stack<Point> S; S.push(points[0]); S.push(points[1]); S.push(points[2]); for (int i = 3; i < m; i++){ while (orientation(nextToTop(S), S.top(), points[i]) != 2) S.pop(); S.push(points[i]); } while (!S.empty()){ Point p = S.top(); cout << "(" << p.x << ", " << p.y <<")" << endl; S.pop(); } } int main(){ Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4}, {0, 0}, {1, 2}, {3, 1}, {3, 3}}; int n = sizeof(points)/sizeof(points[0]); convexHull(points, n); return 0; }आउटपुट
(0, 3) (4, 4) (3, 1) (0, 0)