Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में कन्वेक्स हल - जार्विस एल्गोरिदम या रैपिंग


इस ट्यूटोरियल में, हम जार्विस एल्गोरिदम का उपयोग करके दी गई बिंदुओं के सेट का कन्वेक्स हल ढूंढने के लिए एक प्रोग्राम पर चर्चा करेंगे।

कन्वेक्स हल सबसे छोटा बहुभुज उत्तल आकृति है जो सभी दिए गए बिंदुओं को या तो सीमा पर या आकृति के अंदर समाहित करता है।

जार्विस एल्गोरिदम में, हम सबसे बाएं बिंदु का चयन करते हैं और दक्षिणावर्त दिशा में बिंदुओं को लपेटते हुए आगे बढ़ते हैं।

उदाहरण

#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)

  1. C/C++ में बर्कले का एल्गोरिथ्म C/C++ में बर्कले का एल्गोरिथ्म

    बर्कले का एल्गोरिथ्म वितरित प्रणालियों में क्लॉक सिंक्रोनाइज़ेशन के लिए उपयोग किया जाने वाला एक एल्गोरिथ्म है। यह एल्गोरिथ्म उन मामलों में उपयोग किया जाता है जब वितरित नेटवर्क के कुछ या सभी सिस्टम में निम्नलिखित समस्याएं होती हैं: A. मशीन के पास सटीक समय स्रोत नहीं है। B. नेटवर्क या मशीन के पास UTC

  1. C++ में कंप्यूटर ग्राफिक्स में पॉइंट क्लिपिंग एल्गोरिदम C++ में कंप्यूटर ग्राफिक्स में पॉइंट क्लिपिंग एल्गोरिदम

    कंप्यूटर ग्राफिक्स कंप्यूटर स्क्रीन पर छवियों और ग्राफिक्स को बनाने से संबंधित है। यहां, हम स्क्रीन को 2-D निर्देशांक प्रणाली के रूप में मानते हैं। यह निर्देशांक प्रणाली शीर्ष-बाएं (0,0) से शुरू होती है और नीचे-दाएं पर समाप्त होती है। व्यूइंग प्लेन कंप्यूटर ग्राफिक्स में ग्राफिक्स बनाने के लिए परिभ

  1. C++ में बेलमैन-फोर्ड एल्गोरिदम C++ में बेलमैन-फोर्ड एल्गोरिदम

    बेलमैन-फोर्ड एल्गोरिदम एक डायनामिक प्रोग्रामिंग एल्गोरिदम है जिसका उपयोग किसी भी शीर्ष के सबसे छोटे पथ को खोजने के लिए किया जाता है जिसे एक शीर्ष से प्रारंभिक शीर्ष के रूप में माना जाता है। यह एल्गोरिदम पुनरावृत्त विधि का पालन करता है और लगातार सबसे छोटा पथ खोजने का प्रयास करता है। बेलमैन-फोर्ड एल्