点在多边形内外的判断

备注：

射线法参考1，

转角法代码来源，

图1来源

主要依据《算法竞赛入门经典训练指南》的思路，2020.7.4

射线法和转角法适用于所有多边形

一、射线法：

从这一点出发，引向无穷远点的一条射线，根据交点情况确定点的位置

优点：简单，算法竞赛中常用

缺点：如果多边形是弧形的，不能用下面的那个代码

算法：

以要判断的点为起点，任做一条射线，计算该射线与多边形的交点的数若有偶数个交点，则点在多边形外；否则，点在多边形内若与线段所在的端点处重合或相交，则要进行复杂的判断；此时可另取一条射线

如下是《算法竞赛入门经典训练指南》的代码

const double eps=1e-8; int dcmp(double x) { if(fabs(x)<eps)return 0; else return x<0?-1:1; } int isPointInPolygon(Point p,Polygon poly ) { int wn=0; int n=v.size(); for(int i=0;i<n;++i){ if(isPointonSegment(p,poly[i],poly[(i+1)%n]))return -1; int k=dcmp(Cross(poly[i+1]%n-poly[i],p-poly[i])); int d1=dcmp(poly[i].y-p.y); int d2=dcmp(poly[(i+1)%n].y-p.y); if(k>0 && d1<=0 &&d2>0)wn++; //如果边与射线的右端相交 if(k<0 && d1>0 &&d2<=0)wn--; //如果边与射线的左端相交 } }

代码采用的是射线法，令这条射线为向右，那么它的负方向就是想做，如果交点在右边，交点数就加价，如果交点在左边，交点数减减。再看下面细分析。

计算射线与多边形的交点，那要先排除没有交点的情况，以图表示则为

而（除去点在边上）有交点的情况就是

这也是代码最后两句的思路。

二、转角法：

计算多边形每条边的转角，最后相消为0，则点在多边形内部，否则点在多边形外部

优点：即使多边形的边是弧形的，此算法也不受影响

缺点：需要计算大量的反三角函数，不仅速度慢，而且容易产生精度误差。

算法：

把多边形每条边的转角加起来：如果是360度，则点在多边形内；如果是0度，点在多边形外；如果是180度，则点在多边形边上；

直接求角度要用反三角函数，精度差且费时

如果是凸多边形，就用叉积

#include<iostream> #include<cstdio> #include<cmath> using namespace std; const int maxn=110; const double pi=3.1415926; struct point{ double x,y; }; point poly[maxn]; int n,q; double ang(double x1,double y1,double x2,double y2) { double ans=x1*x2+y1*y2; double base=sqrt(x1*x1+y1*y1)*sqrt(x2*x2+y2*y2); ans/=base; return acos(ans); } int inpolygon(point p) { double angle=0; for(int i=0;i<n;i++){ double x1=poly[i].x-p.x; double y1=poly[i].y-p.y; double x2=poly[(i+1)%n].x-p.x; double y2=poly[(i+1)%n].y-p.y; angle+=ang(x1,y1,x2,y2); } if(fabs(angle-2*pi)<0.000001){ return true; }else{ return false; } } int main() { scanf("%d%d",&n,&q); for(int i=0;i<n;i++){ scanf("%lf%lf",&poly[i].x,&poly[i].y); } point p; for(int i=0;i<q;i++){ scanf("%lf%lf",&p.x,&p.y); if(inpolygon(p)){ printf("Yes\n"); }else{ printf("No\n"); } } return 0; }