उत्तल हल जार्विस का एल्गोरिदम या सी ++ में लपेटना

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

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

जार्विस के एल्गोरिथम में, हम सबसे बाईं ओर के बिंदु का चयन करते हैं और रैपिंग पॉइंट्स को दक्षिणावर्त दिशा में घुमाते रहते हैं।

उदाहरण

#include <bits/stdc++.h>
using namespace std;
//structure of the point
struct Point{
   int x, y;
};
//calculating the position of the points
int cal_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; //collinear
   return (val > 0)? 1: 2; //clock or counterclockwise
}
//printing convex hull
void convexHull(Point points[], int n){
   if (n < 3) return;
   vector<Point> hull;
   //calculating the leftmost point
   int l = 0;
   for (int i = 1; i < n; i++)
   if (points[i].x < points[l].x)
   l = i;
   //moving in the clockwise direction
   int p = l, q;
   do{
      //adding current point to result
      hull.push_back(points[p]);
      q = (p+1)%n;
      for (int i = 0; i < n; i++){
         if (cal_orientation(points[p], points[i], points[q]) == 2)
         q = i;
      }
      p = q;
   } while (p != l); //if didn't reached the first point
   for (int i = 0; i < hull.size(); i++)
   cout << "(" << hull[i].x << ", "
   << hull[i].y << ")\n";
}
int main(){
   Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1},
   {3, 0}, {0, 0}, {3, 3}};
   int n = sizeof(points)/sizeof(points[0]);
   convexHull(points, n);
   return 0;
}

आउटपुट

(0, 3)
(0, 0)
(3, 0)
(3, 3)