C++ प्रोग्राम: जार्विस मार्च एल्गोरिदम से कन्वेक्स हल ढूंढना

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

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

इनपुट: पॉइंट्स का सेट: {(-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]
    प्रत्येक पॉइंट i के लिए, करें
        यदि points[i].x < start.x, तो  // सबसे बाएं पॉइंट प्राप्त करें
            start := points[i]
    किया
    current := start
    रिजल्ट सेट में स्टार्ट पॉइंट जोड़ें।
    कोलिनियर पॉइंट्स स्टोर करने के लिए colPts सेट परिभाषित करें
    जबकि true, करें  // अनंत लूप शुरू करें
        next := points[i]
        0th पॉइंट को छोड़कर सभी पॉइंट्स i के लिए, करें
            यदि points[i] = current, तो
                अगले भाग को छोड़ें, अगले इटरेशन के लिए जाएं
            val := current, next, points[i] का क्रॉस प्रोडक्ट
            यदि val > 0, तो
                next := points[i]
                colPts ऐरे को क्लियर करें
            अन्यथा यदि val = 0, तो
                यदि next, points[i] की तुलना में current के अधिक निकट है, तो
                    next को colPts में जोड़ें
                    next := points[i]
                अन्यथा
                    points[i] को colPts में जोड़ें
        किया
        colPts के सभी आइटम्स को रिजल्ट में जोड़ें
        यदि next = start, तो
            लूप तोड़ें
        रिजल्ट में next डालें
        current := next
    किया
    रिजल्ट लौटाएं
End

उदाहरण कोड

#include <iostream>
#include <set>
#include <vector>
using namespace std;

struct point {
    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 findConvexHull(point points[], int n) {
    point start = points[0];
    for (int i = 1; i < n; i++) {
        // शुरू करने के लिए सबसे बाएं पॉइंट ढूंढें
        if (points[i].x < start.x)
            start = points[i];
    }
    point current = start;
    set result;
    // डुप्लीकेट पॉइंट्स से बचने के लिए सेट का उपयोग
    result.insert(start);
    vector *collinearPoints = new vector();
    
    while (true) {
        point nextTarget = points[0];
        for (int i = 1; i < n; i++) {
            if (points[i] == current) // जब चयनित पॉइंट वर्तमान पॉइंट हो, बाकी भाग इग्नोर करें
                continue;
            
            int val = crossProduct(current, nextTarget, points[i]);
            if (val > 0) {
                // जब ith पॉइंट बाएं तरफ हो
                nextTarget = points[i];
                collinearPoints = new vector(); // कोलिनियर पॉइंट्स रीसेट करें
            } 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::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 result;
    result = findConvexHull(points, n);
    cout << "Boundary points of convex hull are: " << endl;
    set::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)