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

C++ में ग्राहम स्कैन का उपयोग करके कन्वेक्स हल


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

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

ग्राहम स्कैन में, पहले बिंदुओं को सॉर्ट किया जाता है ताकि सबसे नीचे का बिंदु मिल सके। फिर बिंदुओं को क्रम में पार किया जाता है और उनके क्रम के आधार पर सीमा पर होने के लिए अस्वीकार या स्वीकार किया जाता है।

उदाहरण

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

  1. - ग्राहम स्कैन एल्गोरिदम (कन्वेक्स हल)

    परिचय कन्वेक्स हल वह न्यूनतम बंद क्षेत्र है जो सभी दिए गए डेटा बिंदुओं को कवर कर सकता है। ग्राहम स्कैन एल्गोरिदम कन्वेक्स हल के कोने बिंदुओं को ढूंढेगा। इस एल्गोरिदम में, सबसे पहले, सबसे निचला बिंदु चुना जाता है। वह बिंदु कन्वेक्स हल का प्रारंभिक बिंदु होता है। शेष n-1 शीर्षों को प्रारंभ बिंदु से व

  1. C++ में 2-D तल में एक बिंदु का मिरर इमेज ढूंढना C++ में 2-D तल में एक बिंदु का मिरर इमेज ढूंढना

    इस समस्या में, हमें 2-D तल में एक बिंदु P और समीकरण ax + by + c = 0 के बिंदु a, b, c दिए जाते हैं। हमारा कार्य 2-D तल में एक बिंदु का मिरर इमेज ढूंढना है।आइए एक उदाहरण से समस्या को समझते हैं,इनपुटP = (2, 1), a = 1, b = -1, c = 0आउटपुट(1, 2)व्याख्यातल इस तरह दिखता है,समाधान दृष्टिकोणसमस्या को हल करने

  1. C++ में एक बिंदु को दूसरे बिंदु के बारे में घुमाना C++ में एक बिंदु को दूसरे बिंदु के बारे में घुमाना

    मूल बिंदु के बारे में कोण θ पर वामावर्त दिशा में बिंदु X का घुमाव निम्न द्वारा किया जाता है -  X को θ से मूल बिंदु के बारे में वामावर्त घुमाएं: X*polar( 1.0,θ )। यहां, जटिल संख्याओं के लिए polar फ़ंक्शन हेडर फ़ाइल के तहत परिभाषित है और चरण कोण और परिमाण का उपयोग करके एक जटिल संख्या खोजने के ल