जार्विस मार्च एल्गोरिदम (कन्वेक्स हल)

परिचय

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

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

इनपुट और आउटपुट

इनपुट: बिंदुओं का सेट: {(-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]
    done
    current := start
    प्रारंभ बिंदु को परिणाम सेट में जोड़ें।
    collinear बिंदुओं को संग्रहीत करने के लिए colPts सेट परिभाषित करें
    जब तक सत्य, करें
        // अनंत लूप शुरू करें
        next := points[i]
        0वें बिंदु को छोड़कर सभी बिंदुओं i के लिए, करें
            यदि points[i] = current, तो
                // जब चयनित बिंदु वर्तमान बिंदु हो, तो बाकी भाग को अनदेखा करें
                अगली पुनरावृत्ति के लिए जाएं
            val := current, next, points[i] का क्रॉस उत्पाद
            यदि val > 0, तो
                // जब iवां बिंदु बाईं ओर हो
                next := points[i]
                collinearPoints सरणी को रीसेट करें
            अन्यथा यदि val = 0, तो
                // यदि तीन बिंदु संरेखी हैं
                यदि next, points[i] की तुलना में current के करीब है, तो
                    next को colPts में जोड़ें
                    next := points[i]
                अन्यथा
                    points[i] को colPts में जोड़ें
        done
        colPts में सभी आइटम्स को परिणाम में जोड़ें
        यदि next = start, तो
            लूप तोड़ें
        next को परिणाम में डालें
        current := next
    done
    परिणाम लौटाएं
End

उदाहरण (C++ कोड)

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

struct point {
    // 2D तल के लिए बिंदु परिभाषित करें
    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<point> 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<point> result; // डुप्लिकेट बिंदुओं की प्रविष्टि से बचने के लिए सेट का उपयोग
    result.insert(start);
    vector<point> *collinearPoints = new vector<point>();
    
    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) { // जब iवां बिंदु बाईं ओर हो
                nextTarget = points[i];
                collinearPoints = new vector<point>(); // संरेखी बिंदुओं को रीसेट करें
            } else if (val == 0) { // यदि तीन बिंदु संरेखी हैं
                if (distance(current, nextTarget, points[i]) < 0) { // करीब वाले को संरेखी सूची में जोड़ें
                    collinearPoints->push_back(nextTarget);
                    nextTarget = points[i];
                } else {
                    collinearPoints->push_back(points[i]); // जब iवां बिंदु करीब या nextTarget के समान हो
                }
            }
        }
        vector<point>::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<point> result;
    result = findConvexHull(points, n);
    cout << "Boundary points of convex hull are: " << endl;
    set<point>::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)