इस ट्यूटोरियल में, हम जार्विस एल्गोरिदम का उपयोग करके दी गई बिंदुओं के सेट का कन्वेक्स हल ढूंढने के लिए एक प्रोग्राम पर चर्चा करेंगे।
कन्वेक्स हल सबसे छोटा बहुभुज उत्तल आकृति है जो सभी दिए गए बिंदुओं को या तो सीमा पर या आकृति के अंदर समाहित करता है।
जार्विस एल्गोरिदम में, हम सबसे बाएं बिंदु का चयन करते हैं और दक्षिणावर्त दिशा में बिंदुओं को लपेटते हुए आगे बढ़ते हैं।
उदाहरण
#include <bits/stdc++.h> using namespace std; //बिंदु की संरचना struct Point{ int x, y; }; //बिंदुओं की स्थिति की गणना int cal_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; //घड़ी या विपरीत घड़ी दिशा } //कन्वेक्स हल प्रिंट करना void convexHull(Point points[], int n){ if (n < 3) return; vector<Point> hull; //सबसे बाएं बिंदु की गणना int l = 0; for (int i = 1; i < n; i++) if (points[i].x < points[l].x) l = i; //दक्षिणावर्त दिशा में आगे बढ़ना int p = l, q; do{ //वर्तमान बिंदु को परिणाम में जोड़ें hull.push_back(points[p]); q = (p+1)%n; for (int i = 0; i < n; i++){ if (cal_orientation(points[p], points[i], points[q]) == 2) q = i; } p = q; } while (p != l); //यदि पहले बिंदु तक नहीं पहुंचा for (int i = 0; i < hull.size(); i++) cout << "(" << hull[i].x << ", " << hull[i].y << ")\n"; } int main(){ Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1}, {3, 0}, {0, 0}, {3, 3}}; int n = sizeof(points)/sizeof(points[0]); convexHull(points, n); return 0; }आउटपुट
(0, 3) (0, 0) (3, 0) (3, 3)