精华内容
下载资源
问答
  • chopper:目录​zhuanlan.zhihu.com本...文章目录:算法介绍源码实现参考算法介绍在三维空间上,判断线性对象与三角形是否相交,若相交,求出交点,三角形所在的平面是。 图1. 直线与三角形的四种关系三维空间的模型...

    c5f74be5d8e13f5474b67af1d359c69f.png
    chopper:目录zhuanlan.zhihu.com
    ea0770e4a986d1245c13df72f0e8be4d.png

    本篇文章介绍一种三维空间下线性对象与三角形的相交测试算法和实现,线性对象包括:直接、射线和线段,它们可以用类似的形式来表示,先以直接为例来阐述算法,射线和线段是直接的特殊情况。

    文章目录:

    • 算法介绍
    • 源码实现
    • 参考

    算法介绍

    在三维空间上,判断线性对象

    与三角形
    是否相交,若相交,求出交点,三角形所在的平面是

    0fbad02cdef2192245db69bf0ec34638.png
    图1. 直线与三角形的四种关系

    三维空间的模型通常是由一个个三角形面片构成的,线性对象与三角形的相交检测也显得特别的重要。如图1所示,一条直线与三角形可能有四种关系:1)直线

    与三角形相交;2)直线
    与三角形所在的平面相交,但与三角形不相交;3)直线
    与在三角形所在的平面上;4)直线
    与三角形所在的平面平行。 一种朴素的检测算法是计算线性对象与三角形所在的平面的交点,再判断交点是否在三角形内。如果交点在三角形内,则线性对象与三角形相交;否则,不相交。这种算法效率不仅效率较低,而且更容易造成浮点数误差。因为计算机中的浮点数占用字节有限,能表示的精度有限,有效数较少,求直线与平面的交点,由于对同一个变量多次的乘法或者除法操作,造成误差的叠加,最后计算出来的结果由于精度问题,可能造成较大的误差。例如,三角形顶点的坐标数值较大,计算的直线与平面的交点,会由于精度误差导致求出的交点偏离平面,即可以检测到交点不在平面上。

    Möller&Trumbore(1997)[1]提出了一种更加高效的射线与三角形相交测试的算法,而且乘法或者除法操作造成的误差叠加较少,精度损失更小,因此性能上更加健壮。

    三角形内的任意一点都可以用它相对于三角形的顶点的位置来定义:

    其中,

    ,称为重心坐标(barycentric coordinate)。直线可以用参数方程表示为
    ,因此计算直线与三角的交点的等式为

    整理,得

    这相当于是一个齐次线性方程组,

    是它的解,可以采用克拉姆法则来求解,得到

    其中,

    ,依据线性代数的知识,易知
    ,因此等式(4)可以写成:

    如果得到的解

    ,那么直线与平面的交点位于三角形内;否则,位于三角形外。注意,若
    ,则交点在三角形的边上。

    直线与三角形相交测试的算法伪码如下所示:

    在三维空间上,判断直线
    与三角形
    是否相交,若相交,求出交点,三角形所在的平面是

    14fdbe9b91b5f6b03d8183ee7ecacfce.png

    如果需要求射线与三角形的交,必需限定

    的取值范围,
    必需满足条件
    ,若计算出来的
    ,则射线与三角形不相交。同样,如果需要求线段与三角形的交,线段的参数方程仍然可以表示为
    ,线段的两个端点分别是
    ,则
    必需满足条件
    ,因此,若计算出来的
    ,则线段与三角形不相交。

    注意到,在上述的算法伪码中,已经把一些中间变量存储起来,避免重复计算,可以提高算法的速度,例如中间变量

    源码实现

    基础库源码链接,参见这里,下面是前面所描述的算法的实现。

    #include "SrGeometricTools.h"
    #include "SrDataType.h"
    
    namespace {
        class SrSegment3D
        {
        public:
            SrPoint3D mPoint1;
            SrPoint3D mPoint2;
        };
    
        class SrRay3D
        {
        public:
            SrPoint3D   mBase;
            SrPoint3D   mDirection;
        };
    
        class SrLine3D
        {
        public:
            SrPoint3D mBase;
            SrPoint3D mDirection;
        };
    
        /**
        brief 3D triangle class.
        This is a 3D triangle class with public data members.
        */
    
        class SrTriangle3D
        {
        public:
            /**
            brief Default constructor, endpoints is set to (0,0).
            */
            SrTriangle3D()
            {
                mPoint[0] = mPoint[1] = mPoint[1] = SrVector3D(0, 0, 0);
            }
            /**
            brief The line is initialized by three points.
            */
            SrTriangle3D(const SrPoint3D& p0, const SrPoint3D& p1, const SrPoint3D& p2)
            {
                mPoint[0] = p0;
                mPoint[1] = p1;
                mPoint[2] = p2;
            }
            /**
            brief Destructor. Do nothing.
            */
            ~SrTriangle3D() {}
            /**
            brief The triangle is valid if the three points are not on a line.
            */
            bool    isValid() const
            {
                SrVector3D norm = normal();
                if (EQUAL(norm.x, 0) && EQUAL(norm.y, 0) && EQUAL(norm.z, 0))
                    return false;
                return true;
            }
            /**
            brief  Compute the normal using Newell method devised by Martin Newell.It relates to the order of the points.
            */
            const SrVector3D normal()const
            {
                SrVector3D norm = (mPoint[1] - mPoint[0]).cross(mPoint[2] - mPoint[0]);
                return norm;
            }
            /**
            brief  Judge whether or not the line hits the triangle.
            return SR_OVERLAPPING      if the line is on the plane where the triangle lies;
                    SR_PARALLEL         if the line is parallel to the triangle.
                    SR_DISJOINT         if the line misses the triangle;
                    SR_INTERSECTING     if the line intersects with the triangle and intersection point is not on the edge.
            param[out] result If the line intersects with the triangle and the intersection point information is put in 'result'.
            */
            int lineHitTest(const SrLine3D& line, SrPoint3D& /*[OUT]*/ result)const
            {
                SrVector3D ret;
                int retFlag = linearIntersectTriangle(line.mBase, line.mDirection, ret);
                if (retFlag != SR_INTERSECTING)
                    return retFlag;
                result = line.mBase + ret.z*line.mDirection;
                //check whether the intersection point is on the edge.
                //if( EQUAL(ret.x+ret.y-1.0,0) || 
                //  EQUAL(ret.x,0) || 
                //  EQUAL(ret.y,0) )
                //  return SR_INTERSECTING_EDGE;
                return SR_INTERSECTING;
            }
    
            /**
            brief  Judge whether or not the ray hits the triangle.
            return SR_OVERLAPPING      if the ray is on the plane where the triangle lies;
                    SR_PARALLEL         if the ray is parallel to the triangle.
                    SR_DISJOINT         if the ray misses the triangle;
                    SR_INTERSECTING     if the ray intersects with the triangle and intersection point is not on the edge.
            param[out] result If the ray intersects with the triangle and the intersection point information is put in 'result'.
            */
            int rayHitTest(const SrRay3D& ray, SrPoint3D& /*[OUT]*/ result)const
            {
                SrVector3D ret;
                int retFlag = linearIntersectTriangle(ray.mBase, ray.mDirection, ret);
                if (retFlag != SR_INTERSECTING)
                    return retFlag;
                //check t. t>=0
                if (LESS(ret.z, 0))
                    return SR_DISJOINT;
                result = ray.mBase + ret.z*ray.mDirection;
                //check whether the intersection point is on the edge.
                //if( EQUAL(ret.x+ret.y-1.0,0) || 
                //  EQUAL(ret.x,0) || 
                //  EQUAL(ret.y,0) )
                //  return SR_INTERSECTING_EDGE;
    
                return SR_INTERSECTING;
            }
            /**
            brief  Judge whether or not the segment hits the triangle.
            return SR_OVERLAPPING       if the segment is on the plane where the triangle lies;
                    SR_PARALLEL          if the segment is parallel to the triangle.
                    SR_DISJOINT          if the segment misses the triangle;
                    SR_INTERSECTING      if the segment intersects with the triangle and intersection point is not on the edge.
            param[out] result If the segment intersects with the triangle and the intersection point information is put in 'result'.
            */
            int segmentHitTest(const SrSegment3D& segment, SrPoint3D& /*[OUT]*/ result)const
            {
                SrVector3D ret;
                SrVector3D direction = segment.mPoint2 - segment.mPoint1;
                int retFlag = linearIntersectTriangle(segment.mPoint1, direction, ret);
                if (retFlag != SR_INTERSECTING)
                    return retFlag;
                //check t. 0<= t <=1
                if (LESS(ret.z, 0) || GREATER(ret.z, 1))
                    return SR_DISJOINT;
                result = segment.mPoint1 + ret.z*direction;
                //check whether the intersection point is on the edge.
                //if( EQUAL(ret.x+ret.y-1.0,0) || 
                //  EQUAL(ret.x,0) || 
                //  EQUAL(ret.y,0) )
                //  return SR_INTERSECTING_EDGE;
                return SR_INTERSECTING;
            }
    
        public:
            SrPoint3D   mPoint[3];
    
        private:
            /**
            brief  Judge whether or not the line hits the triangle.The line is base + t*direction.
                    It is not necessary for direction to be unit length.
            return SR_OVERLAPPING       if the line is on the plane where the triangle lies;
                    SR_PARALLEL          if the line is parallel to the triangle.
                    SR_DISJOINT          if the line misses the triangle;
                    SR_INTERSECTING      if the line intersects with the triangle.
            param[out] result return the result of (u,v,t) if the line intersects with the triangle.
            */
            /*
            --------------------------------------------------------------------------
            Devised by Moller and Trumbore,1997. <Fast,minimum storage ray-triangle
            intersection>
            Any point in a triangle can be defined in terms of its position relative
            to the triangle’s vertices:
                    Qu,v = (1-u-v)V0 + uV1 + vV2 ,0<=u<=1,0<=v<=1,0<=u+v<=1
            For the linear component–triangle intersection,
                    P + t*^d = Qu,v
            which can be expanded and applied Cramer’s rule to:
                    |t|                         | |P-V0  V1-V0  V2-V0| |
                    |u| = 1/|-^d  V1-V0  V2-V0| | |-^d   P-V0   V2-V0| |
                    |v|                         | |-^d   V1-V0   P-V0| |
    
    
                                                    | ((P-V0)×(V1-V0))·(V2-V0) |
                        = 1/(^d×(V2-v0))·(V1-V0)    |    (^d×(V2-V0))·(P-V0)   |
                                                    |    ((P-V0)×(V1-V0))·^d     |
            --------------------------------------------------------------------------
            */
            int linearIntersectTriangle(const SrPoint3D& base, const SrVector3D& direction, SrVector3D& result)const
            {
                SrReal u, v, tmp;
                SrVector3D e1, e2, p, s, q;
                e1 = mPoint[1] - mPoint[0];
                e2 = mPoint[2] - mPoint[0];
                p = direction.cross(e2);
                tmp = p.dot(e1);
                //If the line is perpendicular to the normal of triangle.
                if (EQUAL(tmp, 0))
                {
                    //The line is on the plane.
                    p = e1.cross(e2);
                    if (EQUAL(p.dot(base - mPoint[0]), 0))
                        return SR_OVERLAPPING;
                    //The line is parallel to the plane.
                    return SR_PARALLEL;
                }
                s = base - mPoint[0];
                u = p.dot(s) / tmp;
                if (LESS(u, 0) || GREATER(u, 1))
                    return SR_DISJOINT;
                q = s.cross(e1);
                v = q.dot(direction) / tmp;
                if (LESS(v, 0) || GREATER(v, 1) || GREATER(u + v, 1))
                    return SR_DISJOINT;
    
                result.x = u;
                result.y = v;
                result.z = e2.dot(q) / tmp;
                return SR_INTERSECTING;
            }
        };
    }
    

    参考

    [1] Tomas Möller, and Ben Trumbore. "Fast, minimum storage ray-triangle intersection." Journal of graphics tools, vol.2, no.1, pp.21-28, 1997.

    [2] Philip J. Schneider, and David H. Eberly. Geometric Tools for Computer Graphics. Morgan Kaufmann, 2002.

    展开全文
  • 判断两条边相交,先用俩矩形快速排斥,再用跨立实验,如果ab和cd相交,那么cd的两端一定在向量ab的两侧,可以通过abc和abd叉积相乘判断是否相交 然后就是存多边形,这里正方形和矩形另外的点得通过向量计算一下 ...

    描述

    While creating a customer logo, ACM uses graphical utilities to draw a picture that can later be cut into special fluorescent materials. To ensure proper processing, the shapes in the picture cannot intersect. However, some logos contain such intersecting shapes. It is necessary to detect them and decide how to change the picture.

    Given a set of geometric shapes, you are to determine all of their intersections. Only outlines are considered, if a shape is completely inside another one, it is not counted as an intersection.

     

    输入

    Input contains several pictures. Each picture describes at most 26 shapes, each specified on a separate line. The line begins with an uppercase letter that uniquely identifies the shape inside the corresponding picture. Then there is a kind of the shape and two or more points, everything separated by at least one space. Possible shape kinds are:

    • square: Followed by two distinct points giving the opposite corners of the square.
    • rectangle: Three points are given, there will always be a right angle between the lines connecting the first point with the second and the second with the third.
    • line: Specifies a line segment, two distinct end points are given.
    • triangle: Three points are given, they are guaranteed not to be co-linear.
    • polygon: Followed by an integer number N (3 ≤ N ≤ 20) and N points specifying vertices of the polygon in either clockwise or anti-clockwise order. The polygon will never intersect itself and its sides will have non-zero length.

    All points are always given as two integer coordinates X and Y separated with a comma and enclosed in parentheses. You may assume that |X|, |Y | ≤ 10000.

    The picture description is terminated by a line containing a single dash (“-”). After the last picture, there is a line with one dot (“.”).

    输出

    For each picture, output one line for each of the shapes, sorted alphabetically by its identifier (X). The line must be one of the following:

    • “X has no intersections”, if X does not intersect with any other shapes.
    • “X intersects with A”, if X intersects with exactly 1 other shape.
    • “X intersects with A and B”, if X intersects with exactly 2 other shapes.
    • “X intersects with A, B, . . ., and Z”, if X intersects with more than 2 other shapes.

    Please note that there is an additional comma for more than two intersections. A, B, etc. are all intersecting shapes, sorted alphabetically.

    Print one empty line after each picture, including the last one.

    样例输入

    A square (1,2) (3,2)
    F line (1,3) (4,4)
    W triangle (3,5) (5,5) (4,3)
    X triangle (7,2) (7,4) (5,3)
    S polygon 6 (9,3) (10,3) (10,4) (8,4) (8,1) (10,2)
    B rectangle (3,3) (7,5) (8,3)
    -
    B square (1,1) (2,2)
    A square (3,3) (4,4)
    -
    .

    样例输出

    A has no intersections
    B intersects with S, W, and X
    F intersects with W
    S intersects with B
    W intersects with B and F
    X intersects with B

    A has no intersections
    B has no intersections

    题意

    给你多边形,如果在内部则视为不相交,判断哪些是相交的

    题解

    把多边形按边存,如果两个多边形相交,那么一定存在两条边相交

    判断两条边相交,先用俩矩形快速排斥,再用跨立实验,如果ab和cd相交,那么cd的两端一定在向量ab的两侧,可以通过abc和abd叉积相乘<0判断是否相交

    然后就是存多边形,这里正方形和矩形另外的点得通过向量计算一下

    PS:码农题,读输入,输出都恶心,题目不算太难

    代码

      1 #include<cstdio>
      2 #include<algorithm>
      3 #include<vector>
      4 #include<set>
      5 using namespace std;
      6 struct point
      7 {
      8     double x,y;
      9     point(double x=0,double y=0):x(x),y(y){}
     10 };
     11 bool judge(point a,point b,point c,point d)
     12 {
     13     if(!(min(a.x,b.x)<=max(c.x,d.x)&&min(c.y,d.y)<=max(a.y,b.y)&&min(c.x,d.x)<=max(a.x,b.x)&&min(a.y,b.y)<=max(c.y,d.y)))
     14         return false;
     15     double u,v,w,z;
     16     u=(c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);
     17     v=(d.x-a.x)*(b.y-a.y)-(b.x-a.x)*(d.y-a.y);
     18     w=(a.x-c.x)*(d.y-c.y)-(d.x-c.x)*(a.y-c.y);
     19     z=(b.x-c.x)*(d.y-c.y)-(d.x-c.x)*(b.y-c.y);
     20     return (u*v<=0.00000001&&w*z<=0.00000001);
     21 }
     22 vector<point>G[27];
     23 
     24 int main()
     25 {
     26     //freopen("A.txt","w",stdout);
     27     int m;
     28     double a,b;
     29     char op[3],shape[20];
     30     while(scanf("%s",op)!=EOF,op[0]!='.')
     31     {
     32         for(int i=0;i<26;i++)G[i].clear();
     33         while(op[0]!='-')
     34         {
     35             int cnt=op[0]-'A';
     36             scanf("%s",shape);
     37             if(shape[0]=='s')///正方形
     38             {
     39                 for(int i=1;i<=2;i++)
     40                 {
     41                     scanf(" (%lf,%lf)",&a,&b);
     42                     G[cnt].push_back(point(a,b));
     43                 }
     44                 double A=G[cnt][0].x,B=G[cnt][0].y,C=G[cnt][1].x,D=G[cnt][1].y;
     45                 G[cnt].push_back(point((A*1.0+B+C-D)/2.0,(-A*1.0+B+C+D)/2.0));
     46                 G[cnt].push_back(point((A*1.0-B+C+D)/2.0,(A*1.0+B-C+D)/2.0));
     47                 swap(G[cnt][1],G[cnt][2]);
     48                 G[cnt].push_back(G[cnt][0]);
     49             }
     50             if(shape[0]=='r')///矩形
     51             {
     52                 for(int i=1;i<=3;i++)
     53                 {
     54                     scanf(" (%lf,%lf)",&a,&b);
     55                     G[cnt].push_back(point(a,b));
     56                 }
     57                 G[cnt].push_back(point(G[cnt][0].x*1.0+G[cnt][2].x-G[cnt][1].x,G[cnt][0].y*1.0+G[cnt][2].y-G[cnt][1].y));
     58                 G[cnt].push_back(G[cnt][0]);
     59             }
     60             if(shape[0]=='l')///线
     61             {
     62                 for(int i=1;i<=2;i++)
     63                 {
     64                     scanf(" (%lf,%lf)",&a,&b);
     65                     G[cnt].push_back(point(a,b));
     66                 }
     67             }
     68             if(shape[0]=='t')///三角形
     69             {
     70                 for(int i=1;i<=3;i++)
     71                 {
     72                     scanf(" (%lf,%lf)",&a,&b);
     73                     G[cnt].push_back(point(a,b));
     74                 }
     75                 G[cnt].push_back(G[cnt][0]);
     76             }
     77             if(shape[0]=='p')///多边形
     78             {
     79                 scanf("%d",&m);
     80                 for(int i=1;i<=m;i++)
     81                 {
     82                     scanf(" (%lf,%lf)",&a,&b);
     83                     G[cnt].push_back(point(a,b));
     84                 }
     85                 G[cnt].push_back(G[cnt][0]);
     86             }
     87             scanf("%s",op);
     88         }
     89         for(int i=0;i<26;i++)
     90         {
     91             int flag=0;
     92             set<int>SET;
     93             if((int)G[i].size()==0)continue;
     94             for(int j=0;j<(int)G[i].size()-1;j++)
     95             {
     96                 for(int k=0;k<26;k++)
     97                 {
     98                     if((int)G[k].size()==0||i==k)continue;
     99                     for(int l=0;l<(int)G[k].size()-1;l++)
    100                     {
    101                         if(judge(G[i][j],G[i][j+1],G[k][l],G[k][l+1]))
    102                         {
    103                             flag=1;
    104                             SET.insert(k);
    105                             break;
    106                         }
    107                     }
    108                 }
    109             }
    110             if(flag==1)
    111             {
    112                 vector<int>VEC(SET.begin(),SET.end());
    113                 int len=(int)VEC.size();
    114                 printf("%c intersects with",i+'A');
    115                 if(len==2)
    116                 {printf(" %c and %c\n",VEC[0]+'A',VEC[1]+'A');continue;}
    117                 for(int l=0;l<len-1;l++)
    118                     printf(" %c,",VEC[l]+'A');
    119                 if(len>1)
    120                     printf(" and %c",VEC[len-1]+'A');
    121                 else
    122                     printf(" %c",VEC[len-1]+'A');
    123                 printf("\n");
    124             }
    125             else
    126                 printf("%c has no intersections\n",i+'A');
    127         }
    128         printf("\n");
    129     }
    130     return 0;
    131 }

    转载于:https://www.cnblogs.com/taozi1115402474/p/9465495.html

    展开全文
  • 本文基础是地球坐标系下判断线段相交,请参考 http://blog.csdn.net/philipzeng/archive/2010/07/22/5754339.aspx<br />能判断线段相交了,多边形相交问题也就迎刃而解。   class ...

    本文基础是地球坐标系下判断线段相交,请参考

    http://blog.csdn.net/philipzeng/archive/2010/07/22/5754339.aspx

    能判断线段相交了,多边形相交问题也就迎刃而解。

     

    class PolygonRegion
    {
    public:
     explicit PolygonRegion(vector<TSectorPoint> &vRegion);
     bool __stdcall IsOverlap(vector<TSectorPoint> vRegion);
    private:
     vector<TSectorPoint> vPoints;
    };

     

    /**********************************************************************
    * 函数名称: Polygon
    * 功能描述: 多边形类构造函数
    * 输入参数:
    * 输出参数:
    * 返 回 值: 无
    * 其它说明:
    * 修改日期    版本号     修改人      修改内容
    ***********************************************************************/
    PolygonRegion::PolygonRegion(vector<TSectorPoint> &vRegion)
    {
     vPoints=vRegion;
    }
    /**********************************************************************
    * 函数名称: IsOverlap
    * 功能描述: 判断是否与另外一个多边形相交
    * 输入参数:
    * 输出参数:
    * 返 回 值: 无
    * 其它说明:
    * 修改日期    版本号     修改人      修改内容
    ***********************************************************************/
    bool __stdcall PolygonRegion::IsOverlap(vector<TSectorPoint> vPolygon)
    {
     vPoints.push_back(vPoints[0]);
     vPolygon.push_back(vPolygon[0]);
     for(unsigned int iLoop=0;iLoop < vPoints.size()-1;iLoop++)
     {
      TLine line(vPoints[iLoop],vPoints[iLoop+1]);
      for(unsigned int iLoop2=0;iLoop2 < vPolygon.size()-1;iLoop2++)
      {
       TLine checkline(vPolygon[iLoop2],vPolygon[iLoop2+1]);
       if(line.IsLineCross(checkline)==true)
       {
        vPoints.pop_back();
        return true;
       }
      }
      TLine checkline(vPolygon[0],vPolygon[vPolygon.size()-1]);
      if(line.IsLineCross(checkline)==true)
      {
       vPoints.pop_back();
       return true;
      }
     }
     vPoints.pop_back();
     return false;
    }

    展开全文
  • int inter(Point a,Point b,Point c,Point d)///判断线段是否相交,不规范相交。 { if (dblcmp(max(a.x, b.x)-min(c.x, d.x)) >= 0 && dblcmp(max(c.x, d.x)-min(a.x, b.x)) >= 0 && dblcmp(max(a.y, b.y)-min(c.y...

    网址:点击打开链接

    Geometric Shapes
    Time Limit: 2000MS   Memory Limit: 65536K
    Total Submissions: 1614   Accepted: 680

    Description

    While creating a customer logo, ACM uses graphical utilities to draw a picture that can later be cut into special fluorescent materials. To ensure proper processing, the shapes in the picture cannot intersect. However, some logos contain such intersecting shapes. It is necessary to detect them and decide how to change the picture.

    Given a set of geometric shapes, you are to determine all of their intersections. Only outlines are considered, if a shape is completely inside another one, it is not counted as an intersection.

    Input

    Input contains several pictures. Each picture describes at most 26 shapes, each specified on a separate line. The line begins with an uppercase letter that uniquely identifies the shape inside the corresponding picture. Then there is a kind of the shape and two or more points, everything separated by at least one space. Possible shape kinds are:

    • square: Followed by two distinct points giving the opposite corners of the square.
    • rectangle: Three points are given, there will always be a right angle between the lines connecting the first point with the second and the second with the third.
    • line: Specifies a line segment, two distinct end points are given.
    • triangle: Three points are given, they are guaranteed not to be co-linear.
    • polygon: Followed by an integer number N (3 ≤ N ≤ 20) and N points specifying vertices of the polygon in either clockwise or anti-clockwise order. The polygon will never intersect itself and its sides will have non-zero length.

    All points are always given as two integer coordinates X and Y separated with a comma and enclosed in parentheses. You may assume that |X|, |Y | ≤ 10000.

    The picture description is terminated by a line containing a single dash (“-”). After the last picture, there is a line with one dot (“.”).

    Output

    For each picture, output one line for each of the shapes, sorted alphabetically by its identifier (X). The line must be one of the following:

    • “X has no intersections”, if X does not intersect with any other shapes.
    • “X intersects with A”, if X intersects with exactly 1 other shape.
    • “X intersects with A and B”, if X intersects with exactly 2 other shapes.
    • “X intersects with A, B, . . ., and Z”, if X intersects with more than 2 other shapes.

    Please note that there is an additional comma for more than two intersections. A, B, etc. are all intersecting shapes, sorted alphabetically.

    Print one empty line after each picture, including the last one.

    Sample Input

    A square (1,2) (3,2)
    F line (1,3) (4,4)
    W triangle (3,5) (5,5) (4,3)
    X triangle (7,2) (7,4) (5,3)
    S polygon 6 (9,3) (10,3) (10,4) (8,4) (8,1) (10,2)
    B rectangle (3,3) (7,5) (8,3)
    -
    B square (1,1) (2,2)
    A square (3,3) (4,4)
    -
    .

    Sample Output

    A has no intersections
    B intersects with S, W, and X
    F intersects with W
    S intersects with B
    W intersects with B and F
    X intersects with B
    
    A has no intersections
    B has no intersections
    题意:此题的输入输出实在是恶心- - 出题人绝壁是抱着虐我们的心态出题的..

    输入一个字母,表示多边形的名字

    输入一个多边形类型,可以是正方形,直线,矩形,三角形,多边形

    最后让你按照名字的字典序输出分别和哪几个多边形相交了。

    思路:具体就不说了,注意要用不规范相交,互跨是判断不出一条线段包含另一条线段的情况的,看代码吧,写了好久,真的恶心到了= = 

    代码:

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    #define N 30
    #define eps 1e-8
    struct Point
    {
        double x,y;
    };
    struct Node
    {
        char name[2];
        int flag;
        int num;
        Point d[N];
    } node[N];
    void get(Point a,Point c,Point *b,Point *d)///已知正方形一条对角线上的两个点,求另外两个点
    {
        ///已知ac点,求bd点
        double x,y,mx, my;
        mx = (a.x+c.x)/2.0, my = (a.y+c.y)/2.0;
        x = a.x - mx;
        y = a.y - my;
        (*b).x = -y + mx;
        (*b).y = x + my;
        x = c.x - mx;
        y = c.y - my;
        (*d).x = - y + mx;
        (*d).y = x + my;
    }
    bool cmp(Node a,Node b)
    {
        return a.name[0]<b.name[0];
    }
    
    double cross(Point a,Point b,Point c) ///叉积
    {
        return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
    }
    
    int dblcmp(double m)
    {
        if (fabs(m) < eps) return 0;
        return m > 0 ? 1 : -1;
    }
    
    int inter(Point a,Point b,Point c,Point d)///判断线段是否相交,不规范相交。
    {
        if (dblcmp(max(a.x, b.x)-min(c.x, d.x)) >= 0 && dblcmp(max(c.x, d.x)-min(a.x, b.x)) >= 0
                && dblcmp(max(a.y, b.y)-min(c.y, d.y)) >= 0 && dblcmp(max(c.y, d.y)-min(a.y, b.y)) >= 0
                && dblcmp(cross(a, d, c)*cross(b, d, c)) <= 0 && dblcmp(cross(c, b, a)*cross(d, b, a)) <= 0)
            return 1;
        return 0;
    
    }
    int check(Node a,Node b)///判断多边形a是否和多边形b相交,注意内含算不相交
    {
        a.d[a.num]=a.d[0];
        b.d[b.num]=b.d[0];
        for(int i=0; i<a.num; i++)
            for(int j=0; j<b.num; j++)
                if(inter(a.d[i],a.d[i+1],b.d[j],b.d[j+1]))
                    return 1;
        return 0;
    }
    int main()
    {
        Point a,c;
        while(1)
        {
            char op[N];
            int t=0;
            while(scanf("%s",node[t++].name))
            {
                if(node[t-1].name[0]=='-'||node[t-1].name[0]=='.')
                    break;
                scanf("%s",op);
                if(strcmp(op,"square")==0)///正方形
                {
                    node[t-1].flag=0;
                    scanf(" (%lf,%lf)",&node[t-1].d[0].x,&node[t-1].d[0].y);
                    scanf(" (%lf,%lf)",&node[t-1].d[2].x,&node[t-1].d[2].y);
                    Point b, d;
                    get(node[t-1].d[0],node[t-1].d[2],&node[t-1].d[1],&node[t-1].d[3]);
                    node[t-1].num=4;
                }
                else if(strcmp(op,"line")==0)///直线
                {
                    scanf(" (%lf,%lf)",&node[t-1].d[0].x,&node[t-1].d[0].y);
                    scanf(" (%lf,%lf)",&node[t-1].d[1].x,&node[t-1].d[1].y);
                    node[t-1].num=2;
                }
                else if(strcmp(op,"triangle")==0)///三角形
                {
                    scanf(" (%lf,%lf)",&node[t-1].d[0].x,&node[t-1].d[0].y);
                    scanf(" (%lf,%lf)",&node[t-1].d[1].x,&node[t-1].d[1].y);
                    scanf(" (%lf,%lf)",&node[t-1].d[2].x,&node[t-1].d[2].y);
                    node[t-1].num=3;
                }
                else if(strcmp(op,"rectangle")==0)///矩形
                {
                    scanf(" (%lf,%lf)",&node[t-1].d[0].x,&node[t-1].d[0].y);
                    scanf(" (%lf,%lf)",&node[t-1].d[1].x,&node[t-1].d[1].y);
                    scanf(" (%lf,%lf)",&node[t-1].d[2].x,&node[t-1].d[2].y);
                    node[t-1].d[3].x = node[t-1].d[2].x + (node[t-1].d[0].x - node[t-1].d[1].x);
                    node[t-1].d[3].y = node[t-1].d[2].y + (node[t-1].d[0].y - node[t-1].d[1].y);
                    node[t-1].num=4;
                }
                else if(strcmp(op,"polygon")==0)///多边形
                {
                    scanf("%d",&node[t-1].num);
                    for(int i=0; i<node[t-1].num; i++)
                        scanf(" (%lf,%lf)",&node[t-1].d[i].x,&node[t-1].d[i].y);
                }
            }
            if(node[t-1].name[0]=='.')
                break;
            t--;
            sort(node,node+t,cmp);
            int cnt;
            for(int i=0; i<t; i++)
            {
                cnt=0;
                for(int j=0; j<t; j++)
                {
                    if(i==j) continue;
                    if(check(node[i],node[j]))
                        op[cnt++]=node[j].name[0];
                }
                if(cnt==0)
                    printf("%c has no intersections\n",node[i].name[0]);
                else if(cnt==1)
                    printf("%c intersects with %c\n",node[i].name[0],op[0]);
                else if(cnt==2)
                    printf("%c intersects with %c and %c\n",node[i].name[0],op[0],op[1]);
                else
                {
                    printf("%c intersects with ",node[i].name[0]);
                    for(int j=0; j<cnt-1; j++)
                        printf("%c, ",op[j]);
                    printf("and %c\n",op[cnt-1]);
                }
            }
                printf("\n");
        }
        return 0;
    }
    


    展开全文
  • 判断多边形多边形是否相交

    千次阅读 2019-11-22 16:37:34
    思路:判断多边形、线段是否和另一多边形相交,可先判断他们的控制矩形是否相交。然后再做点是否在多边形中的判断。【多边形的控制矩形,即能围住多边形的最小矩形。】 当矩形的边与多边形的顶点相交的时刻,不记为...
  • 判断两个多边形是否相交相交

    千次阅读 2020-04-22 15:49:00
    //判断多边形线段是否相交 function isSegmentsIntersectant(segA, segB) {//线线 const abc = (segA[0][0] - segB[0][0]) * (segA[1][1] - segB[0][1]) - (segA[0][1] - segB[0][1]) * (segA[1][0]...
  • 判断两个多边形是否相交 ,未完,不可使用 package org.dxl; import lombok.AllArgsConstructor; import lombok.Data; import lombok.NoArgsConstructor; /** * * @projectName launcher2 * * @title Test * ...
  • 比如:判断地图中的多边形与多边形是否相交。我在项目中具体的需求就是如此,需要过滤某个区域的瓦片地图。先把瓦片地图反向解析成Envolope,然后和该区域进行比对,再做其他处理。  其实在已经有开源的东西GDAL...
  • //判断线段p1p2, 线段q1q2是否相交 int intersection(Point p1 , Point p2 ,Point q1 , Point q2){ double d1 = (p2 - p1) ^ (q1 - p1) ; double d2 = (p2 - p1) ^ (q2 - p1) ; double d3 = (q2 - q1) ^ (p1 - ...
  • //aa, bb为一条线段两端点 cc, dd为另一条线段的两端点 相交返回true, 不相交返回false bool intersect(MapPoint aa, MapPoint bb, MapPoint cc, MapPoint dd) { if (Math.Max(aa.x, bb.x) (cc.x, dd.x)) { ...
  • 判断两个凸多边形是否相交—SAT

    千次阅读 2018-04-26 16:39:14
    介绍https://www.codeproject.com/Articles/15573/D-Polygon-Collision-Detection应用分离轴定理 SAT ,看是否能找到分离轴,如果能找到那么就是不相交。否则相交。利用点积的几何意义: 投影源码判断 polya 和 ...
  • 概念:通过判断任意两个凸多边形在任意角度下的投影是否均存在重叠,来判断是否发生碰撞。若在某一角度光源下,两物体的投影存在间隙,则为不碰撞,否则为发生碰撞。 图例: 在程序中,遍历所有角度是不现实的。...
  • 给定一个多边形点序列,如何判断是否有边自相交? 如果两两线段求交则复杂度太高,请问有没有复杂度低的算法?
  • //判断多边形边界是否相交 function isPolygonsIntersectant($plyA, $plyB) {//面面 for ($i = 0, $il = count( $plyA ); $i < $il; $i++) { for ($j = 0, $jl = count( $plyB ); $j < $jl; $j++)...
  • 真的很讨厌,数学不是太好,但是几何还好,纵使是这样,该忘了的还是忘了...为了解决在百度API中缺少图形是否相交判断,所以必须,要判断两个图形边缘的点,这下问题就来了, 网上搜一大片,全是绘制View的,找了很
  • 判断2个多边形相交

    2020-03-06 15:21:32
    2个多边形的边是否相交。 点在内部。2个多边形的顶点是否在另一个多边形的内部。 关于这2个条件的判断: 《碰撞检测:判断点是否在多边形内部》 https://blog.csdn.net/StevenKyleLee/article/details/88044589 ...
  • 碰撞检测:判断2个多边形相交

    千次阅读 2019-03-02 14:41:09
    演示demo: 需要判断2个条件 边相交。2个多边形的边是否相交。 点在内部。2个多边形的顶点是否在另一个多边形的内部。 关于这2个条件的判断: 《碰撞检测:判断点是否在多边形内部》 ...
  • 扫描线算法判断多边形是否合法

    千次阅读 2013-05-04 01:59:29
    题目大意:就是求多边形面积,可能是凹多边形,还有就是判断不能形成多边形的情况 解题思路:使用扫描线算法判断是否存在不相邻的两条边是否有交点,以及相邻的边是否重叠;  使用的一些小trick  线段相交...
  • 在recast中遇到的一个操作,判断点是在线段的...判断线段是否相交判断两点是否在线段两侧等等。 如https://blog.csdn.net/qiushangren/article/details/90446381 这篇博客所说,顺时针方向 三点组成的向量的叉积...
  • 判断平面内点是否多边形内有多种算法,其中射线法是其中比较好理解的一种,而且能够支持凹多边形的情况。该算法的思路很简单,就是从目标点出发引一条射线,看这条射线和多边形所有边的交点数目。如果有奇数个交点...
  • 分析: 除了圆盘之外,本题的输入也是一个PSLG,因此可以按照前面叙述的算法求出各个区域。但由于本题的特殊性,不难发现...如何让判断多边形是否和圆盘相交?,显然,如果多边形的边和圆周规范相交,圆盘和多变性一定
  • 乍一看这标题,多像是...如果要判断是否在矩形或者圆内部,其实很简单。/** * 勾股定理 * 圆心:cx, cy * 半径: r */ const inside = (p.x - cx) ** 2 + (p.y - cy) ** 2 <= r ** 2 /** * 矩形 * 左...
  • 题目来源: ...   题意: 给定n个点的, 如果这n个点不能形成多边形 以及 n 分析: ... 枚举 每条边, 看 这条边 是否与 其他 n - 3 条边 不规范相交。 (当处理 其他 边时, 我们采用 扩充线段一倍)
  • 题意是判断多边形是否相交 主要的思路就是判断每一个点是否在另外的多变形内 判断一个点是否在另一个多边形内主要思路是: 判断的那个点向左边做射线,如果射线与多边形的交点为奇数个则在多边形内,偶数个则不在,...
  • N不能构成多边形,输出Impossible 然后 在两层循环: 1) i= 1->n  2 ) j = 0->i-2  判断两线段之间是否相交,如果相交不构成多边形。 如果不相交,则能构成多边形。 在利用叉积求...
  • 题目来源: ... 题意: 给定n个点的, 如果这n个点不能形成多边形 以及 n < 3 时, 输出, “Impossible”, 否则 输出 多边形的...这题主要在 分析 n 个点 是否形成 多边形。 枚举 每条边, 看 这条边 是否与 其...
  • 判断新生成的area是否为空 代码: import java.awt.Polygon; import java.awt.geom.Area; Polygon p = new Polygon(new int[]{1,1,3,3},new int[]{0,1,1,0},4); Polygon p1 = new Poly
  • 任意多边形与矩形的相交,其实就是判断多条线段是否与这个矩形相交,再简单点就是判断线段是否与矩形的每一条边相交了。那现在,我们先来看看判断一条线段与矩形的其中一条线段的相交的情况(上方水平线):(图形中的a...

空空如也

空空如也

1 2 3 4 5 ... 15
收藏数 285
精华内容 114
关键字:

判断多边形是否相交