二维实现礼品包装算法的C ++程序
我们将开发一个C++程序来实现二维包装礼品包装算法。礼品包装算法是一种用于计算给定点集的凸包的算法。
算法
开始 函数convexHull()来查找一组n点的凸包： 必须至少有三点。 初始化结果。 找到最左边的点。 从最左端开始，继续逆时针移动 直到再次到达起点。 打印结果。 结束
范例程式码
#include <iostream>
using namespace std;
#define INF 10000
struct P {
int x;
int y;
};
int orient(P a, P b, P c) {
int v = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
if (v == 0)
return 0; // colinear
return (v >0) ? 1 : 2; // clock or counterclock wise
}
void convexHull(P points[], int m) {
if (m < 3)//at least three points required
return;
int n[m];
for (int i = 0; i < m; i++)
n[i] = -1;
int l = 0;//initialize result.
for (int i = 1; i < m; i++)
if (points[i].x < points[l].x)
l = i; //find left most point
int p = l, q;
do {
q = (p + 1) % m;
for (int i = 0; i < m; i++)
if (orient(points[p], points[i], points[q]) == 2)
q = i;
n[p] = q;
p = q;
} while (p != l);
for (int i = 0; i < m; i++) {
if (n[i] != -1)
cout << "(" << points[i].x << ", " << points[i].y << ")\n";
}
}
int main() {
P points[] = {{0, 4}, {2, 1}, {2, 3}, {4, 1}, {3, 0}, {1, 1}, {7, 6}};
cout << "The points in the convex hull are: ";
int n = sizeof(points) / sizeof(points[0]);
convexHull(points, n);
return 0;
}输出结果
The points in the convex hull are: (0, 4) (4, 1) (3, 0) (1, 1) (7, 6)