কনভেক্স হাল হলো সর্বনিম্ন বন্ধ এলাকা যা সমস্ত দিয়ে गये ডেটা পয়েন্ট কভার করতে পারে।
গ্রাহাম স্ক্যান অ্যালগরিদম কনভেক্স হালের কর্নার পয়েন্টগুলো বের করে। এই অ্যালগরিদমে, প্রথমে সবচেয়ে নিচের পয়েন্টটি বেছে নেওয়া হয়। সেই পয়েন্টটি কনভেক্স হালের শুরুতের পয়েন্ট। বাকি 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)
ইনপুট: পয়েন্ট সেট, পয়েন্টের সংখ্যা।
আউটপুট: কনভেক্স হালের বাউন্ডারি পয়েন্টগুলো।
শুরু
minY := points[0].y
min := 0
for i := 1 to n-1 do
y := points[i].y
if y < minY or (minY = y and points[i].x < points[min].x), then
minY := points[i].y
min := i
লুপ শেষ
swap points[0] and points[min]
p0 := points[0]
points[1] থেকে শেষ পর্যন্ত সর্ট করুন
arrSize := 1
for i := 1 to n, do
when i < n-1 and (p0, points[i], points[i+1]) are collinear, do
i := i + 1
লুপ শেষ
points[arrSize] := points[i]
arrSize := arrSize + 1
লুপ শেষ
if arrSize < 3, then
return cHullPoints
push points[0] into stack
push points[1] into stack
push points[2] into stack
for i := 3 to arrSize, do
while top of stack, item below the top and points[i] is not in anticlockwise rotation, do
delete top element from stack
লুপ শেষ
push points[i] into stack
লুপ শেষ
while stack is not empty, do
item stack top element into cHullPoints
pop from stack
লুপ শেষ
শেষ
উদাহরণ কোড
#include<iostream>
#include<stack>
#include<algorithm>
#include<vector>
using namespace std;
struct point {
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; //colinear
else if(val < 0)
return 2; //anti-clockwise direction
return 1; //clockwise direction
}
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]);
p0 = points[0];
qsort(&points[1], n-1, sizeof(point), comp);
int arrSize = 1;
for(int i = 1; i < n; i++) {
while(i < n-1 && direction(p0, points[i], points[i+1]) == 0)
i++;
points[arrSize] = points[i];
arrSize++;
}
if(arrSize < 3)
return convexHullPoints;
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();
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)
