判断点是否在多边形内地5种方法

1、判断点是否在多边形内（凸包和任意多边形分类讨论）/*POJ 1548:判断是否为凸包，判断点（圆是否在凸包内），其中判定点是否在多边形内是主要部分Sample Input5 1.5 1.5 2.01.0 1.02.0 2.01.75 2.01.0 3.00.0 2.05 1.5 1.5 2.01.0 1.02.0 2.01.75 2.51.0 3.00.0 2.0 1Sample OutputHOLE IS ILL-FORMEDPEG WILL NOT FIT*/法1、2:叉积判定、面积法判定(适用于凸包)#include<iostream>#include<cstdio&g

2、t;#include<cstring>#include<string>#include<cmath>#include<cstdlib>#include<queue>#include<stack>#include<map>#include<vector>#include<algorithm>using namespace std;#define maxn 10005#define eps 1e-8#define max(x,y) (x>y?x:y)#define min(x,y) (

3、x<y?x:y)int Fabs(double d) /重点精度控制，如果d精度很高，如-0.00000000001即使是小于 0,但也当做是0,关系到后面数据处理if(fabs(d)<eps) return 0;else return d>0?1:-1;struct pointdouble x,y;bool operator = (const point& p)return Fabs(x-p.x)=0&&Fabs(y-p.y)=0;pmaxn;int n;double pegx,pegy,pegr,max_x,max_y;double x_multi

4、(point p1,point p2,point p3)return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);)bool point_is_inside() /叉积判断点在凸包内部！只针对于凸多边形。圆心连接每一条边的端点得到的叉积必须同向。以此可以延伸出面积法判定点是否在凸包内部。这两种方法都局限于在凸多边形(point p1;p1.x=pegx,p1.y=pegy;int i,flag=1;double tmp1=0.0,tmp2;for(i=0;i<n;i+)(tmp2=Fabs(x_multi(p1,pi,p(i+1)%n)

5、;if(tmp1*tmp2<-eps)(flag=0;break;)tmp1=tmp2;)return flag;)double Len_ab(point p1,point p2)(return sqrt(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);)bool circle_is_inside() /判断圆是否在凸包内(if(pegr=0.0)return true;int i;double ans;point peg,t;peg.x=pegx,peg.y=pegy;for(i=0;i<n;i+) /判断圆心到多边形的每一条边的最短

6、距离是否不小于半径(t=peg;t.x+=pi.y-p(i+1)%n.y;t.y+=p(i+1)%n.x-pi.x;if(Fabs(x_multi(peg,t,pi)*x_multi(peg,t,p(i+1)%n)=1)/ 如果垂足不在线段上则选择到线段两个端点距离较小的ans=Fabs(Len_ab(peg,pi)-Len_ab(peg,p(i+1)%n)=-1?Len_ab(peg,pi):Len_ ab(peg,p(i+1)%n);else/否则ans=fabs(x_multi(peg,p(i+1)%n,pi)/Len_ab(pi,p(i+1)%n);利用面积/底边得到最小距离if(an

7、s-pegr<-eps)return false;return true;int main()int i,j;while(scanf("%d",&n)&&n>=3)scanf("%lf%lf%lf",&pegr,&pegx,&pegy);for(i=0;i<n;i+)scanf("%lf%lf",&pi.x,&pi.y);double tmp1=0.0,tmp2;bool flag=true;for(i=0;i<n;i+)/判断是否为凸包，即叉积一

8、直是顺时针或一直是逆时针(tmp2=Fabs(x_multi(pi,p(i+1)%n,p(i+2)%n);/ 精度控制，否则一直wrong if(tmp1*tmp2<-eps) ( flag=false; break; tmp1=tmp2; if(!flag) ( puts("HOLE IS ILL-FORMED"); continue; if(!point_is_inside()|!circle_is_inside() 判断圆是否在凸多边形内( puts("PEG WILL NOT FIT"); continue; puts("PEG

9、WILL FIT");)return 0;)法3:射线法判定点是否在多边形内部(适用于任意多边形)：做一条水平射线计算与多边形的交点个数 num ,如果num&1则表示在多边形内，否则在多边形外。其中射线正好交与多边形端点或者与多边形的边平行需要特判。bool Onsegment(point p1,point p2,point p3)(double min_x=min(p1.x,p2.x);double min_y=min(p1.y,p2.y);double max_x=max(p1.x,p2.x);double max_y=max(p1.y,p2.y);if(p3.x>

10、;=min_x&&p3.x<=max_x&&p3.y>=min_y&&p3.y<=max_y)return true;return false;)bool Is_intersected(point p1,point p2,point p3,point p4)/ 线段相交(double d1=x_multi(p1,p2,p3);double d2=x_multi(p1,p2,p4);double d3=x_multi(p3,p4,p1);double d4=x_multi(p3,p4,p2);if(d1*d2<0.0&

11、;&d3*d4<0.0)return true;/if(d1=0.0&&Onsegment(p1,p2,p3)/由于前面的特判，低处的交点不作为计算/ return true;if(d2=0.0&&Onsegment(p1,p2,p4)return true;if(d3=0.0&&Onsegment(p3,p4,p1)return true;if(d4=0.0&&Onsegment(p3,p4,p2)return true;return false;double Dot(point p1,point p2,point

12、 p3) /点积return (p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y);int pointonsegment(point p0,point p1,point p2) /判断点是否在线段上return Fabs(x_multi(p0,p1,p2)=0&&Fabs(Dot(p0,p1,p2)<=0;)bool point_is_inside()int i,num=0;point p1,peg,p2,p3;p1.x=999999999.0,p1.y=pegy,peg.x=pegx,peg.y=pegy;p1 坐为在射线极远处

13、的一个点，可以将射线看做线段for(i=0;i<n;i+)if(pi.y=p(i+1)%n.y)/如果和多边形的边平行，则判断起点是否在多边形的该边上，避免了和边重合算作无数多个点if(pointonsegment(peg,pi,p(i+1)%n)/ 判断点是否在线段上return true;)elsep2=pi,p3=p(i+1)%n;if(p2.y>p3.y)/画图知在与多边形端点相交的时候直接计算交的次数都无法直接判定是否在多边形的内外。一条线段的端点有高低之分，此时规定高点的交点为有效交点swap(p2,p3);if(Is_intersected(peg,p1,p2,p3)

14、num+;return num%2=1;法4:角度和判定法，适用于任意多边形。如果点在多边形内则点连接多边形每条边的到 的角度*叉积和为360.在边上白话为180.double x_multi(point p1,point p2,point p3)return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);double Len_ab(point p1,point p2)return sqrt(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);double Dot(point p1,point p2,p

15、oint p3)(return (p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y);)int pointonsegment(point p1,point p2,point p3)(return Fabs(x_multi(p1,p2,p3)=0&&Fabs(Dot(p1,p2,p3)<=0;)bool point_is_inside()(int i;double sum=0.0;for(i=0;i<n;i+)(if(p0=pi) /点在多边形端点上return true;if(pi=p(i+1)%n)/ 去重点continu

16、e;if(pointonsegment(p0,pi,p(i+1)%n)/ 点在多边形边上return true;double a=Len_ab(p0,pi);double b=Len_ab(p0,p(i+1)%n);double c=Len_ab(pi,p(i+1)%n);sum+=Fabs(x_multi(p0,pi,p(i+1)%n)*acos(a*a+b*b-c*c)/(2.0*a*b); 计算角度和，叉积大于0则加上，小于0则减去sum=fabs(sum);if(Fabs(sum-2.0*pi)=0)return true;return false; /法5:改进弧长法(适用于任意多边

17、形)一一权威算法！精度很高！以下对于该算法的解析摘自 该算法只需O(1)的附加空间，时间复杂度为O(n),系数很小；最大的优点是具有很高的精度 ，只 需做乘法和减法，若针对整数坐标则完全没有精度问题.而且实现起来也非常简单，比转角法和射线法都要好写且不易出错 .有关“弧长法”的介绍："弧长法要求多边形是有向多边形 ，一般规定沿多边形的正向，边的左 侧为多边形的内侧域.以被测点为圆心作单位圆 ，将全部有向边向单位圆作径向投影，并计算其中单位圆上弧长的代数和，若代数和为0,则点在多边形外部；若代数和为2兀,则点在多边形 内部;若代数和为兀，则点在多边形上."根据上面的介绍，其实

18、弧长法就是转角法，但它的改进方法比较比较厉害：将坐标原点平移到被测点P,这个新坐标系将平面划分为4个象限，对每个多边形顶点P,只考虑其所在的象限，然后按邻接顺序访问多边形的各个顶点P,分析Pi和Pi+1,有下列三种情况：(1) Pi+1在Pi的下一象限，此时弧长和加兀/2;(2) Pi+1在Pi的上一象限，此时弧长和减兀/2;(3) Pi+1在 Pi的相对象限，首先计算f=pi+1.y*pi.x-pi+1.x*pi.y( 叉积)，若f=0,则点在多边形上；若f<0,弧长和减兀；若f>0,弧长和加兀.最后对算出的代数和和上述的情 况一样判断即可.实现的时候还有两点要注意 ：1>

19、若P的某个坐标为0时，一律当正号处理；2>若被测点和多边形的顶点重合时要特殊处理.还有一个问题那就是当多边形的某条边在坐标轴上而且两个顶点分别在原点的两侧时会出错，如边(3,0)>(-3,0),按以上的处理，象限分别是第一和第二，这样会使代数和加兀/2,有 可能导致最后结果是被测点在多边形外，而实际上被测点是在多边形上(该边穿过该点).对于这点，处理办法是：每次计算Pi和Pi+1时，就计算叉积和点积，判断该点是否在该边 上,是则判断结束，否则继续上述过程，这样牺牲了时间，但保证了正确性.具体实现的时候，由于只需知道当前点和上一点的象限位置，所以附加空间只需 O(1).实现的时候可以把上述的"兀/2"改成1,"兀"改成2,这样便可以完全使用整数进行计算，不必考虑顶点的顺序，逆时针和顺时针都可以处理，只是最后的代数和符号不同而已int get_t