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

C++ . में उत्तल हल ग्राहम स्कैन

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

उत्तल पतवार सबसे छोटी बहुभुज उत्तल आकृति है जिसमें दिए गए सभी बिंदु या तो आकृति के अंदर की सीमा पर होते हैं।

ग्राहम स्कैन में, सबसे पहले बिंदुओं को सबसे निचले बिंदु तक पहुंचने के लिए क्रमबद्ध किया जाता है। फिर बिंदुओं को क्रम में घुमाया जाता है और उनके आदेश के आधार पर सीमा पर छोड़ दिया जाता है या स्वीकार किया जाता है।

उदाहरण

#include <iostream>
#include <stack>
#include <stdlib.h>
using namespace std;
struct Point{
   int x, y;
};
//point reference for sorting other points
Point p0;
//moving to the next top in stack
Point nextToTop(stack<Point> &S){
   Point p = S.top();
   S.pop();
   Point res = S.top();
   S.push(p);
   return res;
}
//swapping two points
int swap(Point &p1, Point &p2){
   Point temp = p1;
   p1 = p2;
   p2 = temp;
}
//calculating the square of difference
int distSq(Point p1, Point p2){
   return (p1.x - p2.x)*(p1.x - p2.x) +
   (p1.y - p2.y)*(p1.y - p2.y);
}
//checking the orientation of points
int orientation(Point p, Point q, Point r){
   int val = (q.y - p.y) * (r.x - q.x) -
   (q.x - p.x) * (r.y - q.y);
   if (val == 0) return 0;
   return (val > 0)? 1: 2;
}
//sorting and comparing the points
int compare(const void *vp1, const void *vp2){
   Point *p1 = (Point *)vp1;
   Point *p2 = (Point *)vp2;
   int o = orientation(p0, *p1, *p2);
   if (o == 0)
   return (distSq(p0, *p2) >= distSq(p0, *p1))? -1 : 1;
   return (o == 2)? -1: 1;
}
//printing convex hull
void convexHull(Point points[], int n){
   int ymin = points[0].y, min = 0;
   for (int i = 1; i < n; i++){
      int y = points[i].y;
      if ((y < ymin) || (ymin == y &&
      points[i].x < points[min].x))
      ymin = points[i].y, min = i;
   }
   swap(points[0], points[min]);
   p0 = points[0];
   qsort(&points[1], n-1, sizeof(Point), compare);
   for (int i=1; i<n; i++){
      while (i < n-1 && orientation(p0, points[i],
      points[i+1]) == 0)
         i++;
      points[m] = points[i];
      m++; //updating size of modified array
   }
   if (m < 3) return;
   stack<Point> S;
   S.push(points[0]);
   S.push(points[1]);
   S.push(points[2]);
   for (int i = 3; i < m; i++){
      while (orientation(nextToTop(S), S.top(), points[i]) != 2)
      S.pop();
      S.push(points[i]);
   }
   while (!S.empty()){
      Point p = S.top();
      cout << "(" << p.x << ", " << p.y <<")" << endl;
      S.pop();
   }
}
int main(){
   Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4},
   {0, 0}, {1, 2}, {3, 1}, {3, 3}};
   int n = sizeof(points)/sizeof(points[0]);
   convexHull(points, n);
   return 0;
}

आउटपुट

(0, 3)
(4, 4)
(3, 1)
(0, 0)

  1. ग्राहम स्कैन एल्गोरिथम

    उत्तल पतवार न्यूनतम बंद क्षेत्र है जो सभी दिए गए डेटा बिंदुओं को कवर कर सकता है। ग्राहम के स्कैन एल्गोरिथम उत्तल पतवार के कोने बिंदु पाएंगे। इस एल्गोरिथम में, सबसे पहले, सबसे कम बिंदु चुना जाता है। वह बिंदु उत्तल पतवार का प्रारंभिक बिंदु है। शेष n-1 शीर्षों को प्रारंभ बिंदु से वामावर्त दिशा के आधार

  1. C++ में 2-डी तल में एक बिंदु की दर्पण छवि खोजें

    इस समस्या में, हमें एक 2-डी तल में एक बिंदु P दिया जाता है और समीकरण ax + by + c =0 के बिंदु a, b, cof दिए जाते हैं। हमारा काम है 2-डी समतल में बिंदु की दर्पण छवि। समस्या को समझने के लिए एक उदाहरण लेते हैं, इनपुट P = (2, 1), a = 1, b = -1, c = 0 आउटपुट (1, 2) स्पष्टीकरण विमान ऐसा दिखता है, समाध

  1. C++ में किसी अन्य बिंदु के बारे में एक बिंदु का घूमना

    मूल बिंदु के बारे में एक बिंदु X का घूर्णन एक कोण से होता है घड़ी की विपरीत दिशा में − . द्वारा किया जाता है X by उत्पत्ति के बारे में यहां, सम्मिश्र संख्याओं के लिए फंक्शन पोलर को हेडर फाइल के तहत परिभाषित किया गया है और इसका उपयोग फेज एंगल और परिमाण का उपयोग करके एक कॉम्प्लेक्स नंबर खोजने के