精华内容
下载资源
问答
  • PSLG,直线切割凸多边形,和判断圆多边形相交
    千次阅读
    2015-05-15 22:04:18

    分析:

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

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

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

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

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

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

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

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


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

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<algorithm>
    #include<cmath>
    #include<cctype>
    #include<string>
    #include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<vector>
    using namespace std;
    const double eps=1e-6;
    int dcmp(double x)
    {
        if(fabs(x)<eps) return 0;
        return 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<<x<<' '<<y<<endl;
      }
      point operator + (const point &t) const
      {
          return point(x+t.x,y+t.y);
      }
      point operator - (const point &t) const
      {
          return point(x-t.x,y-t.y);
      }
      point operator * (const double &t) const
      {
          return point(x*t,y*t);
      }
      point operator / (const double &t) const
      {
          return point(x/t,y/t);
      }
      bool operator < (const point &t) const
      {
          return (dcmp(x-t.x)<0||(dcmp(x-t.x)==0&&dcmp(y-t.y)<0));
      }
      bool operator == (const point &t) const
      {
          return dcmp(x-t.x) ==0 &&dcmp(y-t.y)==0;
      }
    };
    double cross(point a,point b)
    {
        return a.x*b.y-a.y*b.x;
    }
    double dot(point a,point b)
    {
        return a.x*b.x+a.y*b.y;
    }
    double length(point a)
    {
        return sqrt(dot(a,a));
    }
    point nomal(point t)
    {
        double l=length(t);
        return  point(-t.y/l,t.x/l);
    }
    struct line
    {
        point p;
        point v;
        double ang;
        line() {}
        line(point p,point v):p(p),v(v){
            ang=atan2(v.y,v.x);
        }
        bool operator < (const line &l) const
        {
            return ang<l.ang;
        }
        point ppoint(double t)
        {
            return point(p+v*t);
        }
    };
    struct Circle
    {
        point c;
        double r;
        Circle(point c=point(0,0),double r=0):c(c),r(r) {}
    
        point ppoint(double a)
        {
            return point(c.x+r*cos(a),c.y+r*sin(a));
        }
    };
    int getLineCircleIntersection(line l,Circle C,double &t1,double &t2,vector<point> &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<point> Polygon;
    double PolygonArea(Polygon poly)
    {
        double area=0;
        int n=poly.size();
        for(int i=1;i<n-1;i++)
        {
            area+=cross(poly[i]-poly[0],poly[(i+1)%n]-poly[0]);
        }
        return area/2;
    }
    
    vector<Polygon> pieces,newpieces;
    
    Polygon CutPolygon(Polygon poly,point a,point b)
    {
        Polygon newPoly;
        int n=poly.size();
    
        for(int i=0;i<n;i++)
        {
            point c=poly[i];
            point d=poly[(i+1)%n];
            if(dcmp(cross(b-a,c-a))>=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<pieces.size();i++)
        {
            Polygon poly=pieces[i];
    
            Polygon left=CutPolygon(poly,a,b);
            Polygon right=CutPolygon(poly,b,a);
            if(left.size()>=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<n;i++)
        {
            if(onsegment(p,poly[i],poly[(i+1)%n])) return -1;
            int  k=dcmp(cross(poly[(i+1)%n]-poly[i],p-poly[i]));
            int  d1=dcmp(poly[i].y-p.y);
            int  d2=dcmp(poly[(i+1)%n].y-p.y);
    
            if(k>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<point> 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<n;i++)
        {
            a=poly[i];
            b=poly[(i+1)%n];
            if(CircleSegIntersection(C,a,b)) return 1;
            if(inCircle(C,(a+b)/2)) return 1;
        }
        return 0;
    }
    void Query(Circle circle)
    {
        vector<double> ans;
        for(int i=0;i<pieces.size();i++)
            if(CirclePolyIntersection(circle,pieces[i]))
        {
            ans.push_back(fabs(PolygonArea(pieces[i])));
        }
        sort(ans.begin(),ans.end());
    
        cout<<ans.size();
        for(int i=0;i<ans.size();i++)
        {
            printf(" %.2f",ans[i]);
        }
        cout<<endl;
    }
    
    int main()
    {
        int n,m,l,w;
        Circle C;
        while(cin>>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<n;i++)
            {
                a.in();
                b.in();
                cut(a,b);
            }
            for(int i=0;i<m;i++)
            {
                cin>>C.c.x>>C.c.y>>C.r;
                Query(C);
            }
            printf("\n");
        }
        return 0;
    }
    


    更多相关内容
  • 判断两个多边形是否相交 ,当前认为一个点相交也是相交,可针对凹多边形和凸边型等多复杂的多边形进行相交判断,采用java实现,因为网上java实现的比较少,所以这里写下如何实现,适用于碰撞检测,地图等等应用场景

    判断两个多边形是否相交 ,当前认为一个点相交也是相交,可针对凹多边形和凸边型等多复杂的多边形进行相交判断,采用java实现,因为网上java实现的比较少,所以这里写下如何实现,适用于碰撞检测,地图等等应用场景

    入口方法:intersectionJudgment

    package org.dxl;
    
    import lombok.AllArgsConstructor;
    import lombok.Data;
    import lombok.NoArgsConstructor;
    import lombok.experimental.Accessors;
    import lombok.extern.slf4j.Slf4j;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collection;
    import java.util.List;
    
    /**
     * * @projectName launcher2
     * * @title Test
     * * @package org.dxl
     * * @description  判断两个多边形是否相交
     * * @author IT_CREAT     
     * * @date  2020 2020/11/5/005 22:06  
     * * @version
     */
    @Slf4j
    public class Test {
        /*
        第一步:快速排除,以某一个多边形参照物,沿着此多边形画矩形,用矩形将多边形包起来,
        在判断另一个多边形是否在这个矩形框中存在顶点,没有就说明另一个矩形一定在参照矩形框的外围。
        第二步:利用的是向量叉乘求两线段是否相交,这种求法是求的绝对相交(交叉相交),只要存在多边形任意两线段相交,就一定相交,
        同时还有一种情况,就是平行或者在延长线及线段上,这时候需要排除平行和在延长线上的情况
        第三步:用点射法求某一个顶点是否在某个多边形内部,这里需要同时同时判断多变形1上的所有点都在多边形2的内部或者边线段上,
        或者是反向多边形2的所有点在多边形1的内部或边线上,二者满足其一即可;
        */
        public static void main(String[] args) {
            Point point = new Point(0, 0.5);
            Polygon polygon = new Polygon().setPoints(Arrays.asList(
                    new Point(0, 0),
                    new Point(0, 0.5),
                    new Point(0.5, 0.5),
                    new Point(0.5, 0)
            ));
            // 点是否在内部
            boolean b = pointInPolygon(point, getLineSegment(polygon));
            System.out.println(b);
    
            Polygon polygon1 = new Polygon().setPoints(Arrays.asList(
                    new Point(-1, -1),
                    new Point(-1, 1),
                    new Point(1, 1),
                    new Point(1, -1)
            ));
            // 两个多边形相交
            System.out.println(intersectionJudgment(polygon, polygon1));
        }
    
        /**
         * 多边形相交判断(有一个点相交也认为相交)
         *
         * @param polygon1 多边形1
         * @param polygon2 多边形2
         * @return boolean
         */
        public static boolean intersectionJudgment(Polygon polygon1, Polygon polygon2) {
            if (isExistNull(polygon1, polygon2)) {
                return false;
            }
            if (isExistNullOrEmpty(polygon1.getPoints(), polygon2.getPoints())) {
                return false;
            }
            // 1、快速判断,如果不想交,则返回不相交
            if (!fastExclude(polygon1, polygon2)) {
                return false;
            }
            // 获取多边形线段集合
            List<LineSegment> lineSegment1 = getLineSegment(polygon1);
            List<LineSegment> lineSegment2 = getLineSegment(polygon2);
            // 存在线段集合任意一方为空,则不想交
            if (isExistNullOrEmpty(lineSegment1, lineSegment2)) {
                return false;
            }
            // 2、向量叉乘判断多边形是否存在线段相交,存在相交则返回相交
            if (crossJudgment(lineSegment1, lineSegment2)) {
                return true;
            }
            // 3、包含关系判断,分别两次判断,判断polygon1是否在polygon2内部和polygon2是否在polygon1内部,满足其一即可
            boolean isInclude = includeRelation(polygon1, lineSegment2);
            if (isInclude) {
                return true;
            }
            return includeRelation(polygon2, lineSegment1);
        }
    
        /**
         * 1、快速判断多边形是否相交
         *
         * @param polygon1 多边形1
         * @param polygon2 多边形2
         * @return boolean
         */
        private static boolean fastExclude(Polygon polygon1, Polygon polygon2) {
            // 多边形1
            double polygon1MaxX = polygon1.getPoints().get(0).getX();
            double polygon1MinX = polygon1.getPoints().get(0).getX();
            double polygon1MaxY = polygon1.getPoints().get(0).getY();
            double polygon1MinY = polygon1.getPoints().get(0).getY();
            for (Point point : polygon1.getPoints()) {
                polygon1MaxX = Math.max(polygon1MaxX, point.getX());
                polygon1MinX = Math.min(polygon1MinX, point.getX());
                polygon1MaxY = Math.max(polygon1MaxY, point.getY());
                polygon1MinY = Math.min(polygon1MinY, point.getY());
            }
    
            // 多边形2
            double polygon2MaxX = polygon2.getPoints().get(0).getX();
            double polygon2MinX = polygon2.getPoints().get(0).getX();
            double polygon2MaxY = polygon2.getPoints().get(0).getY();
            double polygon2MinY = polygon2.getPoints().get(0).getY();
            for (Point point : polygon2.getPoints()) {
                polygon2MaxX = Math.max(polygon2MaxX, point.getX());
                polygon2MinX = Math.min(polygon2MinX, point.getX());
                polygon2MaxY = Math.max(polygon2MaxY, point.getY());
                polygon2MinY = Math.min(polygon2MinY, point.getY());
            }
    
            // 我这里是人为临界点的点-点,点-线也是属于相交,(如过你认为不是,加上等于条件,也就是最大和最小出现任意相等也是不想交)
            // 1、多边形1的最大x比多边形2最小x还小,说明多边形1在多边形2左边,不可能相交
            // 2、多边形1的最小x比多边形2最大x还大,说明多边形1在多边形2右边,不可能相交
            // 3、多边形1的最大y比多边形2最小y还小,说明多边形1在多边形2下边,不可能相交
            // 4、多边形1的最小y比多边形2最大y还小,说明多边形1在多边形2上边,不可能相交
            return !(polygon1MaxX < polygon2MinX)
                    && !(polygon1MinX > polygon2MaxX)
                    && !(polygon1MaxY < polygon2MinY)
                    && !(polygon1MinY > polygon2MaxY);
        }
    
        /**
         * 获取线段集合
         *
         * @param polygon 多边形
         * @return 线段集合
         */
        private static List<LineSegment> getLineSegment(Polygon polygon) {
            List<LineSegment> lineSegments = new ArrayList<>();
            List<Point> points = polygon.getPoints();
            // 依次链接,形成线段
            for (int i = 0; i < points.size() - 1; i++) {
                Point previousElement = points.get(i);
                Point lastElement = points.get(i + 1);
                lineSegments.add(new LineSegment(previousElement, lastElement));
            }
            // 最后一组线段(最后一个点和初始点形成最后一条线段,形成闭环)
            if (lineSegments.size() > 0) {
                Point previousElement = points.get(points.size() - 1);
                Point lastElement = points.get(0);
                lineSegments.add(new LineSegment(previousElement, lastElement));
            }
            return lineSegments;
        }
    
        /**
         * 2、线段集合之间是否存在相交关系
         *
         * @param lineSegments1 线段集合1(其中一个多边形的线段集合)
         * @param lineSegments2 线段集合2(另一个多边形的线段集合)
         * @return boolean
         */
        private static boolean crossJudgment(List<LineSegment> lineSegments1, List<LineSegment> lineSegments2) {
            for (LineSegment lineSegment1 : lineSegments1) {
                for (LineSegment lineSegment2 : lineSegments2) {
                    // 任意一组线段相交及多边形相交,返回相交
                    if (calculationLineSegmentCrossing(lineSegment1, lineSegment2)) {
                        return true;
                    }
                }
            }
            return false;
        }
    
        /**
         * 线段是否相交(向量叉乘判断)
         *
         * @param lineSegment1 线段1
         * @param lineSegment2 线段2
         * @return boolean
         */
        private static boolean calculationLineSegmentCrossing(LineSegment lineSegment1, LineSegment lineSegment2) {
            // 如果存在任意一点在对方线段上,则相交
            if (isPointOnline(lineSegment1, lineSegment2)) {
                return true;
            }
            // 当不存端点在线段上,则进行交叉相交判断
            // A点
            Point aPoint = lineSegment1.getPrePoint();
            // B点
            Point bPoint = lineSegment1.getLastPoint();
            // C点
            Point cPoint = lineSegment2.getPrePoint();
            // D点
            Point dPoint = lineSegment2.getLastPoint();
            // AB向量叉乘AC向量
            double bc = crossProduct(aPoint, bPoint, aPoint, cPoint);
            // AB向量叉乘AD向量
            double bd = crossProduct(aPoint, bPoint, aPoint, dPoint);
            // CD向量叉乘CA向量
            double da = crossProduct(cPoint, dPoint, cPoint, aPoint);
            // CD向量叉乘CB向量
            double db = crossProduct(cPoint, dPoint, cPoint, bPoint);
            return bc * bd < 0 && da * db < 0;
        }
    
        /**
         * 两线段是否存在点在对方线段上
         *
         * @param lineSegment1 线段1
         * @param lineSegment2 线段2
         * @return boolean
         */
        private static boolean isPointOnline(LineSegment lineSegment1, LineSegment lineSegment2) {
            return isExistTrue(new boolean[]{
                    isCollinearIntersection(lineSegment1.getPrePoint(), lineSegment2),
                    isCollinearIntersection(lineSegment1.getLastPoint(), lineSegment2),
                    isCollinearIntersection(lineSegment2.getPrePoint(), lineSegment1),
                    isCollinearIntersection(lineSegment2.getLastPoint(), lineSegment1)});
        }
    
        /**
         * 点是否在线段上
         *
         * @param point            点
         * @param lineSegmentStart 线段起始点
         * @param lineSegmentEnd   线段尾点
         * @return boolean
         */
        private static boolean isCollinearIntersection(Point point, Point lineSegmentStart, Point lineSegmentEnd) {
            // 排除在延长线上的情况
            if (point.getX() >= Math.min(lineSegmentStart.getX(), lineSegmentEnd.getX())
                    && point.getX() <= Math.max(lineSegmentStart.getX(), lineSegmentEnd.getX())
                    && point.getY() >= Math.min(lineSegmentStart.getY(), lineSegmentEnd.getY())
                    && point.getY() <= Math.max(lineSegmentStart.getY(), lineSegmentEnd.getY())) {
                // 任意两点之间形成的向量叉乘等于0,表示在线段上或延长线上(三点共线)
                return crossProduct(point, lineSegmentStart, point, lineSegmentEnd) == 0;
            }
            return false;
        }
    
        /**
         * 点是否在线段上
         *
         * @param point       点
         * @param lineSegment 线段
         * @return boolean
         */
        private static boolean isCollinearIntersection(Point point, LineSegment lineSegment) {
            return isCollinearIntersection(point, lineSegment.getPrePoint(), lineSegment.getLastPoint());
        }
    
        /**
         * 3、多边形polygon的所有点是都在另一个多边形内部(包含关系)
         *
         * @param polygon      被包含(内部)多边形
         * @param lineSegments 包含(外部)多边形所有线段集合
         * @return boolean
         */
        private static boolean includeRelation(Polygon polygon, List<LineSegment> lineSegments) {
            List<Point> points = polygon.getPoints();
            // 所有点在内部或者线段上才算包含,返回包含关系,只要一个不满足,则返回不包含关系
            for (Point point : points) {
                if (!pointInPolygon(point, lineSegments)) {
                    return false;
                }
            }
            return true;
        }
    
        /**
         * 判断某个点是否在多边形内部
         *
         * @param point        点
         * @param lineSegments 多边形线段集合
         * @return boolean
         */
        private static boolean pointInPolygon(Point point, List<LineSegment> lineSegments) {
            // 点坐标
            double x = point.getX();
            double y = point.getY();
            // 交点个数
            int intersectionNum = 0;
            // 判断射线与多边形的交点个数
            for (LineSegment seg : lineSegments) {
                // 如果点在多边形边线上,则算在多边形内部
                if (isCollinearIntersection(point, seg.getPrePoint(), seg.getLastPoint())) {
                    return true;
                }
                double maxY = Math.max(seg.getPrePoint().getY(), seg.getLastPoint().getY());
                double minY = Math.min(seg.getPrePoint().getY(), seg.getLastPoint().getY());
                if (y >= minY && y < maxY) {
                    // 计算交点X坐标
                    double intersectionPointX = (y - seg.getPrePoint().getY()) * (seg.getLastPoint().getX() - seg.getPrePoint().getX())
                            / (seg.getLastPoint().getY() - seg.getPrePoint().getY()) + seg.getPrePoint().getX();
                    if (x > intersectionPointX) {
                        intersectionNum++;
                    }
                }
            }
            return intersectionNum % 2 != 0;
        }
    
        /**
         * 向量叉乘
         *
         * @param point1Start 向量1起点
         * @param point1End   向量1尾点
         * @param point2Start 向量2起点
         * @param point2End   向量2尾点
         * @return 向量叉乘结果
         */
        private static double crossProduct(Point point1Start, Point point1End, Point point2Start, Point point2End) {
            // 向量a
            double aVectorX = point1End.getX() - point1Start.getX();
            double aVectorY = point1End.getY() - point1Start.getY();
            // 向量b
            double bVectorX = point2End.getX() - point2Start.getX();
            double bVectorY = point2End.getY() - point2Start.getY();
            // 向量a叉乘向量b
            return aVectorX * bVectorY - bVectorX * aVectorY;
        }
    
        /**
         * 是否存在空对象
         *
         * @param objects 对象集合
         * @return boolean
         */
        private static boolean isExistNull(Object... objects) {
            for (Object object : objects) {
                if (object == null) {
                    return true;
                }
            }
            return false;
        }
    
        /**
         * 是否存在空集合
         *
         * @param collections 集合对象
         * @return boolean
         */
        private static boolean isExistNullOrEmpty(Collection<?>... collections) {
            for (Collection<?> collection : collections) {
                if (collection == null || collection.isEmpty()) {
                    return true;
                }
            }
            return false;
        }
    
        /**
         * 是否存在true
         *
         * @param booleans 布尔集合
         * @return boolean
         */
        private static boolean isExistTrue(boolean[] booleans) {
            for (boolean bool : booleans) {
                if (bool) {
                    return true;
                }
            }
            return false;
        }
    
        /**
         * 点
         */
        @Data
        @AllArgsConstructor
        @NoArgsConstructor
        private static class Point {
            private double x;
            private double y;
        }
    
        /**
         * 线段
         */
        @Data
        @AllArgsConstructor
        @NoArgsConstructor
        private static class LineSegment {
            private Point prePoint;
            private Point lastPoint;
        }
    
        /**
         * 多边形
         */
        @Data
        @AllArgsConstructor
        @NoArgsConstructor
        @Accessors(chain = true)
        private static class Polygon {
            private List<Point> points;
        }
    }
    

     

    展开全文
  • 真的很讨厌,数学不是太好,但是几何还好,纵使是这样,该忘了的还是忘了...为了解决在百度API中缺少图形是否相交判断,所以必须,要判断两个图形边缘的点,这下问题就来了, 网上搜一大片,全是绘制View的,找了很

    真的很讨厌,数学不是太好,但是几何还好,纵使是这样,该忘了的还是忘了!满意以为随便搜搜都是一大堆,但是我真的想错了!

    看结果图:
    40条边数,获取每一个点的在实际地理中的坐标(经纬度)
    原点(center)是=32.02103 : 118.763435
    这里写图片描述
    这里写图片描述

    为了解决在百度API中缺少图形是否相交的判断,所以必须,要判断两个图形边缘的点,这下问题就来了,
    网上搜一大片,全是绘制View的,找了很久,算了自己算吧!!

    上代码:
    1.获取圆形上的多个点集合

    /**
    	 * 
    	 * @param lineNum需要获取的正多边形书也可以认为是点的个数
    	 * @param a需要的偏移量本项目中默认是50
    	 * @param ll地理坐标的中心店
    	 * @return实际地理范围的坐标店集合
    	 */
    public static ArrayList<LatLng> logPoint(int lineNum, double a, LatLng ll) {
    	ArrayList<LatLng> lls = new ArrayList<LatLng>();
    	float angle = 360 / lineNum;
    		// 已知多边形的半径为50
    	double b, c;// 边长,a是圆半径固定是50,b是高(Y轴),C是长(X轴)
    	float A = 90, B, C;// 角度,设定B是向量-变化
    	for (int i = 0; i < lineNum; i++) {
    		float angleCenter = angle * i;
    		Log.i("zjs","当前角度   = "+angleCenter);
    			
    			if(angleCenter <=180){
    				B = angleCenter;
    				C = 90 - B;
    				b=a * Math.sin(Math.toRadians(B));
    				c = a * Math.sin(Math.toRadians(C));		
    			}else{
    				B = angleCenter-360;
    				C = 90 - B;
    				b=a * Math.sin(Math.toRadians(B));
    				c = a * Math.sin(Math.toRadians(C));
    			}
    			// 1.同一纬线上经度差一度,实际距离差多少
    			// 111km*cosφ (φ为当地纬度)
    			// 2.同一经线上纬度差一度,实际距离差多少
    			// 111km
    //			Log.d("zjs","b= "+b+"  :  c="+c);
    			b = b / (111000*Math.cos(ll.longitude)) + ll.longitude;
    			c = c / 111000 + ll.latitude;
    		Log.d("zjs","以地理坐标点为中心——第"+(i+1)+"个坐标点的位置是      =   "+b+"  :  "+c);
    			lls.add(new LatLng(c, b));
    
    		}
    
    		return lls;
    	}
    

    2.通过百度API判断是否相交

    // TODO 获取正多边形(40边)的角点,(后面可以加入方位角,根据需求减少判断的方向)
    	ArrayList<LatLng> lls = logPoint(40, minlen, gps);
    		boolean inDistance = false;
    		 for (int i = 0; i < lls.size(); i++) {
    if (SpatialRelationUtil.isPolygonContainsPoint(list,
    				lls.get(i))) {
    						inDistance=true;
    						break;
    					}
    				}
    

    铛铛铛:(需要注意的坑)
    1.Java的Math.sin等调用的参数是弧度,我一度直接调用,到时结果莫名其妙,所以一定要转换成角度,不会再被坑了,
    2.实际地理地图中的坐标和长度之间的转换,//能复制就复制,别敲错了
    3.在角度和方向的问题,判断减少了,以180度为中心对半开。前面写的绕了

    然后就可以妥妥来实现,google,高德都有的(图形相交的状态)功能了,
    加油了,继续努力!!

    谢谢你您的回复,根据您的回复我单独在底图上绘制出来
    在这里插入图片描述我也想明白你们为什么会是椭圆的,或者说椭圆都不算,是向个鸡蛋一样。
    真的对此我还是不太了解…

    展开全文
  • 概念:通过判断任意两个凸多边形在任意角度下的投影是否均存在重叠,来判断是否发生碰撞。若在某一角度光源下,两物体的投影存在间隙,则为不碰撞,否则为发生碰撞。 图例: 在程序中,遍历所有角度是不现实的。...

    参考原文:原文

    预备知识:向量的点积: 

     

    关于向量的知识这里不再赘述 

    分离轴定理(Separating Axis Theorem)

    概念:通过判断任意两个 凸多边形 在任意角度下的投影是否均存在重叠,来判断是否发生碰撞。若在某一角度光源下,两物体的投影存在间隙,则为不碰撞,否则为发生碰撞。

    图例:

    在程序中,遍历所有角度是不现实的。那如何确定 投影轴 呢?其实投影轴的数量与多边形的边数相等即可。

     

    上述代码有几个需要解决的地方:

    • 如何确定多边形的各个投影轴
    • 如何将多边形投射到某条投影轴上
    • 如何检测两段投影是否发生重叠

    投影轴

    如下图所示,我们使用一条从 p1 指向 p2 的向量来表示多边形的某条边,我们称之为边缘向量。在分离轴定理中,还需要确定一条垂直于边缘向量的法向量,我们称之为“边缘法向量”。

    投影轴平行于边缘法向量。投影轴的位置不限,因为其长度是无限的,故而多边形在该轴上的投影是一样的。该轴的方向才是关键的。

     

    投影

    投影的大小:通过将一个多边形上的每个顶点与原点(0,0)组成的向量,投影在某一投影轴上,然后保留该多边形在该投影轴上所有投影中的最大值和最小值,这样即可表示一个多边形在某投影轴上的投影了。

    判断两多边形的投影是否重合:projection1.max > projection2.min && project2.max > projection.min

     

     碰撞工具类:

    interface IPoint {
        x: number;
        y: number;
    }
    
    class CollisionUitls {
    
        /**
         * 返回矩形的顶点坐标位置 相对于当前父节点的坐标点。
         * @param shap 
         */
        public static getRectangleVerPoints(shap: egret.DisplayObject): IPoint[] {
            const anX = shap.anchorOffsetX;
            const anY = shap.anchorOffsetY;
    
            const mat2x3 = shap.matrix;
            const a = mat2x3.a;
            const b = mat2x3.b;
            const c = mat2x3.c;
            const d = mat2x3.d;
            const tx = mat2x3.tx;
            const ty = mat2x3.ty;
            const w = shap.width;
            const h = shap.height;
    
    
            const p1x = - anX
            const p1y = -anY
    
            const p2x = w - anX;
            const p2y = -anY;
    
            const p3x = w - anX;
            const p3y = (h - anY);
    
            const p4x = -anX;
            const p4y = (h - anY);
    
    
            // a: 缩放或者旋转图像是影响沿x轴定位的值
            // b: 旋转或者倾斜影响y轴定位的值
            // 对x坐标有影响的值为a 和 c的值
            // 对y坐标有影响的值为b 和 d的值
            const p1 = { x: tx + a * p1x + c * p1y, y: ty + b * p1x + d * p1y };
            const p2 = { x: tx + a * p2x + c * p2y, y: ty + b * p2x + d * p2y };
            const p3 = { x: tx + a * p3x + c * p3y, y: ty + b * p3x + d * p3y };
            const p4 = { x: tx + a * p4x + c * p4y, y: ty + b * p4x + d * p4y };
    
            return [p1, p2, p3, p4];
        }
    
        /**
         * 检测圆和多边形
         * @param obj1 
         * @param obj2 
         */
        public static TestCircleAndPolygon(CircleX: number, CircleY: number,r:number, PolygonVertexPoints: IPoint[]): boolean {
            for (let i: number = 0; i < PolygonVertexPoints.length; i++) {
                let startPoint = PolygonVertexPoints[i];
                let endPoint;
                let sideNorVec;
    
                if (i != PolygonVertexPoints.length - 1) {
                    endPoint = PolygonVertexPoints[i + 1];
                } else {
                    //最后一个
                    endPoint = PolygonVertexPoints[0];
                }
                sideNorVec = CollisionUitls.get2PointVec(startPoint, endPoint, false);
    
                //这个边的法相量方向(标准化过的)
                let dotNorVec = CollisionUitls.getSideNorml(sideNorVec, false);
                const data1 = CollisionUitls.calcProj(dotNorVec, PolygonVertexPoints);
                const dot = CollisionUitls.dot([CircleX, CircleY], CollisionUitls.normalize(dotNorVec));
    
                const value = CollisionUitls.segDist(data1.min, data1.max, dot-r, dot+r);
                if (!value) {
                    return false;
                }
            }
            return true;
        }
    
    
        /**
         * 检测两个矩形是否相交 
         * @param r1PointList 矩形顶点数组
         * @param r2PointList 
         */
        public static checkPolygon(r1PointList: IPoint[], r2PointList: IPoint[]): boolean {
            
            var fun1 = function (pointlist: IPoint[], vertexPoints1: IPoint[], vertexPoints2: IPoint[]): boolean {
                //先计算 r1的边 ---》 顺时针
                for (let i: number = 0; i < pointlist.length; i++) {
                    let startPoint = pointlist[i];
                    let endPoint;
                    let sideNorVec;
    
                    if (i != pointlist.length - 1) {
                        endPoint = pointlist[i + 1];
                    } else {
                        //最后一个
    
    
                        endPoint = pointlist[0];
                    }
                    sideNorVec = CollisionUitls.get2PointVec(startPoint, endPoint, false);
    
                    //这个边的法相量方向(标准化过的)
                    let dotNorVec = CollisionUitls.getSideNorml(sideNorVec, false);
                    const data1 = CollisionUitls.calcProj(dotNorVec, vertexPoints1);
                    const data2 = CollisionUitls.calcProj(dotNorVec, vertexPoints2);
                    const value = CollisionUitls.segDist(data1.min, data1.max, data2.min, data2.max);
                    if (!value) {
                        return false;
                    }
    
                }
                return true;
            }
    
            if (!fun1(r1PointList, r1PointList, r2PointList)) {
                return false;
            }
    
            if (!fun1(r2PointList, r1PointList, r2PointList)) {
                return false;
            }
            return true;
    
    
        }
    
        /**
         * 计算某个图形坐标点到当前轴上的投影最小点
         * @param axis 
         * @param objPoints 
         */
        public static calcProj(axis: number[], objPoints: IPoint[]): { min: number, max: number } {
    
            let min = 0;
            let max = 0;
            for (let i: number = 0; i < objPoints.length; i++) {
                const vec2 = [objPoints[i].x, objPoints[i].y];
    
    
                const dot = CollisionUitls.dot(vec2, CollisionUitls.normalize(axis));
    
                //const dot = CollisionUitls.dot(vec2,axis);
    
                if (min == 0 || max == 0) {
                    min = max = dot;
                } else {
                    min = (dot < min) ? dot : min;
                    max = (dot > max) ? dot : max;
                }
    
            }
    
            return { min: min, max: max }
        }
    
    
    
        /**
         * 计算同一个轴上线段的距离s1(min1,max1),s2(min2,max2),如果距离小于0则表示两线段有相交;
         * @param min1 
         * @param max1 
         * @param min2 
         * @param max2 
         * @returns true: 相交 false: 不相交
         */
        public static segDist(min1: number, max1: number, min2: number, max2: number): boolean {
            if (min1 < min2) {
                return min2 < max1 && max2 > min1;
            }
            else {
                return min1 < max2 && max1 > min2;
            }
        }
    
        /**
         * 计算两点向量方向
         * @param p1 
         * @param p2 
         */
        public static get2PointVec(p1: IPoint, p2: IPoint, isNormlize = true): number[] {
    
    
            const x = p2.x - p1.x;
            const y = p2.y - p1.y;
    
    
    
            if (isNormlize) {
                return CollisionUitls.normalize([x, y]);
            }
            return [x, y];
        }
    
    
        /**
         * 根据当前多边形边长获取对应边长的 法线向量
         * @param vec2 
         */
        public static getSideNorml(vec2: number[], isNormlize = true): number[] {
    
            const x = vec2[0];
            const y = vec2[1];
    
            //顺时针方向的法相量 
            //normal=(-y,x) || normal=(y,-x)
            if (isNormlize) {
                CollisionUitls.normalize([-y, x])
            }
            return [-y, x];
        }
    
        public static normalize(vec2: number[]): number[] {
            if (vec2.length != 2) {
                console.error("只能标准化2d向量")
                return vec2;
            }
            const x = vec2[0];
            const y = vec2[1];
            const model = Math.sqrt(x * x + y * y);
    
    
            return [x / model, y / model];
        }
        /**
         * 计算两个向量的点积
         * @param vec2A 
         * @param vec2B 
         */
        public static dot(vec2A: number[], vec2B: number[]): number {
            if (vec2A.length != 2 || vec2B.length != 2) {
                console.error("只能计算2d向量的点积")
                return null;
            }
    
            return vec2A[0] * vec2B[0] + vec2A[1] * vec2B[1];
        }
    }

    源码地址:git@github.com:lck898989/egret2d_collisionDEMO.git

     

    展开全文
  • java判断图形相交,并获得相交区域

    千次阅读 2019-07-27 08:22:44
    客户提出的需求:比如地图上有2个图形,图形任意,需要判断出图形的交点区域的图形。...5.多边形 6. 7.折线 这样的判断其实有一定的难度性,需要判断客户点击的图形是怎样的,根据不同的图形来判断。而且判...
  • 2017-01-02 回答多边形内角的简易算法 引言 本文所论述的观点是我在写作业过程中偶然发现的一个规律,老师在课堂中从未涉及,碰到类似的题目时一般来讲也是就题论题,并没有一个普遍应用的公式,希望通过这篇文章...
  • (1)定义一个Point类,其属性包括点的坐标,提供计算两点之间距离的方法; (2)定义一个圆形类,其属性包括圆心半径;...(3)创建两个圆形对象,提示用户输入圆心坐标半径,判断两个圆是否相交,并输出结果。
  • 使用gdal计算点与圆相交的条件:   注意:以下方法以WKT格式为准。 1.圆形在GDAL中无法直接通过两个点位信息以及半径描述出来,需要自己通过构建圆形的方式才能拼凑出符合GDAL的图形描述,其中参数graph为图形...
  • 碰撞检测:判断2个多边形相交

    千次阅读 2019-03-02 14:41:09
    演示demo: 需要判断2个条件 边相交。2个多边形的边是否相交。 点在内部。2个多边形的顶点是否在另一个多边形的内部。 关于这2个条件的判断: 《碰撞检测:判断是否多边形内部》 ...
  • //判断多边形边界是否相交 function isPolygonsIntersectant($plyA, $plyB) {//面面 for ($i = 0, $il = count( $plyA ); $i < $il; $i++) { for ($j = 0, $jl = count( $plyB ); $j < $jl; $j++)...
  • 今天突然遇到要判断圆形与矩形相交的问题!在网上搜索了一下,看看有没有好的方法!发现讨论这个的比较少,以前有一个帖子倒是讨论过,但是帖子上好像没讨论出什么东西,最后就不了了之了!后来想了一下,我用下面的...
  • 因为任意简单多边形都可以划分成若干三角形,我们可以把这个简单多边形划分成三角形后,求三角形与的面积交,然后在把所有三角形的解合并。 计算一个与一个三角形的面积交(其中一个三角形...
  • 简单多边形圆相交求面积

    千次阅读 2019-12-24 16:32:40
    简单多边形圆相交求面积简单多边形的有向面积简单多边形圆相交的有向面积圆心三角形与圆相交求面积 简单多边形的有向面积 所谓简单多边形,就是指不相邻的边不相交,且每个顶点只跟2条边相邻。一般而言,除非...
  • 题目:用最简单,最快速的方法计算出下面这个圆形是否和正方形相交。 3D 坐标系原点(0.0,0.0,0.0) 圆形: 半径r = 3.0 圆心o = (*.*, 0.0, *.*) 正方形: 4 个角坐标; 1:(*.*, 0.0, *.*) 2:(*.*, 0.0, *.*) 3...
  • 前言 图形相交检测常常用在伤害判定,使用自定义的图形相交... 4、圆形与凸多边形  5、圆形与AABB  6、圆形与OBB 通过简单化处理,把被判定物都处理成由圆柱或多个圆柱构成的区域,所以只需要考虑圆形与其他形状的
  • 图形相交检测常常用在伤害判定,使用自定义的图形相交检测,可以在一定程度上控制性能。 比如2D格斗游戏中使用的矩形包围盒(AABB),一些动作游戏中常常出现的扇形攻击。 2D的图形相交检测能够满足大部分的需求,...
  • 圆和矩形的重叠问题一.问题描述二.分析思路三.代码示例(JQuery) 一.问题描述 给你一个以 (radius, x_center, y_center) 表示的圆和一个与坐标轴平行的矩形 (x1, y1, x2, y2),其中 (x1, y1) 是矩形左下角的坐标,(x2...
  • 总结图形学方法处理多边形相交问题
  • 多边形和圆分开写,首先简单的就是判断是否里面,如何判断一个坐标是否在圆形区域内,相信不用我说都知道,计算这个坐标点圆心之间的距离,然后跟的半径进行比较,如果比半径大,就不在圆形区域内,如果小于...
  • 【Unity】图形相交检测

    千次阅读 2018-05-22 18:19:49
    本文会实现几个圆形与其他2D图形的相交检测: 1、圆形与圆形 2、圆形与胶囊体 3、圆形与扇形 4、圆形与凸多边形 5、圆形与AABB 6、圆形与OBB
  • 前几天面试的时候被问到了,如何随机在三角形内生成点,我...判断一个点是否多边形内首先先说一下输入的内容,多边形的顶点是一个数组输入进来,其中每个相邻点之间对应着多边形上有边相连POINT p1=ptPolygon[i];...
  • line2 = wkt.loads("LINESTRING (116.23761690616871 40.17092015348095, 116.23760690616871 40.17092015348095)") # 判断线线是否相交 print(line1.intersects(line2)) # 增加0.3米的buffer, 这里0.3/100000后的...
  • C++ 判断是否多边形内部的方法

    千次阅读 多人点赞 2018-11-29 14:26:59
    在网上看到了很多种方法来判断“点是否多边形内部”,最终选择了一种简单易懂,且适合所有多边形的方法--水平/垂直交叉点数判别法。 方法 如果从点P作水平向左的射线的话,假设P在多边形内部,那么这条射线与...
  • 最近在做一些简单的图像对比工作,总结了一些GDI+...判断Rectangl与多边形的关系 /// <summary> /// 是否包含输入范围 /// </summary> /// <param name="rectangle">要对比的范围<...
  • 判断点与多边形关系

    2019-09-21 23:41:57
    面积法:从多边形一顶点出发,计算被判断的点相邻两点组成的三角形的面积(可用 1/2 * 向量叉乘求),面积多边形面积相等则在多边形内 夹角法:从多边形一顶点出发,计算被判断的点和多边形相邻两顶点的...
  • 1.判断某坐标 位置是否多边形区域内 /** * 判断当前位置是否多边形区域内 * @param orderLocation 当前点 * @param partitionLocation 区域顶点 * @return */ public static boolean isInPolygon(String X,...
  • jsapi里有如何判断是否多边形内的例子,但是这个项目根据实际需要,需要在后台来判断,点是否多边形中,但是在百度地图web服务api中没有相关的方法,只有百度其他的了:主要看来数学要不错才行啊。亲测可用。...
  • @TOCC# 判断是否多边形的内部-射线法判断是否有交点的分析 最近在做关于点在多边形内部的判断,有很多大佬都讲过使用射线法,但是涉及到细节地方没有详细的分析,本文只针对分析是否穿过其中一条边的情况。 关于...
  • 题意:给出一个多边形和一个,问是否是凸多边形,若是则再问圆是否在凸多边形内部。分3步:1、判断是否是凸多边形2、判断是否多边形内部3、判断点到各边的距离是否大于等于半径上代码:#include #include #...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,297
精华内容 1,718
关键字:

判断圆和多边形是否相交