[经验分享] C语言判断两线段是否相交

 /*

        利用矢量叉积判断是逆时针还是顺时针。

        设A(x1,y1),B(x2,y2),C(x3,y3),则三角形两边的矢量分别是：

        AB=(x2-x1,y2-y1), AC=(x3-x1,y3-y1)

        则AB和AC的叉积为：(2*2的行列式)

        |x2-x1, y2-y1|

        |x3-x1, y3-y1|

        值为：(x2-x1)*(y3-y1) - (y2-y1)*(x3-x1)

        利用右手法则进行判断：

        如果AB*AC>0,则三角形ABC是逆时针的

        如果AB*AC<0,则三角形ABC是顺时针的

        */

        

        #include<stdio.h>

        #include<math.h>

        

        typedef struct point{

                double x,y;

        }Point; //点

        

        typedef struct vector{

                double x,y;

        }Vector; //向量

        

        typedef struct{

                double xmax,xmin; //矩形在x轴的最小值和最大值

                double ymax,ymin; //矩形在y轴的最小值和最大值

        }MBR; //最小外包矩形

        

        /*返回x和y的最大值*/

        double Max(double x,double y){

                return x>y?x:y;

        }

        

        /*返回x和y的最小值*/

        double Min(double x,double y){

                return x<y?x:y;

        }

        

        /*

        由 A(x1,y1)，B(x2,y2) 构造向量AB

        向AB=OB-OA=(x2-x1, y2-y1)

         */

        Vector VectorConstruct(Point A, Point B) {

                Vector v;

                v.x = B.x - A.x;  

                v.y = B.y - A.y;

                return v;

        }

        

        /*

        向量a(x1,y1)和b(x2,y2)的叉积

        a×b = x1y2-x2y1

        */

        double CrossProduct(Vector a, Vector b) {

                return a.x * b.y - a.y * b.x;

        }

        

        /*

        由A点和B点构造一个最小外包矩形【以线段AB为对角线的矩形】

         */

        MBR MbrConstruct(Point A, Point B) {

                MBR m;

                /*将点A和点B中x值大的赋给xmax，小的赋给xmin*/

                if(A.x > B.x){ 

                        m.xmax = A.x;

                        m.xmin = B.x;

                }

                else{

                        m.xmax = B.x;

                        m.xmin = A.x;

                }

                /*将点A和点B中y值大的赋给ymax，小的赋给ymin*/

                if(A.y > B.y){

                        m.ymax = A.y;

                        m.ymin = B.y;

                }

                else{

                        m.ymax = B.y;

                        m.ymin = A.y;

                }

                return m;

        }

        

        /*

        快速排斥实验【两个MBR在x以及y坐标的投影是否有重合】

        判断两个MBR是否有交集，有返回1，否0

        */

        int MbrOverlap(MBR m1, MBR m2) {

                double xmin, xmax, ymin, ymax;

                xmin = Max(m1.xmin, m2.xmin);   //两个外包矩形中最小x中的大者

                xmax = Min(m1.xmax, m2.xmax);   //两个外包矩形中最大x中的小者

                ymin = Max(m1.ymin, m2.ymin);   //两个外包矩形中最小y中的大者

                ymax = Min(m1.ymax, m2.ymax);   //两个外包矩形中最大y中的小者

                

                /*

                如果：两个外包矩形中最大x中的小者 >= 两个外包矩形中最小x中的大者

                并且：两个外包矩形中最大y中的小者 >= 两个外包矩形中最小y中的大者

                则两个MBR是有交集，返回1

                */

                return (xmax >= xmin && ymax >= ymin) ? 1 : 0;

        }

        

        /*

        方法一：快速排斥+跨立

        判断两线段(线段AB和CD)是否相交，是返回1，否0

        */

        int SegmentIntersection(Point A, Point B, Point C, Point D) {

                MBR m1,m2;

                Vector CA,CB,CD,AC,AD,AB;

        

            /*求线段AB和CD所在的MBR*/

                m1 = MbrConstruct(A, B);

                m2 = MbrConstruct(C, D);

        

                /*【快速排斥实验】判断AB和CD所在的MBR是否相交*/

                if(MbrOverlap(m1, m2) == 0) //不相交，直接返回0

                        return 0; 

                

                /*求向量CA、CB、CD的坐标表示*/

                CA = VectorConstruct(C, A); 

                CB = VectorConstruct(C, B);

                CD = VectorConstruct(C, D);

                

                /*求向量AC、AD、AB的坐标表示*/

                AC = VectorConstruct(A, C);

                AD = VectorConstruct(A, D);

                AB = VectorConstruct(A, B);

                

                /*【跨立实验】进一步判断*/ 

                /*AB跨立CD，并且，CD跨立AB*/

                /*判断条件：(CA×CD)*(CB×CD)<= 0 && (AC×AB)*(AD×AB)<= 0*/

                if (CrossProduct(CA, CD) * CrossProduct(CB, CD) <= 0 && CrossProduct(AC, AB) * CrossProduct(AD, AB) <= 0)

                        return 1;

                else 

                        return 0;

        }

        

        void main(){

                int tag;

                Point A,B,C,D;

                A.x=1,A.y=2;

                B.x=3,B.y=4;

                C.x=1,C.y=3;

                D.x=4,D.y=1;

                /*方法一：快速排斥+跨立试验*/

                tag=SegmentIntersection(A,B,C,D);

                if(tag)

                        printf("两直线相交\n");

                else

                        printf("两直线不相交\n");

        }