[GIS算法] 多边形是否在圆内

[GIS算法] 多边形是否在圆内 - C语言实现

本文主要是介绍[GIS算法] 多边形是否在圆内 - C语言实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*@Time:20181112@Title:判断多边形是否在圆内@Desc:圆是一个凸集，判断多边形的每一个顶点是否在圆内即可*/
#include<stdio.h>
#include<stdlib.h>#define EXP 1e-8 //精度typedef struct point{double x;double y;struct point *next;
}Point, *Polygon;
typedef struct circle{Point centre;double r;
}Circle;int InitPolygon(Polygon *p); //初始化多边形
int InitCircle(Circle *c);	//初始化圆
int PolygonInCircle(Polygon p, Circle C); //多边形是否在圆内
int PointInCircle(Point A, Circle C); //点是否在圆内/*测试数据
// 第一组
11
0 0 
1 2
2 1
3 2
4 2
5 3
6 0
3 1
2 0
1 1.5
0 0
1 1
6
// 第二组
11
0 0 
1 2
2 1
3 2
4 2
5 3
6 0
3 1
2 0
1 1.5
0 0
1 1
2*/
int main() {Polygon P;Circle C;InitPolygon(&P);printf("Polygon init success\n");InitCircle(&C);printf("circle init success\n");printf("多边形是否在圆内：%d", PolygonInCircle(P, C) );return 0;
}// 返回1：创建成功
// 返回0：创建不成功，点没有闭合
int InitPolygon(Polygon *pHead) {int n;int i;Point *p,*q;double a,b;double suba, subb;scanf("%d", &n);p = NULL;for (i=0; i<n; i++) {scanf("%lf%lf", &a, &b);q = (Point *)malloc(sizeof(Point)); if (!q) exit(0);q->x = a; q->y = b;// 连接if (p==NULL) { //第一个点q->next = q; //循环队列p = q;*pHead = q;} else {suba = (*pHead)->x - a;subb = (*pHead)->y - b;if ( suba>=-EXP && suba<=EXP && subb>=-EXP && subb<=EXP) {//闭合 构造完成free(q);return 1;}p->next = q;q->next = *pHead;// 下一个p = q;}}return 0;
}// 返回1：创建成功
// 返回0：创建失败
int InitCircle(Circle *c) {scanf("%lf%lf", &c->centre.x, &c->centre.y);scanf("%lf", &c->r);return 1;
}// 多边形是否在圆内
int PolygonInCircle(Polygon head, Circle c) {Point *p;p = head;do {if ( PointInCircle(*p, c)==0 ) return 0;p = p->next;} while (p!=head);return 1;
}// 点是否在圆内
int PointInCircle(Point A, Circle C) {double d2;d2 = (A.x - C.centre.x) * (A.x - C.centre.x) + (A.y - C.centre.y) * (A.y - C.centre.y);if (d2 > C.r*C.r) {return 0;} else {return 1;}
}