计算几何-多边形内核判定-HPI-poj3335

This article is made by Jason-Cow.
Welcome to reprint.
But please post the article's address.

先解决一个问题，什么是多边形内核

形象的说就是在多边形中可以找到一个区域安放一台360°摄像头，能够监视到整个凸多边形区域

用手在多边形内侧摸一圈，凹凸不平？！

对，就是这个感觉。

借助数学必修5线性规划的思想，可以将多边形的n条边

看做n个线性约束条件

然后，在二位笛卡尔坐标系下求交集就好了（显然）

证明！

题目：poj3335

好，是不是直接上半平面交？！

我想给一组数据，poj上的，反正吓得我一弹，冷静的加了一行

bool Left(L l,D A){return Cross(l.v,A-l.P)>||fabs(Cross(l.v,A-l.P))<eps;}

key

先看数据

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <cstdlib>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <map>

 #include <set>

 using namespace std;

 #define sqr(x) ((x)*(x))

 #define RG register

 #define op operator

 #define IL inline

 typedef double db;

 typedef bool bl;

 const db pi=acos(-1.0),eps=1e-;

 struct D{

   db x,y;

   D(db x=0.0,db y=0.0):x(x),y(y){}

 };

 typedef D V;

 bl operator<(D A,D B){return A.x<B.x||(A.x==B.x&&A.y<B.y);}

 V operator+(V A,V B){return V(A.x+B.x,A.y+B.y);}

 V operator-(V A,V B){return V(A.x-B.x,A.y-B.y);}

 V operator*(V A,db N){return V(A.x*N,A.y*N);}

 V operator/(V A,db N){return V(A.x/N,A.y/N);}

 db Ang(db x){return(x*180.0/pi);}

 db Rad(db x){return(x*pi/180.0);}

 V Rotate(V A,db a){return V(A.x*cos(a)-A.y*sin(a),A.x*sin(a)+A.y*cos(a));}

 db Dis(D A,D B){return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));}

 db Cross(V A,V B){return A.x*B.y-A.y*B.x;}

 db Area(D*R,int n){

     db S=0.0;

     for(int i=;i<n;i++)S+=Cross(R[i]-R[],R[i+]-R[]);

     return S/;

 }

 db Length(D*R,int n){

     db C=0.0;

     for(int i=;i<=n;i++)C+=Dis(R[i],R[i-]);

     return C+Dis(R[n],R[]);

 }

 struct L{

   D P,v;db a;

   L(){}

   L(D P,V v):P(P),v(v){a=atan2(v.y,v.x);}

   bool operator<(const L x)const{return a<x.a;}

 };

 D Intersect(L a,L b){

   V u=a.P-b.P;

   return a.P+a.v*(Cross(b.v,u)/Cross(a.v,b.v));

 }

 bool Left(L l,D A){return Cross(l.v,A-l.P)>||fabs(Cross(l.v,A-l.P))<eps;}

 int HPI(L*l,int n,D*ans){

   int head,tail,m=;

   D*P=new D[n];L*q=new L[n];

   sort(l+,l+n+),q[head=tail=]=l[];

   for(int i=;i<=n;i++){

     while(head<tail && !Left(l[i],P[tail-]))tail--;

     while(head<tail && !Left(l[i],P[head]))  head++;

     q[++tail]=l[i];

     if(fabs(Cross(q[tail].v,q[tail-].v))<eps){

       tail--;

       if(Left(q[tail],l[i].P))q[tail]=l[i];

     }

     if(head<tail)P[tail-]=Intersect(q[tail-],q[tail]);

   }

   while(head<tail && !Left(q[head],P[tail-]))tail--;

   if(tail-head<=)return ;

   P[tail]=Intersect(q[tail],q[head]);

   for(int i=head;i<=tail;i++)ans[++m]=P[i];

   return m;

 }

 const int maxn=+;

 D P[maxn];L l[maxn];

 int main(){

     int T,n,cnt;

     for(scanf("%d",&T);T--;){

         scanf("%d",&n),cnt=;

         for(int i=;i<=n;i++){

             db a,b;scanf("%lf%lf",&a,&b);

             P[i]=D(a,b);

         }

       for(int i=n;i>=;i--)

           l[++cnt]=L(P[i],P[i-]-P[i]);

       l[++cnt]=L(P[],P[n]-P[]);

       printf("%s\n",HPI(l,n,P)>=?"YES":"NO");

     }

   return ;

 }

poj3335