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

परिचय

कन्वेक्स हल वह न्यूनतम बंद क्षेत्र है जो सभी दिए गए डेटा बिंदुओं को कवर कर सकता है।

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

शेष बिंदुओं से, उन्हें स्टैक में पुश करें। और स्टैक से आइटम्स को एक-एक करके हटाएं, जब स्टैक के शीर्ष बिंदु, दूसरे शीर्ष बिंदु और नए चयनित बिंदु points[i] के लिए अभिविन्यास वामावर्त न हो, जांच के बाद, points[i] को स्टैक में डालें।

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

इनपुट: बिंदुओं का सेट: {(-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) (-10, 3) (-10, 4) (-7, 8) (8, 6) (8, -7) (6, -10)

एल्गोरिदम

findConvexHull(points, n)
इनपुट: बिंदुओं का सेट, बिंदुओं की संख्या
आउटपुट: कन्वेक्स हल के सीमा बिंदु

Begin
    minY := points[0].y
    min := 0
    i := 1 से n-1 तक करें
        y := points[i].y
        यदि y < minY या minY = y और points[i].x < points[min].x, तो
            minY := points[i].y
            min := i
    done
    points[0] और points[min] को स्वैप करें
    p0 := points[0]
    points[1] से अंत तक क्रमबद्ध करें
    arrSize := 1
    i := 1 से n तक, करें
        जब i < n-1 और (p0, points[i], points[i+1]) संरेखी हों, करें
            i := i + 1
        done
        points[arrSize] := points[i]
        arrSize := arrSize + 1
    done
    यदि arrSize < 3, तो
        cHullPoints लौटाएं
    points[0] को स्टैक में पुश करें
    points[1] को स्टैक में पुश करें
    points[2] को स्टैक में पुश करें
    i := 3 से arrSize तक, करें
        जब तक स्टैक का शीर्ष, शीर्ष के नीचे का आइटम और points[i] वामावर्त घुमाव में न हों, करें
            स्टैक से शीर्ष तत्व हटाएं
        done
        points[i] को स्टैक में पुश करें
    done
    जब तक स्टैक खाली न हो, करें
        आइटम स्टैक शीर्ष तत्व को cHullPoints में डालें
        स्टैक से पॉप करें
    done
End

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

#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
using namespace std;

struct point {
    // 2D तल के लिए बिंदु परिभाषित करें
    int x, y;
};

point p0; // दो अन्य बिंदुओं के लिए उपयोग किया जाता है

point secondTop(stack<point>& stk) {
    point tempPoint = stk.top(); stk.pop();
    point res = stk.top(); // दूसरा शीर्ष तत्व प्राप्त करें
    stk.push(tempPoint); // पिछले शीर्ष को फिर से पुश करें
    return res;
}

int squaredDist(point p1, point p2) {
    return ((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}

int direction(point a, point b, point c) {
    int val = (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
    if (val == 0)
        return 0; // संरेखी
    else if (val < 0)
        return 2; // वामावर्त दिशा
    return 1; // दक्षिणावर्त दिशा
}

int comp(const void *point1, const void* point2) {
    point *p1 = (point*)point1;
    point *p2 = (point*)point2;
    int dir = direction(p0, *p1, *p2);
    if (dir == 0)
        return (squaredDist(p0, *p2) >= squaredDist(p0, *p1)) ? -1 : 1;
    return (dir == 2) ? -1 : 1;
}

vector<point> findConvexHull(point points[], int n) {
    vector<point> convexHullPoints;
    int minY = points[0].y, min = 0;
    for (int i = 1; i < n; i++) {
        int y = points[i].y;
        // सबसे निचला या सबसे बाएं बिंदु खोजें
        if ((y < minY) || (minY == y) && points[i].x < points[min].x) {
            minY = points[i].y;
            min = i;
        }
    }
    swap(points[0], points[min]); // न्यूनतम बिंदु को 0वें स्थान पर स्वैप करें
    p0 = points[0];
    qsort(&points[1], n-1, sizeof(point), comp); // 1 स्थान से अंत तक बिंदुओं को क्रमबद्ध करें
    
    int arrSize = 1; // संशोधित सरणी में आइटम्स का पता लगाने के लिए उपयोग किया जाता है
    for (int i = 1; i < n; i++) {
        // जब iवें और (i+1)वें तत्वों का कोण समान हो, तो बिंदुओं को हटाएं
        while (i < n-1 && direction(p0, points[i], points[i+1]) == 0)
            i++;
        points[arrSize] = points[i];
        arrSize++;
    }
    if (arrSize < 3)
        return convexHullPoints; // कम से कम 3 बिंदु होने चाहिए, खाली सूची लौटाएं।
    
    // एक स्टैक बनाएं और पहले तीन बिंदुओं को स्टैक में जोड़ें
    stack<point> stk;
    stk.push(points[0]); stk.push(points[1]); stk.push(points[2]);
    
    for (int i = 3; i < arrSize; i++) {
        // शेष शीर्षों के लिए
        while (direction(secondTop(stk), stk.top(), points[i]) != 2)
            stk.pop(); // जब शीर्ष, दूसरा शीर्ष और iवां बिंदु बाएं मोड़ नहीं बना रहे हों, तो बिंदु हटाएं
        stk.push(points[i]);
    }
    
    while (!stk.empty()) {
        convexHullPoints.push_back(stk.top()); // स्टैक से बिंदु जोड़ें
        stk.pop();
    }
    return convexHullPoints;
}

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;
    vector<point> result;
    result = findConvexHull(points, n);
    cout << "Boundary points of convex hull are: " << endl;
    vector<point>::iterator it;
    for (it = result.begin(); it != result.end(); it++)
        cout << "(" << it->x << ", " << it->y << ") ";
}

आउटपुट

Boundary points of convex hull are: (-9, -5) (-10, 3) (-10, 4) (-7, 8) (8, 6) (8, -7) (6, -10)