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

判断点是否在多边形内（凸包和任意多边形分类讨论） /* POJ 1548:判断是否为凸包，判断点（圆是否在凸包内），其中判定点是否在多边形内是主要部分 Sample Input 5 1.5 1.5 2.0 1.0 1.0 2.0 2.0 1.75 2.0 1.0 3.0 0.0 2.0 5 1.5 1.5 2.0 1.0 1.0 2.0 2.0 1.75 2.5 1.0 3.0 0.0 2.0 1 Sample Output HOLE IS ILL-FORMED PEG WILL NOT FIT */ //法1、2：叉积判定、面积法判定（适用于凸包）。 #includeiostream #includecstdio #includecstring #includestring #includecmath #includecstdlib #includequeue #includestack #includemap #includevector #includealgorithm using namespace std; #define maxn 10005 #define eps 1e-8 #define max(x,y) (xy?x:y) #define min(x,y) (xy?x:y) int Fabs(double d) //重点:精度控制，如果d精度很高，如-0.00000000001即使是小于0，但也当做是0，关系到后面数据处理 { if(fabs(d)eps) return 0; else return d0?1:-1; } struct point { double x,y; bool operator == (const point p) { return Fabs(x-p.x)==0Fabs(y-p.y)==0; } }p[maxn]; int n; double pegx,pegy,pegr,max_x,max_y; 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); } bool point_is_inside() //叉积判断点在凸包内部！ 只针对于凸多边形。圆心连接每一条边的端点得到的叉积必须同向。 以此可以延伸出面积法判定点是否在凸包内部。这两种方法都局限于在凸多边形 { point p1; p1.x=pegx,p1.y=pegy; int i,flag=1; double tmp1=0.0,tmp2; for(i=0;in;i++) { tmp2=Fabs(x_multi(p1,p[i],p[(i+1)%n])); 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;in;i++) //判断圆心到多边形的每一条边的最短距离是否不小于半径 { t=peg; t.x+=p[i].y-p[(i+1)%n].y; t.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]); else ans=fabs(x_multi(peg,p[(i+1)%n],p[i]))/Len_ab(p[i],p[(i+1)%n]); // 否则利用面积/底边得到最小距离 if(ans-pegr-eps) return false; } return true; } int main() { int i,j; w