判断点在多边形的内外

方法一：扫描法(使用于任意多边形)

通常情况下，当射线与多边形的交点个数是奇数时，Q在多边形内，是偶数时，Q在多边形外。

通常将射线设为水平向右，那么就有一些特殊情况值得考虑

1.射线与多边形的顶点相交，这是交点只能计算一个。

2.射线与多边形顶点的交点不应该被计算

3.射线与多边形的一条边重合，这条边应该被忽略

算法描述：首先，对于多边形的水平边不做考虑，其次，对于多边形的顶点和射线相交的情况，如果该顶点时其所属的边上纵坐标较大的顶点，则计数，否则忽略该点，最后，对于Q在多边形上的情形，直接判断Q是否属于多边形。

时间复杂度分析：O(n)

注意：点的输入必须有顺序，不是顺时针就是逆时针

附上代码：

2. #include<iostream>
3. #include<cstdio>
5. using namespace std;
7. const int maxn=110;
8. const double eps=1e-5;
10. struct point{
11. double x,y;
12. };
13. point poly[maxn];
15. int n,q;
17. bool onsegment(point pi,point pj,point Q)
18. {
19. if((Q.x-pi.x)*(pj.y-pi.y)==(pj.x-pi.x)*(Q.y-pi.y)&&min(pi.x,pj.x)<=Q.x&&Q.x<=max(pi.x,pj.x)&&min(pi.y,pj.y)<=Q.y&&Q.y<=max(pi.y,pj.y)){
20. return true;
21. }else{
22. return false;
23. }
24. }
26. bool insidepolygon(point p)
27. {
28. int counter=0;
29. double xinters;
30. point p1,p2;
31. p1=poly[0];
32. for(int i=1;i<=n;i++){
33. p2=poly[i%n];
34. if(onsegment(p1,p2,p)){
35. return true;
36. }
37. if(p.y>min(p1.y,p2.y)){
38. if(p.y<=max(p1.y,p2.y)){
39. if(p.x<=max(p1.x,p2.x)){
40. if(p1.y!=p2.y){
41. xinters=(p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
42. if(p1.x==p2.x||p.x<=xinters){
43. counter++;
44. }
45. }
46. }
47. }
48. }
49. p1=p2;
50. }
51. if(counter%2==0){
52. return false;
53. }
54. return true;
55. }
57. int main()
58. {
59. point p;
60. scanf('%d%d',&n,&q);
61. for(int i=0;i<n;i++){
62. scanf('%lf%lf',&poly[i].x,&poly[i].y);
63. }
64. for(int i=0;i<q;i++){
65. scanf('%lf%lf',&p.x,&p.y);
66. if(insidepolygon(p)){
67. printf('within\n');
68. }else{
69. printf('outside\n');
70. }
71. }
72. return 0;
73. }

方法二：叉乘判别法(只适用于凸多边形)

设这个多边形的边数为n。选一条边作为1号边，然后按照顺时针或者逆时针给每条边编号，连接第i(i=1,2,3......,n)条边的第一个端点和要测试的点得到一个向量vi。连接第一个端点与第二个端点得到向量ui，都以第一个端点为起点，作叉积vi*ui，记录结果。除了第一条边以外，都与前一次运算得到的叉积作乘积。如果为正则继续判断，知道遍历所有边，若全部满足，则证明点在多边形内，否则，证明点在多边形外。

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=110;
struct point{
    double x,y;
};
point poly[maxn];
int n,q;
double multi(point p1,point p2,point p0)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
bool isinside(point p)
{
    double pre,now;
    for(int i=0;i<n;i++){
        now=multi(p,poly[i],poly[(i+1)%n]);
        if(i>0){
            if(pre*now<0){
                return 0;
            }
        }
        pre=now;
    }
    return true;
}
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(isinside(p)){
            printf('Yes\n');
        }else{
            printf('No\n');
        }
    }
    return 0;
}

方法三：角度和的判断法(适用于任意多边形)

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

1. #include<iostream>
2. #include<cstdio>
3. #include<cmath>
5. using namespace std;
7. const int maxn=110;
8. const double pi=3.1415926;
10. struct point{
11. double x,y;
12. };
13. point poly[maxn];
15. int n,q;
17. double ang(double x1,double y1,double x2,double y2)
18. {
19. double ans=x1*x2+y1*y2;
20. double base=sqrt(x1*x1+y1*y1)*sqrt(x2*x2+y2*y2);
21. ans/=base;
22. return acos(ans);
23. }
25. int inpolygon(point p)
26. {
27. double angle=0;
28. for(int i=0;i<n;i++){
29. double x1=poly[i].x-p.x;
30. double y1=poly[i].y-p.y;
31. double x2=poly[(i+1)%n].x-p.x;
32. double y2=poly[(i+1)%n].y-p.y;
33. angle+=ang(x1,y1,x2,y2);
34. }
35. if(fabs(angle-2*pi)<0.000001){
36. return true;
37. }else{
38. return false;
39. }
40. }
42. int main()
43. {
44. scanf('%d%d',&n,&q);
45. for(int i=0;i<n;i++){
46. scanf('%lf%lf',&poly[i].x,&poly[i].y);
47. }
48. point p;
49. for(int i=0;i<q;i++){
50. scanf('%lf%lf',&p.x,&p.y);
51. if(inpolygon(p)){
52. printf('Yes\n');
53. }else{
54. printf('No\n');
55. }
56. }
57. return 0;
58. }