এই টিউটোরিয়ালে, আমরা জার্ভিসের অ্যালগরিদম ব্যবহার করে একটি নির্দিষ্ট বিন্দুর উত্তল হুল খুঁজে বের করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব।
উত্তল হুল হল ক্ষুদ্রতম বহুভুজ উত্তল চিত্র যাতে চিত্রের ভিতরের সীমানায় সমস্ত প্রদত্ত বিন্দু থাকে।
জার্ভিসের অ্যালগরিদমে, আমরা সবচেয়ে বাম বিন্দু নির্বাচন করি এবং মোড়ানো পয়েন্টগুলি ঘড়ির কাঁটার দিকে চলতে থাকি।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
//structure of the point
struct Point{
int x, y;
};
//calculating the position of the points
int cal_orientation(Point p, Point q, Point r){
int val = (q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y);
if (val == 0) return 0; //collinear
return (val > 0)? 1: 2; //clock or counterclockwise
}
//printing convex hull
void convexHull(Point points[], int n){
if (n < 3) return;
vector<Point> hull;
//calculating the leftmost point
int l = 0;
for (int i = 1; i < n; i++)
if (points[i].x < points[l].x)
l = i;
//moving in the clockwise direction
int p = l, q;
do{
//adding current point to result
hull.push_back(points[p]);
q = (p+1)%n;
for (int i = 0; i < n; i++){
if (cal_orientation(points[p], points[i], points[q]) == 2)
q = i;
}
p = q;
} while (p != l); //if didn't reached the first point
for (int i = 0; i < hull.size(); i++)
cout << "(" << hull[i].x << ", "
<< hull[i].y << ")\n";
}
int main(){
Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1},
{3, 0}, {0, 0}, {3, 3}};
int n = sizeof(points)/sizeof(points[0]);
convexHull(points, n);
return 0;
} আউটপুট
(0, 3) (0, 0) (3, 0) (3, 3)
