判断点是否在多边形内常用的有两种方法：射线法和转角法

 

射线法：就是从a点引一条水平向右（其实向哪个方向效果都是一样的）的射线，如果这条射线与多边形交奇数个点，则点在多边形内部

网上的代码一般是这样的

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i < nvert; j = i++) {
    if ( ((verty[i]>testy) != (verty[j]>testy)) &&
     (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       c = !c;
  }
  return c;
}

参数：

  • nvert: 多边形的顶点数
  • vertx, verty: 顶点X坐标和Y坐标分别组成的数组
  • testx, testy: 需要测试的点的X坐标和Y坐标

但实际上它处理不了这种情况

射线法会判断A点在多边形外，而实际上射线法也很难处理这种情况

所以，我们就可以选择用转角法来判断，而且转角法思路更加清晰易写

转角法：对于平面多边形来说，连接多边形内点于多边形所有顶点所形成的所有角的角度在要求精度范围内应该等于360度，如果小于360度或者大于360度，则证明不在多边形中。

例如A与BCDEF所成的五个交角度和为360度，所以a在多边形内，反之，如果角度和小于360度，则不在；

由于精度问题，我们最后计算出来的角度和与π的差的绝对值小于0.000001，就可以了；

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <string>
#include <set>
#include <string>
#define Max 9999999.0
#define ll long long
using namespace std;
typedef struct point
{
    double x1,x2,y1,y2;
}point;
point a[20000];int n,m;
int pd(double x,double y)
{
    double sum=0.0;
    for(int i=1;i<=n;i++)
    {
        if((y-a[i].y1)*(a[i].x2-a[i].x1)==(a[i].y2-a[i].y1)*(x-a[i].x1))//如果点在边上（包括顶点） 输出Yes
        {
            if(x<=max(a[i].x1,a[i].x2)&&x>=min(a[i].x1,a[i].x2)&&y<=max(a[i].y1,a[i].y2)&&y>=min(a[i].y1,a[i].y2)) return 1;
            continue;
        }
        double ab,ac,bc,cosA,A;
        ab=sqrt((a[i].x1-x)*(a[i].x1-x)+(a[i].y1-y)*(a[i].y1-y));
        ac=sqrt((a[i].x2-x)*(a[i].x2-x)+(a[i].y2-y)*(a[i].y2-y));
        bc=sqrt((a[i].x1-a[i].x2)*(a[i].x1-a[i].x2)+(a[i].y1-a[i].y2)*(a[i].y1-a[i].y2));
        cosA=(ab*ab+ac*ac-bc*bc)/(2*ab*ac);
        A=acos(cosA);
        sum+=A;

        //printf("ab=%lf ac=%lf bc=%lf cosA=%lf A=%lf acos(-1)=%lf sum=%lf\n",ab,ac,bc,cosA,A,acos(-1),sum);
    }
    if(abs(sum-2*acos(-1))<0.000001)return 1;
    return 0;
}
int main()
{
    while(scanf("%d",&n)!=EOF)//n个点
    {
        scanf("%d",&m);//m个测试点
        scanf("%lf %lf",&a[1].x1,&a[1].y1);
        for(int i=2;i<=n;i++)
        {

            scanf("%lf %lf",&a[i].x1,&a[i].y1);
            a[i-1].x2=a[i].x1;
            a[i-1].y2=a[i].y1;
            if(i==n)
            {
                a[i].x2=a[1].x1;
                a[i].y2=a[1].y1;
                continue;
            }
            a[i-1].x2=a[i].x1;
            a[i-1].y2=a[i].y1;
        }
        /*for(int i=1;i<=n;i++)
        {
            printf("a[%d].x1=%lf a[%d].y1=%lf a[%d].x2=%lf a[%d].y2=%lf\n",i,a[i].x1,i,a[i].y1,i,a[i].x2,i,a[i].y2);
        }*/
        for(int i=1;i<=m;i++)
        {
            double x,y;
            scanf("%lf %lf",&x,&y);
            if(pd(x,y)%2==0)
            {
                printf("No\n");
            }
            else printf("Yes\n");
        }
    }
}