请用C语言写一段quick hull的测试代码
时间: 2024-01-22 10:20:40 浏览: 18
以下是一个简单的 Quick Hull 算法的 C 语言实现示例。该示例使用随机点集测试了 Quick Hull 算法。在此示例中,我们假设点的坐标为整数。
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 20 // 点的数量
#define MAX_X 100 // x 坐标的最大值
#define MAX_Y 100 // y 坐标的最大值
typedef struct Point {
int x;
int y;
} Point;
int rand_int(int min, int max) {
return min + rand() % (max - min + 1);
}
void print_point(Point p) {
printf("(%d, %d)\n", p.x, p.y);
}
int get_side(Point p, Point a, Point b) {
int val = (p.y - a.y) * (b.x - a.x) - (p.x - a.x) * (b.y - a.y);
if (val > 0) {
return 1;
} else if (val < 0) {
return -1;
} else {
return 0;
}
}
int distance(Point a, Point b, Point c) {
int val = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
if (val < 0) {
val = -val;
}
return val;
}
void quickhull(Point points[], int n, Point a, Point b, int side, Point hull[], int* hn) {
int i;
int index = -1;
int max_distance = 0;
for (i = 0; i < n; i++) {
int d = distance(a, b, points[i]);
if (get_side(points[i], a, b) == side && d > max_distance) {
index = i;
max_distance = d;
}
}
if (index == -1) {
hull[(*hn)++] = b;
return;
}
quickhull(points, n, points[index], a, -get_side(points[index], a, b), hull, hn);
quickhull(points, n, points[index], b, -get_side(points[index], b, a), hull, hn);
}
void print_hull(Point hull[], int n) {
int i;
for (i = 0; i < n; i++) {
print_point(hull[i]);
}
}
int main() {
Point points[N];
Point hull[N];
int hn = 0;
int i;
srand(time(NULL));
for (i = 0; i < N; i++) {
points[i].x = rand_int(0, MAX_X);
points[i].y = rand_int(0, MAX_Y);
}
printf("Points:\n");
for (i = 0; i < N; i++) {
print_point(points[i]);
}
quickhull(points, N, (Point){0, 0}, (Point){MAX_X, 0}, 1, hull, &hn);
quickhull(points, N, (Point){MAX_X, 0}, (Point){MAX_X, MAX_Y}, 1, hull, &hn);
quickhull(points, N, (Point){MAX_X, MAX_Y}, (Point){0, MAX_Y}, 1, hull, &hn);
quickhull(points, N, (Point){0, MAX_Y}, (Point){0, 0}, 1, hull, &hn);
printf("Convex hull:\n");
print_hull(hull, hn);
return 0;
}
```
该示例在 Quick Hull 算法中使用了递归,并且在函数调用时传递了大量参数。其中 `rand_int()` 函数用于生成随机的点集,`print_point()` 函数用于打印点的坐标,`get_side()` 函数用于判断点位于直线的哪一侧,`distance()` 函数用于计算点到直线的距离,`quickhull()` 函数是 Quick Hull 算法的核心部分,用于查找凸包上的点,`print_hull()` 函数用于打印凸包的点集。