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

《判断点是否在多边形内地5种方法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用标准文案判断点是否在多边形内（凸包和任意多边形分类讨论）/*POJ1548:判断是否为凸包，判断点（圆是否在凸包内），其中判定点是否在多边形内是主要部分SampleInput51.51.52.01.01.02.02.01.752.01.03.00.02.051.51.52.01.01.02.02.01.752.51.03.00.02.01SampleOutputHOLEISILL-FORMEDPEGWILLNOTFIT*///法1、2：叉积判定、面积法判定（适用于凸包）。#include#include#include

2、tring>#include#include#include#include#include#include

3、01即使是小于0，但也当做是0，关系到后面数据处理{if(fabs(d)0?1:-1;}structpoint{doublex,y;booloperator==(constpoint&p){returnFabs(x-p.x)==0&&Fabs(y-p.y)==0;}}p[maxn];intn;doublepegx,pegy,pegr,max_x,max_y;doublex_multi(pointp1,pointp2,pointp3){return(p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)

4、*(p2.y-p1.y);}boolpoint_is_inside()//叉积判断点在凸包内部！只针对于凸多边形。圆心连接每一条边的端点得到的叉积必须同向。以此可以延伸出面积法判定点是否在凸包内部。这两种方法都局限于在凸多边形{pointp1;p1.x=pegx,p1.y=pegy;inti,flag=1;doubletmp1=0.0,tmp2;for(i=0;i

5、}精彩文档实用标准文案doubleLen_ab(pointp1,pointp2){returnsqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}boolcircle_is_inside()//判断圆是否在凸包内{if(pegr==0.0)returntrue;inti;doubleans;pointpeg,t;peg.x=pegx,peg.y=pegy;for(i=0;i

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

7、if(ans-pegr<-eps)returnfalse;}returntrue;}intmain(){inti,j;while(scanf("%d",&n)&&n>=3){scanf("%lf%lf%lf",&pegr,&pegx,&pegy);for(i=0;i

8、i+1)%