জারভিস মার্চ অ্যালগরিদম একটি ডেটা পয়েন্ট সেট থেকে কনভেক্স হালের কর্নার পয়েন্টগুলো সনাক্ত করতে ব্যবহৃত হয়।
ডেটা সেটের বামপাশের পয়েন্ট থেকে শুরু করে, আমরা অ্যান্টি-ক্লকওয়াইজ ঘুরে পয়েন্টগুলো কনভেক্স হালে রাখি। বর্তমান পয়েন্ট থেকে, আমরা সেই পয়েন্ট থেকে অরিয়েন্টেশন চেক করে পরবর্তী পয়েন্ট বেছে নিই। যখন কোণটি সবচেয়ে বড় হয়, তখন সেই পয়েন্টটি বেছে নেওয়া হয়। সব পয়েন্ট পূরণ হলে, যখন পরবর্তী পয়েন্ট শুরুতের পয়েন্ট হয়, তখন অ্যালগরিদমটি থামায়।
ইনপুট: পয়েন্ট সেট: {(-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)
ইনপুট: পয়েন্টগুলো, পয়েন্টের সংখ্যা।
আউটপুট: কনভেক্স হালের কর্নার পয়েন্টগুলো।
শুরু
start := points[0]
প্রতিটি পয়েন্ট i এর জন্য, করুন
if points[i].x < start.x, তবে // বামপাশের পয়েন্ট পান
start := points[i]
লুপ শেষ
current := start
start পয়েন্টকে রেজাল্ট সেটে যোগ করুন।
colPts সেট ডিফাইন করুন কোলিনিয়ার পয়েন্ট স্টোর করতে
যতক্ষণ true, করুন // অসীম লুপ
next := points[i]
0th পয়েন্ট ছাড়া সব পয়েন্ট i এর জন্য, করুন
if points[i] = current, তবে
পরবর্তী অংশ স্কিপ করুন, পরবর্তী ইটেরেশনের জন্য যান
val := current, next, points[i]-র ক্রস প্রোডাক্ট
if val > 0, তবে
next := points[i]
colPts অ্যারে ক্লিয়ার করুন
else if val = 0, তবে
if next current-এর চেয়ে points[i]-এর কাছে নিকটতর, তবে
next কে colPts-এ যোগ করুন
next := points[i]
অন্যথায়
points[i] কে colPts-এ যোগ করুন
লুপ শেষ
colPts-এ থাকা সব আইটেম রেজাল্টে যোগ করুন
if next = start, তবে
লুপ ব্রেক করুন
next কে রেজাল্টে ইনসার্ট করুন
current := next
লুপ শেষ
return result
শেষ
উদাহরণ কোড
#include<iostream>
#include<set>
#include<vector>
using namespace std;
struct point {
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) {
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; // if result < 0, c in the left, > 0, c in the right, = 0, a,b,c are collinear
}
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; // when b and c are in same distance from a
else if(item1 < item2)
return -1; // when b is closer to a
return 1; // when c is closer to 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) {
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]);
}
}
}
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)
