कन्वेक्स हल वह न्यूनतम बंद क्षेत्र है जो सभी दिए गए डेटा पॉइंट्स को कवर कर सकता है।
ग्राहम स्कैन एल्गोरिदम कन्वेक्स हल के कॉर्नर पॉइंट्स ढूंढता है। इस एल्गोरिदम में, सबसे पहले सबसे निचले पॉइंट को चुना जाता है। वह पॉइंट कन्वेक्स हल का शुरुआती पॉइंट होता है। शेष 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
किया
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
किया
points[arrSize] := points[i]
arrSize := arrSize + 1
किया
यदि arrSize < 3, तो
cHullPoints लौटाएं
points[0] को स्टैक में पुश करें
points[1] को स्टैक में पुश करें
points[2] को स्टैक में पुश करें
i := 3 से arrSize तक, करें
जबकि स्टैक का टॉप, टॉप से नीचे का आइटम और points[i] एंटी-क्लॉकवाइज रोटेशन में न हों, करें
स्टैक से टॉप एलिमेंट डिलीट करें
किया
points[i] को स्टैक में पुश करें
किया
जबकि स्टैक खाली न हो, करें
आइटम स्टैक टॉप एलिमेंट को cHullPoints में डालें
स्टैक से पॉप करें
किया
End
उदाहरण कोड
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
using namespace std;
struct point {
int x, y;
};
point p0; // दो अन्य पॉइंट्स के लिए उपयोग
point secondTop(stack &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 findConvexHull(point points[], int n) {
vector 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]); // मिन पॉइंट को 0th लोकेशन पर स्वैप करें
p0 = points[0];
qsort(&points[1], n - 1, sizeof(point), comp); // 1 प्लेस से अंत तक पॉइंट्स सॉर्ट करें
int arrSize = 1; // मॉडिफाइड ऐरे में आइटम्स लोकेट करने के लिए उपयोग
for (int i = 1; i < n; i++) {
// जब ith और (i+1)th एलिमेंट्स का कोण समान हो, पॉइंट्स हटाएं
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 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(); // जब टॉप, सेकंड टॉप और ith पॉइंट लेफ्ट टर्न न बना रहे हों, पॉइंट हटाएं
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 result;
result = findConvexHull(points, n);
cout << "Boundary points of convex hull are: " << endl;
vector::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)
