计算点在不在多边形内部

射线法,代码很明白,也理解了。有些小地方应该注意下

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
const double esp = 1e-8;
struct Point{
	double x, y;
}pnt[maxn];
double cross(double a, double b, double c, double d){
	return a*d - b*c;
}
int Is_online(Point a, Point b, Point c){
	if(abs(cross(a.x-b.x, a.y-b.y, c.x-b.x, c.y-b.y))<esp && 
		a.x >= min(b.x,c.x) && a.x<=max(b.x,c.x) && 
			a.y>=min(b.y,c.y) && a.y<= max(b.y,c.y))
		return 1;
	return 0;
}
int main(){
	int n,m;
	Point a, b, c, d;
	while(scanf("%d",&n) != EOF){
		int flag = 0, js = 0;
		for(int i=0; i<n; i++)
			scanf("%lf%lf", &pnt[i].x, &pnt[i].y);
		scanf("%d", &m);
		while(m--){
			flag = js = 0;
			scanf("%lf%lf", &a.x, &a.y);
			b.x = -100; b.y=a.y;
			for(int i=0; i<n; i++){
				c.x = pnt[i].x;
				c.y = pnt[i].y;
				d.x = pnt[ (i+1)%n ].x;
				d.y = pnt[ (i+1)%n ].y;
			if(Is_online(a, c, d)){
				flag = 1;break;
			}
			if(c.y!=d.y && a.y>=min(c.y,d.y) && a.y<max(c.y,d.y))//只能等于一个端点
				if(cross(a.x-d.x, a.y-d.y, c.x-d.x, c.y-d.y)*cross(b.x-d.x, b.y-d.y, c.x-d.x, c.y-d.y) < 0)
					js++;
			}
			if(js&1)
				flag = 1;
			if(flag)
				printf("Yes\n");
			else
				printf("No\n");
		}
	}
	//system("pause");
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注