判定点は任意のポリゴン(バンプエッジを含む)内

タイトルアドレス:http://www.cnblogs.com/try86/archive/2012/04/22/2465416.html この問題は、端に点を置くと、点も多角形内に見える.凸多角形には多角形内に点を判断する方法がたくさんありますが、凹多角形であれば頼りになる方法は多くありません.グーグルしてみてください.
1)水平/垂直交差点数判別法(任意の多角形に適用する凹凸辺形を含む)Pから水平左への放射線を行う場合、Pが多角形内部にある場合、この放射線と多角形との交点は必ず奇数であり、Pが多角形外部にある場合、交点個数は必ず偶数(0も含む)であることに注意する.したがって,多角形の各エッジを順番に考慮し,交点の総個数を求めることができる.コードを参照してください.

 
//offset        
//on_edge              
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<time.h>
using namespace std;
const int offset=1000;
const double eps=1e-8;
struct Point{
    double x,y;
}p[105];
double cross(Point pi,Point pj,Point pk){ // (pi,pj)X(pi,pk)
    return (pj.x-pi.x)*(pk.y-pi.y)-(pj.y-pi.y)*(pk.x-pi.x);
}
int InPolygon(const Point *arr,const int &len,const Point &p,int on_edge=1){
 Point q;
 int i=0,counter;
 while(i<len){
   q.x=rand()+offset;//          q
   q.y=rand()+offset;// p   q      L
   for(counter=i=0;i<len;i++){//              
    if(fabs(cross(p,arr[i],arr[(i+1)%len]))<eps &&
    (arr[i].x-p.x)*(arr[(i+1)%len].x-p.x)<eps && (arr[i].y-p.y)*(arr[(i+1)%len].y-p.y)<eps)
      return on_edge; // p   ,  on_edge
    else if(fabs(cross(p,q,arr[i]))<eps) break; // arr[i]   pq ，     ，  q
    else if(cross(p,arr[i],q)*cross(p,arr[(i+1)%len],q)<-eps &&
      cross(arr[i],p,arr[(i+1)%len])*cross(arr[i],q,arr[(i+1)%len])<-eps)
      counter++;
   }
 }
 return counter&1;
}
int main(){
 int n,m;
 while(scanf("%d",&n)==1){
   for(int i=0;i<n;i++)
    scanf("%lf%lf",&p[i].x,&p[i].y);
   scanf("%d",&m);
   Point temp;
   while(m--){
     scanf("%lf%lf",&temp.x,&temp.y);
     if(InPolygon(p,n,temp))
      puts("Yes");
     else
      puts("No");
   }
 }
 return 0;

2)角度と判別法この方法の原理は,多角形内の一点(辺上の点を含まない)から各隣接点への挟み角の和が360度である.ネット上で多くの人がこの方法を転載して、任意の多角形に適用すると言っていますが、実はそうではありません.もちろん多くの人のテンプレートはやはり上の方法を使っています.の角度と判別法は凸多角形にしか適していないが,この問題に対して,この問題に対してグループデータを出し,点は時計回りに与えられる:4 0 0 5 10 0 5 5 1 5 0この多角形は凹多角形であり,点(5,0)は多角形内にはないが,挟み角の和は360度であるため,この方法では使えない  この方法については,以下のコードを提出し,断固としてWA