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