PSLG,直线切割凸多边形，和判断圆与多边形相交-白红宇的个人博客

PSLG,直线切割凸多边形，和判断圆与多边形相交

发布日期：2021-10-08 15:48:56 浏览次数：18 分类：技术文章

本文共 3544 字，大约阅读时间需要 11 分钟。

分析：

除了圆盘之外，本题的输入也是一个PSLG,因此可以按照前面叙述的算法求出各个区域。但由于本题的特殊性，不难发现把线段改成直线后答案不变，因此每个块都是凸多边形，

可以用切割凸多边形的方法求解：每读入一条线段，都把它当做直线，切割所有块。这样，我们最终得到了若干凸多边形，需要分别判断是否与圆盘相交。

如何让判断多边形是否和圆盘相交？，显然，如果多边形的边和圆周规范相交，圆盘和多变性一定相交，但反过来却不成立——圆盘和多边形相交，多边形的边和圆周不一定规范相交。

（1）即使完全没有公共点的时候，圆盘和多边形也可以相交，原因是二者可以相互内含。因此，需要判断多边形是否有顶点在圆内，还需要判断圆心是否在多边形内。

（2）如果是非规范相交,需要分情况讨论。在图中，待判断的线段（用粗线表示）完全在圆外；在图中待判断的线段则是完全在内部。判断方法很简单，只需判断线段中点是否在圆内即可。

直接切割多边形~ 判断多边形和园盘是否有公共点（面积>0）

1 内含的情况--只要多边形poly[0] 在圆内、或者圆心在多边形内

2 相交的情况-如果不是规范相交，那么不是内含，却有非零公共面积只有一种情况，就是两个点都在圆上，只有判断中点在圆上即可。

每一个案例忘记输出空行并不提示Presentation Error ，wa每次pieces更新的时候，newpieces 需要清零

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                using namespace std;const double eps=1e-6;int dcmp(double x){ if(fabs(x)
                
                 0?1:-1; //return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1);}struct point{ double x; double y; point(){} point(double x,double y):x(x),y(y){} void in() { cin>>x>>y; } void out() { cout<
                 
                  <<' '<
                  
                   <
                   
                     &sol){ double a=l.v.x; double b=l.p.x-C.c.x; double c=l.v.y; double d=l.p.y-C.c.y; double e=a*a+c*c; double f=2*(a*b+c*d); double g=b*b+d*d-C.r*C.r; double delta=f*f-4*e*g; if(dcmp(delta)<0) return 0; if(dcmp(delta)==0) { t1=t2=-f/(2*e); sol.push_back(l.ppoint(t1)); return 1; } else { t1=(-f-sqrt(delta))/(2*e); t2=(-f+sqrt(delta))/(2*e); sol.push_back(l.ppoint(t1)); sol.push_back(l.ppoint(t2)); return 2; }}bool onleft(line l,point p){ return cross(l.v,p-l.p)>0;}point getintersection(line a,line b){ point u=a.p-b.p; double t=cross(b.v,u)/cross(a.v,b.v); return a.p+a.v*t;}bool sgementproperintersection(point a1,point a2,point b1,point b2){ double c1=cross(a2-a1,b1-a1),c2=cross(a2-a1,b2-a1), c3=cross(b2-b1,a1-b1),c4=cross(b2-b1,a2-b1); return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;}bool onsegment(point p,point a1,point a2){ return dcmp(cross(a1-p,a2-p))==0&&dcmp(dot(a1-p,a2-p))<0;}typedef vector
                    
                      Polygon;double PolygonArea(Polygon poly){ double area=0; int n=poly.size(); for(int i=1;i
                     
                       pieces,newpieces;Polygon CutPolygon(Polygon poly,point a,point b){ Polygon newPoly; int n=poly.size(); for(int i=0;i
                      
                       =0) newPoly.push_back(c); if(dcmp(cross(b-a,d-c))!=0) { point ip=getintersection(line(c,d-c),line(a,b-a)); if(onsegment(ip,c,d)) newPoly.push_back(ip); //此时必须用不含端点的“在线段上" } } return newPoly;}void cut(point a,point b){ newpieces.clear(); //仅仅是一个temp 记得清空 for(int i=0;i
                       
                        =3) newpieces.push_back(left); if(right.size()>=3) newpieces.push_back(right); } pieces=newpieces;}bool isPointInPolygon(point p,Polygon poly){ int wn=0; int n=poly.size(); for(int i=0;i
                        
                         0&&d1<=0&&d2>0) wn++; if(k<0&&d2<=0&&d1>0) wn--; } if(wn!=0) return 1; else return 0;}double length2(point a){ return dot(a,a);}bool inCircle(Circle C,point p) //圆周不算{ if(dcmp(length2(p-C.c)-C.r*C.r)<0) return 1; else return 0;}bool CircleSegIntersection(Circle C,point a,point b) //线段端点不算{ double t1,t2; vector
                         
                           sol; if(getLineCircleIntersection(line(a,b-a),C,t1,t2,sol)<=1) return 0; if(dcmp(t1)>0&&dcmp(t1-1)<0) return 1; if(dcmp(t2)>0&&dcmp(t2-1)<0) return 1; return 0;}bool CirclePolyIntersection(Circle C,Polygon poly){ if(isPointInPolygon(C.c,poly)) return 1; if(inCircle(C,poly[0])) return 1; point a,b; int n=poly.size(); for(int i=0;i
                          
                            ans; for(int i=0;i
                           
                            >n>>m>>l>>w) { if(!n) break; pieces.clear(); Polygon bbox; bbox.push_back(point(0,0)); bbox.push_back(point(l,0)); bbox.push_back(point(l,w)); bbox.push_back(point(0,w)); pieces.push_back(bbox); point a,b; for(int i=0;i
                            
                             >C.c.x>>C.c.y>>C.r; Query(C); } printf("\n"); } return 0;}

转载地址：https://blog.csdn.net/ONE_PIECE_HMH/article/details/45750073 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：简单三维几何，判断俩个三角形是否相交

下一篇：UVA LA3218 找边界，PSLG

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章