Convex Hull Jarvis's Algorithm hoặc Wrapping in C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm phần lồi của một tập hợp điểm nhất định bằng cách sử dụng Thuật toán của Jarvis.

Vỏ lồi là hình đa giác lồi nhỏ nhất chứa tất cả các điểm đã cho hoặc nằm trên đường biên bên trong hình.

Trong thuật toán của Jarvis, chúng tôi chọn điểm ngoài cùng bên trái và tiếp tục di chuyển các điểm theo chiều kim đồng hồ.

Ví dụ

#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;
}

Đầu ra

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