Convex Hull Jarvis의 알고리즘 또는 C++의 래핑

이 튜토리얼에서는 Jarvis의 알고리즘을 사용하여 주어진 점 집합의 볼록 껍질을 찾는 프로그램에 대해 논의할 것입니다.

볼록 껍질은 그림 내부의 경계에 있는 모든 주어진 점을 포함하는 가장 작은 다각형 볼록 그림입니다.

Jarvis의 알고리즘에서는 가장 왼쪽에 있는 점을 선택하고 랩핑 점을 시계 방향으로 계속 이동합니다.

예시

#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)