线段与线段、矩形相交问题

发表于 更新于 阅读次数：

图形学问题

最近在做毕设时，遇到 判断线段是否经过矩形障碍物的图形学问题。

为了解决这一问题，我们先看看 如何判断两线段是否相交

线段与线段是否相交

具体解决办法大致可以分为两个步骤。

a.快速排斥实验

若以该线段为对角线的矩形A与该障碍物矩形B不重合，则显然这两线段不相交。

但，若矩形A与矩形B重合，则并不一定代表这两线段相交。

1

b.跨立实验

如果两线段相交，则线段AB的两端点必然在线段CD两侧，同时线段CD的两端点也必然在线段AB的两侧。

2

因此我们 可以通过叉积来判断 ABMC=AB x AC，ABMD=AB x AD

若ABMC * ABMD < 0, 则代表CD在AB 直线 的异侧。

接下来还应该判断 CDMA = CD x CA， CDMB = CD x CB。

若CDMA * CDMB < 0, 则代表AB在CD 直线 的异侧。

因此，若满足ABMC · ABMD < 0 且 CDMA · CDMB < 0 则 则这两线段必相交，否则不相交。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct node  
{  
    double x,y;  
};    
double Cross_Prouct(node A,node B,node C)       //  计算BA叉乘CA；  
{  
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);   //向量叉积运算  
}  
bool Intersect(node A,node B,node C,node D)     //  通过叉乘判断线段是否相交；  
{  
    if(min(A.x,B.x)<=max(C.x,D.x)&&         //  快速排斥实验；  
       min(C.x,D.x)<=max(A.x,B.x)&&  
       min(A.y,B.y)<=max(C.y,D.y)&&  
       min(C.y,D.y)<=max(A.y,B.y)&&  
       Cross_Prouct(A,B,C)*Cross_Prouct(A,B,D)<0&&      //  跨立实验；  
       Cross_Prouct(C,D,A)*Cross_Prouct(C,D,B)<0)       //  叉乘异号表示在两侧；  
       return true;  
    else return false;  
}

当然判断可以直接从b开始，a只是起简单快速判断的作用。

线段与矩形是否相交

探索完了两线段是否相交的问题，我们开始步入正题，来看看怎么判断线段是否与矩形相交。

a.判断线段两端点是否有一个端点或两端点都在矩形中，若有则相交，否则进入b判断。

3

1
2
3
4
5
6
7
//A,C为对角线的两点
bool checkIfOutsideobstacles(node A, node C, nade M) {
    if(min(A.x, C.x) <= M.x && M.x <= max(A.x, C.x) && min(A.y, C.y) <= M.y && M.y <= max(A.y, C.y)){
        return false;
    }
    return true;
}

经过a判断排除后，代表线段两端点都在矩形外。

再介绍b判断前，先介绍下，若一线段端点都在矩形外，且该线段与矩形相交，那么该线段必然与该矩形中的某一条对角线相交。 因此，又回到开始判断两线段是否相交上面。

b. 分别判断该线段是否与矩形的两条对角线是否相交，若都不相交，则代表该线段与矩形不相交，否则 相交。

另外补充：

一些常用的计算几何算法概览