凸包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)

以上是 凸包Jarvis的算法或C ++包装 的全部内容, 来源链接: utcz.com/z/334885.html

回到顶部