ডেটা স্ট্রাকচারে উত্তল হুলের উদাহরণ

এখানে আমরা উত্তল হুলের একটি উদাহরণ দেখব। ধরুন আমাদের পয়েন্টের একটি সেট আছে। কম পরিমাণ পয়েন্ট নিয়ে আমাদের একটি বহুভুজ তৈরি করতে হবে, যা সমস্ত প্রদত্ত বিন্দুকে কভার করবে। এই বিভাগে আমরা উত্তল হুল পেতে জার্ভিস মার্চ অ্যালগরিদম দেখব।

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

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

ইনপুট − পয়েন্টের সেট:{(-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)ইনপুট:পয়েন্ট, পয়েন্টের সংখ্যা। আউটপুট:উত্তল হুলের কোণ বিন্দু। প্রতিটি বিন্দু i এর জন্য শুরু করুন :=পয়েন্ট[0], যদি পয়েন্ট[i].x <শুরু হয় তাহলে করুন। x, তারপর // বাম সর্বাধিক পয়েন্ট শুরু করুন :=পয়েন্ট [i] সম্পন্ন বর্তমান :=ফলাফল সেটে শুরু বিন্দু যোগ করুন। colPts সংজ্ঞায়িত করুন যখন সত্য থাকাকালীন সমরেখার বিন্দু সংরক্ষণ করতে সেট করুন, //শুরু করুন একটি অসীম লুপ পরের :=পয়েন্ট[i] 0ম পয়েন্ট ব্যতীত সমস্ত পয়েন্টের জন্য, করুন যদি পয়েন্ট [i] =বর্তমান, তারপর পরবর্তী অংশটি এড়িয়ে যান, পরবর্তীতে যান iteration val :=কারেন্টের ক্রস প্রোডাক্ট, পরবর্তী, পয়েন্ট[i] যদি val> 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){ point start =points[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 <<") "; }

আউটপুট