গ্রাহম স্ক্যান অ্যালগরিদম (Graham Scan Algorithm)

কনভেক্স হাল হল সর্বনিম্ন বন্ধ এলাকা যা সমস্ত প্রদত্ত ডেটা পয়েন্ট কভার করতে পারে।

গ্রাহম স্ক্যান অ্যালগরিদম কনভেক্স হালের কর্ণার বিন্দুগুলো বের করবে। এই অ্যালগরিদমে, প্রথমে সবচেয়ে নিচের বিন্দুটি বেছে নেওয়া হয়। সেটি কনভেক্স হালের শুরুর বিন্দু। বাকি 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 
  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-এ যোগ করুন 
    স্টক থেকে পপ করুন 
  শেষ 
শেষ

উদাহরণ

#include<iostream> #include<stack> #include<algorithm> #include<vector> using namespace std; struct point {   //২D প্লেনের জন্য বিন্দু সংজ্ঞায়িত করুন   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;    //কোলিনিয়ার   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<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]);    //min বিন্দু ০তম লোকেশনে সোয়াপ করুন   p0 = points[0];   qsort(&points[1], n-1, sizeof(point), comp);   //১ প্লেস থেকে শেষ পর্যন্ত পয়েন্ট সর্ট করুন       int arrSize = 1;   //মডিফাইড অ্যারেতে আইটেম লোকেট করতে ব্যবহৃত   for(int i = 1; i<n; i++) {     //যখন i-তম এবং (i+1)তম এলিমেন্টের কোণ একই, পয়েন্ট সরান     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();   //যখন টপ, সেকেন্ড টপ এবং i-তম পয়েন্ট বামে ঘুরে না, পয়েন্ট সরান       stk.push(points[i]);     }       while(!stk.empty()) {       convexHullPoints.push_back(stk.top());    //স্টক থেকে পয়েন্ট যোগ করুন       stk.pop();     } } 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)