জার্ভিস মার্চ অ্যালগরিদম

জার্ভিস মার্চ অ্যালগরিদম প্রদত্ত ডেটা পয়েন্টের সেট থেকে উত্তল হুলের কোণার বিন্দু সনাক্ত করতে ব্যবহৃত হয়।

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

ইনপুট এবং আউটপুট

ইনপুট:পয়েন্টের সেট:{(-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(পয়েন্ট, n)

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

আউটপুট: উত্তল হুলের কোণ বিন্দু।

শুরু শুরু করুন :=পয়েন্ট[0] প্রতিটি পয়েন্টের জন্য i, করুন যদি পয়েন্ট[i].x  0, তারপর পরবর্তী :=পয়েন্ট[i] colPts অ্যারে সাফ করুন অন্যথা যদি cal =0 হয়, তারপর যদি পরবর্তী পয়েন্টের চেয়ে কারেন্টের কাছাকাছি হয় , তারপর colPts next এ যুক্ত করুন :=points[i] অন্যথায় colPts-এ পয়েন্ট যোগ করুন পরবর্তী সম্পন্ন রিটার্ন ফলাফলEnd

উদাহরণ

#include#include#includeনেমস্পেস ব্যবহার করে std;struct বিন্দু {//2d সমতল int x, y-এর জন্য পয়েন্ট নির্ধারণ করুন; bool অপারেটর==(পয়েন্ট p2) { if(x ==p2.x &&y ==p2.y) রিটার্ন 1; রিটার্ন 0; } বুল অপারেটর<(const পয়েন্ট &p2)const { //ডামি তুলনা ফাংশন সেট রিটার্ন সত্যে সাজানোর জন্য ব্যবহৃত হয়; }};int crossProduct(বিন্দু a, বিন্দু বি, বিন্দু c) { //ab ভেক্টর int y1 =a.y - b.y থেকে c এর স্থান খুঁজে বের করে; int y2 =a.y - c.y; int x1 =a.x - b.x; int x2 =a.x - c.x; রিটার্ন y2*x1 - y1*x2; //যদি ফলাফল <0, বাম দিকে c,> 0, c ডানদিকে, =0, a, b,c হয় সমরেখার} int দূরত্ব (বিন্দু a, বিন্দু বি, বিন্দু 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) রিটার্ন 0; //যখন b এবং c একটি অন্য থেকে একই দূরত্বে থাকে if(item1 findConvexHull(পয়েন্ট পয়েন্ট[], int n) { পয়েন্ট স্টার্ট =পয়েন্টস[0] এর কাছাকাছি থাকে; for(int i =1; i ফলাফল; //সেট ডুপ্লিকেট পয়েন্টের এন্ট্রি এড়াতে ব্যবহার করা হয় result.insert(start); ভেক্টর<পয়েন্ট> *কলিনিয়ারপয়েন্টস =নতুন ভেক্টর<পয়েন্ট>; while(true) { point nextTarget =points[0]; for(int i =1; i 0) { //যখন ith পয়েন্ট বাম পাশে থাকে nextTarget =points[i]; collinearPoints =নতুন ভেক্টর<পয়েন্ট>; //সমাবেশী বিন্দু পুনরায় সেট করুন }অন্যথায় যদি(ভাল ==0) { //যদি তিনটি বিন্দু সমরেখার হয় যদি(দূরত্ব(বর্তমান, পরবর্তী লক্ষ্য, পয়েন্ট[i]) <0) { //সমস্তর তালিকার কাছাকাছি একটি যোগ করুন collinearPoints-> push_back(পরবর্তী লক্ষ্য); নেক্সট টার্গেট =পয়েন্ট[i]; }অন্য{ collinearPoints->push_back(পয়েন্ট[i]); //যখন ith পয়েন্ট কাছাকাছি হয় বা nextTarget } } } ভেক্টর::iterator এর মত হয়; for(it =collinearPoints->begin(); it !=collinearPoints->end(); it++) { result.insert(*it); //সমস্ত পয়েন্ট যোগ করুন ফলাফল সেট করতে } if(nextTarget ==start) //যখন পরবর্তী পয়েন্ট শুরু হয় এর মানে, এলাকা কভার করা বিরতি; result.insert(nextTarget); বর্তমান =পরবর্তী লক্ষ্য; } ফলাফল ফেরত;} int main() { পয়েন্ট পয়েন্ট[] ={{-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; সেট<পয়েন্ট> ফলাফল; ফলাফল =FindConvexHull(পয়েন্ট, n); cout <<"উত্তল হুলের সীমানা বিন্দুগুলি হল:"<::ইটারেটর এটা; for(it =result.begin(); it!=result.end(); it++) cout <<"(" <x <<", " <y <<") "; }

আউটপুট