Judgment of points inside and outside polygon

Judgment of points inside and outside the polygon

remarks ：

Radiographic reference 1,

Angle method code source ,

chart 1 source

The main basis is 《 Introduction to algorithm competition classic training guide 》 The idea of ,2020.7.4

Ray method and rotation method are applicable to all polygons

One 、 Ray method ：

From this point of view , A ray leading to infinity , Determine the position of the point according to the intersection condition

advantage ： Simple , Commonly used in algorithm competitions

shortcoming ： If the polygon is curved , You can't use the following code

Algorithm ：

1. Take the point to be judged as the starting point , Any ray , Calculate the number of intersections between the ray and the polygon
2. If there are an even number of intersections , The point is outside the polygon ; otherwise , Point in polygon
3. If it coincides or intersects with the endpoint of the line segment , Then you have to make complex judgments ; At this time, another ray can be taken

The following is 《 Introduction to algorithm competition classic training guide 》 Code for

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 the edge intersects the right end of the ray 
        if(k<0 && d1>0  &&d2<=0)wn--;  // If the edge intersects the left end of the ray 
    }
}

The code uses the ray method , Let this ray be to the right , So its negative direction is to do , If the intersection is on the right , The number of intersections is marked up , If the intersection is on the left , The number of intersections is reduced . Let's take a closer look at the following analysis .

Calculate the intersection of ray and polygon , We must first rule out the case that there is no intersection , If it is shown in the figure, it is

and （ Remove the point on the edge ） The case where there is an intersection is

This is also the idea of the last two sentences of the code .

Two 、 Corner method ：

Calculate the corner of each side of the polygon , Finally, it is eliminated as 0, Then the point is inside the polygon , Otherwise the point is outside the polygon

advantage ： Even if the edges of a polygon are curved , This algorithm is also unaffected

shortcoming ： Need to calculate a large number of inverse trigonometric functions , Not only is it slow , And it is easy to produce precision error .

Algorithm ：

1. Add up the corners of each side of the polygon ： If it is 360 degree , Then the point is in the polygon ; If it is 0 degree , The point is outside the polygon ; If it is 180 degree , Then point on the edge of the polygon ;

2. The inverse trigonometric function is used to find the angle directly , Poor accuracy and time-consuming

3. If it's a convex polygon , Just cross product

#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;
}