গ্রাহাম স্ক্যান অ্যালগরিদম

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

গ্রাহামের স্ক্যান অ্যালগরিদম উত্তল হুলের কোণার বিন্দু খুঁজে পাবে। এই অ্যালগরিদমে, প্রথমে, সর্বনিম্ন পয়েন্টটি বেছে নেওয়া হয়। সেই বিন্দুটি উত্তল হুলের সূচনা বিন্দু। অবশিষ্ট n-1 শীর্ষবিন্দুগুলি শুরু বিন্দু থেকে ঘড়ির কাঁটার বিপরীত দিকের উপর ভিত্তি করে সাজানো হয়। যদি দুই বা ততোধিক বিন্দু একই কোণ গঠন করে, তাহলে শুরু থেকে দূরতম বিন্দু ব্যতীত একই কোণের সমস্ত বিন্দু সরিয়ে ফেলুন।

অবশিষ্ট পয়েন্ট থেকে, স্ট্যাকের মধ্যে তাদের ধাক্কা. এবং স্ট্যাকের শীর্ষ পয়েন্ট, দ্বিতীয় শীর্ষ বিন্দু এবং নতুন নির্বাচিত পয়েন্ট পয়েন্ট[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(পয়েন্ট, n)

ইনপুট - পয়েন্টের সেট, পয়েন্টের সংখ্যা।

আউটপুট - উত্তল হুলের সীমানা বিন্দু।

শুরু করুন minY :=পয়েন্ট[0].y min :=0 এর জন্য i :=1 থেকে n-1 করতে y :=পয়েন্ট[i].y যদি y  
উদাহরণ
 
#include#include#include#includeNamespace ব্যবহার করে std;struct point { //define points for 2d সমতল int x, y;};point p0; //অন্য দুটি পয়েন্টপয়েন্ট সেকেন্ডটপ(স্ট্যাক<পয়েন্ট>&stk) { পয়েন্ট tempPoint =stk.top(); stk.pop(); পয়েন্ট res =stk.top(); // দ্বিতীয় শীর্ষ উপাদান stk.push(tempPoint) পান; //পুশ আগের টপ আবার রিটার্ন রিটার্ন;}int squaredDist(point p1, point p2) { রিটার্ন ((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y) )*(p1.y-p2.y));}int দিক (বিন্দু a, বিন্দু বি, বিন্দু c) { int val =(b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y -দ্বারা); যদি (val ==0) রিটার্ন 0; //কোলিনিয়ার else if(val <0) রিটার্ন 2; //ঘড়ির কাঁটার বিপরীত দিকে রিটার্ন 1; //ঘড়ির কাঁটার দিক} int comp(const void *point1, const void*point2) { point *p1 =(point*)point1; পয়েন্ট *p2 =(বিন্দু*)বিন্দু 2; int dir =দিক (p0, *p1, *p2); if(dir ==0) রিটার্ন (squaredDist(p0, *p2)>=squaredDist(p0, *p1))?-1 :1; ফেরত (dir==2)? -1 :1; }ভেক্টর<পয়েন্ট>ফাইন্ডকনভেক্সহুল(পয়েন্ট পয়েন্ট[], int n) { ভেক্টর<পয়েন্ট> কনভেক্সহুলপয়েন্টস; int minY =points[0].y, min =0; জন্য(int i =1; i stk; stk.push(পয়েন্ট[0]); stk.push(পয়েন্ট[1]); stk.push(পয়েন্ট[2]); for(int i =3; i ফলাফল; ফলাফল =FindConvexHull(পয়েন্ট, n); cout <<"উত্তল হুলের সীমানা বিন্দুগুলি হল:"<::ইটারেটর এটি; for(it =result.begin(); it!=result.end(); it++) cout <<"(" <x <<", " <y <<") "; }
 
আউটপুট
 উত্তল হুলের সীমানা বিন্দুগুলি হল:(-9, -5) (-10, 3) (-10, 4) (-7, 8) (8, 6) (8, -7) (6, - 10)