凸包ジャービスのアルゴリズムまたはC++でのラッピング

このチュートリアルでは、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)