凸包Jarvis的算法或C ++包装

在本教程中，我们将讨论一个使用Jarvis算法查找给定点集的凸包的程序。

凸包是最小的多边形凸图，其中包含图内边界上的所有给定点。

在Jarvis的算法中，我们选择最左边的点并保持包裹点沿顺时针方向移动。

示例

#include <bits/stdc++.h>
using namespace std;
//点的结构
struct Point{
   int x, y;
};
//计算点的位置
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
}
//打印凸包
void convexHull(Point points[], int n){
   if (n < 3) return;
   vector<Point> hull;
   //计算最左边的点
   int l = 0;
   for (int i = 1; i < n; i++)
   if (points[i].x < points[l].x)
   l = i;
   //沿顺时针方向移动
   int p = l, q;
   do{
      //将当前点添加到结果
      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)