Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> प्रोग्रामिंग

डेटा संरचनाओं में उत्तल हल उदाहरण

यहां हम उत्तल पतवार पर एक उदाहरण देखेंगे। मान लीजिए कि हमारे पास बिंदुओं का एक सेट है। हमें कम अंक लेकर एक बहुभुज बनाना है, जो सभी दिए गए बिंदुओं को कवर करेगा। इस खंड में हम उत्तल पतवार प्राप्त करने के लिए जार्विस मार्च एल्गोरिथम देखेंगे।

जार्विस मार्च एल्गोरिथ्म का उपयोग डेटा बिंदुओं के दिए गए सेट से उत्तल पतवार के कोने बिंदुओं का पता लगाने के लिए किया जाता है।

डेटा सेट के सबसे बाएं बिंदु से शुरू करते हुए, हम उत्तल पतवार में बिंदुओं को वामावर्त घुमाकर रखते हैं। वर्तमान बिंदु से, हम वर्तमान बिंदु से उन बिंदुओं के उन्मुखीकरण की जांच करके अगला बिंदु चुन सकते हैं। जब कोण सबसे बड़ा होता है, तो बिंदु चुना जाता है। सभी बिंदुओं को पूरा करने के बाद, जब अगला बिंदु प्रारंभ बिंदु हो, तो एल्गोरिथम को रोकें।

इनपुट - बिंदुओं का सेट:{(-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)
Input: The points, number of points.
Output: Corner points of convex hull.
Begin
   start := points[0]
   for each point i, do
      if points[i].x < start.x, then // get the left most point
         start := points[i]
   done
   current := start
   add start point to the result set.
   define colPts set to store collinear points
   while true, do //start an infinite loop
      next := points[i]
      for all points i except 0th point, do
         if points[i] = current, then
            skip the next part, go for next iteration
         val := cross product of current, next, points[i]
         if val > 0, then
            next := points[i]
            clear the colPts array
         else if cal = 0, then
            if next is closer to current than points[i], then
               add next in the colPts
               next := points[i]
            else
               add points[i] in the colPts
      done
      add all items in the colPts into the result
      if next = start, then
         break the loop
      insert next into the result
      current := next
   done
   return result
End

उदाहरण

#include<iostream>
#include<set>
#include<vector>
using namespace std;
struct point{ //define points for 2d plane
   int x, y;
   bool operator==(point p2){
      if(x == p2.x && y == p2.y)
         return 1;
      return 0;
   }
   bool operator<(const point &p2)const{ //dummy compare function used to sort in set
      return true;
   }
};
int crossProduct(point a, point b, point c){ //finds the place of c from ab vector
   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; //if result < 0, c in the left, > 0, c in the right, = 0, a,b,c are collinear
}
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; //when b and c are in same distance from a
   else if(item1 < item2)
      return -1; //when b is closer to a
   return 1; //when c is closer to a
}
set<point> findConvexHull(point points[], int n){
   point start = points[0];
   for(int i = 1; i<n; i++){ //find the left most point for starting
      if(points[i].x < start.x)
         start = points[i];
   }
   point current = start;
   set<point> result; //set is used to avoid entry of duplicate points
   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) //when selected point is current point, ignore rest part
            continue;
         int val = crossProduct(current, nextTarget, points[i]);
         if(val > 0){ //when ith point is on the left side
            nextTarget = points[i];
            collinearPoints = new vector<point>; //reset collinear points
         }else if(val == 0){ //if three points are collinear
            if(distance(current, nextTarget, points[i]) < 0){ //add closer one to collinear list
               collinearPoints->push_back(nextTarget);
               nextTarget = points[i];
            }else{
               collinearPoints->push_back(points[i]); //when ith point is closer or same as nextTarget
            }
         }
      }
      vector<point>::iterator it;
      for(it = collinearPoints->begin(); it != collinearPoints->end(); it++){
         result.insert(*it); //add allpoints in collinear points to result set
      }
      if(nextTarget == start) //when next point is start it means, the area covered
         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)

  1. पत्राचार आधारित डेटा संरचनाएं

    टोटल और लीफ पत्राचार अधिक परिष्कृत पत्राचार तकनीक हैं। इन दोनों तकनीकों में, आधे तत्व न्यूनतम PQ में और अन्य आधे अधिकतम PQ में स्थित होते हैं। जब तत्वों की संख्या विषम होती है, तो एक तत्व बफर में संग्रहीत होता है। यह बफ़र किया गया तत्व या तो PQ का सदस्य नहीं है। कुल पत्राचार तकनीक में, न्यूनतम PQ मे

  1. डेटा संरचनाओं में न्यूनतम फैले हुए पेड़

    एक फैला हुआ पेड़ अप्रत्यक्ष ग्राफ़ का एक उपसमुच्चय है जिसमें सभी शीर्ष किनारों की न्यूनतम संख्या से जुड़े होते हैं। यदि सभी कोने एक ग्राफ में जुड़े हुए हैं, तो कम से कम एक फैले हुए पेड़ मौजूद हैं। ग्राफ़ में, एक से अधिक फैले हुए वृक्ष हो सकते हैं। न्यूनतम फैले हुए पेड़ एक न्यूनतम स्पैनिंग ट्री (MS

  1. डेटा संरचनाओं में बाइनरी ट्री प्रतिनिधित्व

    यहां हम देखेंगे कि कंप्यूटर मेमोरी में बाइनरी ट्री का प्रतिनिधित्व कैसे किया जाता है। प्रतिनिधित्व करने के दो अलग-अलग तरीके हैं। ये सरणी का उपयोग कर रहे हैं और लिंक्ड सूची का उपयोग कर रहे हैं। मान लीजिए हमारे पास एक ऐसा पेड़ है - सरणी प्रतिनिधित्व स्तर क्रम फैशन का उपयोग करके तत्वों को स्कैन करक