জার্ভিস মার্চ অ্যালগরিদম প্রদত্ত ডেটা পয়েন্ট সেট থেকে কনভেক্স হালের কর্ণার বিন্দুগুলো সনাক্ত করতে ব্যবহৃত হয়।
ডেটা সেটের বামপাশের বিন্দু থেকে শুরু করে, আমরা অ্যান্টি-ক্লকওয়াইজ ঘুরে কনভেক্স হালের বিন্দুগুলো রাখি। বর্তমান বিন্দু থেকে, আমরা পরবর্তী বিন্দু বেছে নিতে পারি সেগুলোর ওরিয়েন্টেশন বর্তমান বিন্দু থেকে চেক করে। যখন কোণ সবচেয়ে বড় হয়, সেই বিন্দুটি বেছে নেওয়া হয়। সব বিন্দু পুরা হলে, যখন পরবর্তী বিন্দু শুরু বিন্দু হয়, অ্যালগরিদম বন্ধ করুন।
ইনপুট এবং আউটপুট
ইনপুট: বিন্দু সেট: {(-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 জন্য, করুন
যদি points[i].x < start.x, তবে
// সবচেয়ে বামের বিন্দু পান
start := points[i]
শেষ
current := start
শুরু বিন্দুটি রেজাল্ট সেটে যোগ করুন।
colPts সেট সংজ্ঞায়িত করুন কোলিনিয়ার বিন্দু সংরক্ষণে
যতক্ষণ সত্য, করুন
//একটি অসীম লুপ শুরু
next := points[i]
০তম বিন্দু বাদে সব বিন্দু i জন্য, করুন
যদি points[i] = current, তবে
পরবর্তী অংশ বাদ দিন, পরবর্তী ইটেরেশনের জন্য যান
val := current, next, points[i]-এর ক্রস প্রোডাক্ট
যদি val > 0, তবে
next := points[i]
colPts অ্যারে ক্লিয়ার করুন
অন্যথায় যদি cal = 0, তবে
যদি next current-এর চেয়ে points[i]-এর কাছে নিকট, তবে
next কে colPts-এ যোগ করুন
next := points[i]
অন্যথায়
points[i] কে colPts-এ যোগ করুন
শেষ
colPts-এ থাকা সব আইটেম রেজাল্টে যোগ করুন
যদি next = start, তবে
লুপ ভাঙুন
next কে রেজাল্টে প্রবেশ করান
current := next
শেষ
result ফেরত দিন
শেষউদাহরণ
#include<iostream> #include<set> #include<vector> using namespace std; struct point { //২D প্লেনের জন্য বिंदু সংজ্ঞায়িত করুন 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) { //ab ভেক্টর থেকে 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; //যদি ফলাফল < 0, c বামে, > 0, c ডানে, = 0, a,b,c কোলিনিয়ার } 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; //যখন b এবং c, a থেকে সমান দূরত্বে else if(item1 < item2) return -1; //যখন b, a-র কাছে নিকট return 1; //যখন c, 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) { //যখন i-তম বিন্দু বাম পাশে 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]); //যদি i-তম বিন্দু nextTarget-এর চেয়ে নিকট বা সমান } } } 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)
