四边形网格剖分代码 C++
时间: 2023-10-16 22:11:05 浏览: 43
以下是一个简单的四边形网格剖分的代码示例,使用 C 语言编写:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_POINTS 1000
typedef struct {
int x, y;
} Point;
typedef struct {
Point p1, p2;
} Line;
int point_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;
}
return p1->y - p2->y;
}
int line_cmp(const void* a, const void* b) {
Line* l1 = (Line*)a;
Line* l2 = (Line*)b;
if (l1->p1.x != l2->p1.x) {
return l1->p1.x - l2->p1.x;
}
if (l1->p1.y != l2->p1.y) {
return l1->p1.y - l2->p1.y;
}
if (l1->p2.x != l2->p2.x) {
return l1->p2.x - l2->p2.x;
}
return l1->p2.y - l2->p2.y;
}
int main() {
int n, m;
Point points[MAX_POINTS];
Line lines[MAX_POINTS];
int num_lines = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d %d", &points[i].x, &points[i].y);
}
qsort(points, n, sizeof(Point), point_cmp);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (points[j].x - points[i].x > 1) {
break;
}
if (abs(points[j].y - points[i].y) == 1) {
lines[num_lines].p1 = points[i];
lines[num_lines].p2 = points[j];
num_lines++;
}
}
}
qsort(lines, num_lines, sizeof(Line), line_cmp);
scanf("%d", &m);
for (int i = 0; i < m; i++) {
int x1, y1, x2, y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
Point p1 = {x1, y1};
Point p2 = {x2, y2};
Line query = {p1, p2};
int index = bsearch(&query, lines, num_lines, sizeof(Line), line_cmp);
if (index != -1) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}
```
这个代码示例的思路是先输入点的坐标,按照 x 坐标从小到大排序,然后遍历每一对相邻的点,如果它们的 x 坐标之差大于 1 就停止遍历,如果它们的 y 坐标之差为 1 就记录这条线段。然后输入查询的线段,按照相同的方式排序,使用二分查找判断是否存在与查询线段相交的四边形。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)