c语言凸包算法,要求: 1、给定平面上的坐标范围(minx,miny,maxx,maxy) ,随机生成范围内100个 2、求100个点的凸包; 3、按顺时针方向输出凸包多边形的坐标;
时间: 2024-05-05 14:22:21 浏览: 133
以下是C语言的凸包算法的实现代码,使用的是Graham扫描法:
```c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define PI 3.14159265358979323846
typedef struct Point {
double x;
double y;
} Point;
typedef struct Stack {
Point* arr;
int top;
} Stack;
int cmp(const void* a, const void* b) {
Point* p1 = (Point*)a;
Point* p2 = (Point*)b;
if (p1->x != p2->x) {
return p1->x < p2->x ? -1 : 1;
}
else {
return p1->y < p2->y ? -1 : 1;
}
}
double cross_product(Point p1, Point p2, Point p3) {
return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}
double distance(Point p1, Point p2) {
return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2));
}
void push(Stack* s, Point p) {
s->top++;
s->arr[s->top] = p;
}
Point pop(Stack* s) {
Point p = s->arr[s->top];
s->top--;
return p;
}
void print_points(Point* points, int n) {
for (int i = 0; i < n; i++) {
printf("(%f, %f)\n", points[i].x, points[i].y);
}
}
void print_stack(Stack s) {
for (int i = 0; i <= s.top; i++) {
printf("(%f, %f)\n", s.arr[i].x, s.arr[i].y);
}
}
void graham_scan(Point* points, int n) {
qsort(points, n, sizeof(Point), cmp);
Stack s;
s.arr = (Point*)malloc(n * sizeof(Point));
s.top = -1;
push(&s, points[0]);
push(&s, points[1]);
for (int i = 2; i < n; i++) {
while (s.top >= 1 && cross_product(s.arr[s.top - 1], s.arr[s.top], points[i]) <= 0) {
pop(&s);
}
push(&s, points[i]);
}
int lower_hull_size = s.top + 1;
push(&s, points[n - 2]);
for (int i = n - 3; i >= 0; i--) {
while (s.top >= lower_hull_size && cross_product(s.arr[s.top - 1], s.arr[s.top], points[i]) <= 0) {
pop(&s);
}
push(&s, points[i]);
}
printf("Convex Hull Points (in clockwise order):\n");
print_stack(s);
free(s.arr);
}
int main() {
double minx = -10.0;
double miny = -10.0;
double maxx = 10.0;
double maxy = 10.0;
int n = 100;
Point* points = (Point*)malloc(n * sizeof(Point));
for (int i = 0; i < n; i++) {
points[i].x = (double)rand() / RAND_MAX * (maxx - minx) + minx;
points[i].y = (double)rand() / RAND_MAX * (maxy - miny) + miny;
}
printf("Randomly Generated Points:\n");
print_points(points, n);
graham_scan(points, n);
free(points);
return 0;
}
```
上述代码中,首先定义了一个`Point`结构体和一个`Stack`结构体,分别表示平面上的点和栈。然后实现了一个用于比较两个点大小的函数`cmp`,用于在排序时确定点的顺序。接着实现了计算叉积和计算两点之间距离的函数。然后实现了栈的`push`和`pop`操作,以及用于打印点集和栈的函数。
最后,实现了Graham扫描法的主要部分`graham_scan`函数。该函数首先对点集进行排序,然后依次遍历每个点,将其加入凸壳栈中。每次加入点后,检查凸壳栈中前两个点与新加入的点的叉积是否为正,如果不是则将栈顶元素弹出,直到满足条件为止。遍历完所有点后,再从后往前遍历一次点集,重复上述步骤,得到完整的凸包。最后按顺时针方向输出凸包多边形的坐标。
在`main`函数中,首先指定了点集的范围和点的个数,然后随机生成点集,并打印出来。最后调用`graham_scan`函数求解凸包。