摸鱼第一,干活第二

It's time for BOOM!(ノ≧∀≦)ノ

【计算几何】线段相交判断

学习&借鉴于:勿忘初心0924点击这里


要判断这玩意,要用到两步操作:

1、快速排斥实验

2、跨立实验


快速排斥实验

假设我们有两条线段,分别用两个点坐标表示每条线段\((x_{1},y_{1}),(x_{2},y_{2})\)

同样的,两个点坐标还可以表示一个矩形,所以快速排斥实验的基本思想就是判断矩形是否有重合部分

如果没有重合部分,那么两条线段也不可能相交,否则就要进入跨立实验判断。

以下是一张简图:

《【计算几何】线段相交判断》

当矩形重合时同时满足:

1、a的最低点不高于b的最高点

2、a的最高点不低于b的最低点

3、a的最左点不右于b的最右点

4、a的最右点不左于b的最左点

判断代码(坐标变量以图中为例):

1
2
3
4
if((min(y1,y2)<=max(y3,y4))&&(max(y1,y2)>=min(y3,y4))&&(min(x1,x2)<=max(x3,x4))&&(max(x1,x2)>=min(x3,x4)))
    return true;//矩形重合,通过快速排斥
else
    return false;//矩形不重合,未通过快速排斥

跨立实验

在讲跨立实验之前,我们需要明白一些向量计算法则,因为一会要用到。

1、向量点乘

表示为:

\(\vec{a}\cdot\vec{b}\)或\((x_{a},y_{a})\cdot(x_{b},y_{b})\)

计算过程(\(\theta\)为两向量夹角):

\(\vec{a}\cdot\vec{b}=(x_{a},y_{a})\cdot(x_{b},y_{b})=|\vec{a}||\vec{b}|\cos\theta=x_{a}x_{b}+y_{a}y_{b}\)

由:

\(\vec{a}\cdot\vec{b}>0\;\left(0<\theta<\frac{\pi}{2},\frac{3\pi}{2}<\theta<2\pi\right)\)

\(\vec{a}\cdot\vec{b}<0\;\left(\frac{\pi}{2}<\theta<\frac{3\pi}{2}\right)\)

所以我们可以用它判断两向量是否反向(反向即夹角为180°)。

注:向量点乘结果是一个数值

2、向量叉乘

表示为:

\(\vec{a}\times \vec{b}\)或\((x_{a},y_{a})\times (x_{b},y_{b})\)

与点乘不同,叉乘的结果是一个向量

但是我们用一下式子可以求出结果的模(\(\theta\)为两向量夹角):

\(|\vec{a}\times\vec{b}|=|(x_{a},y_{a})\times(x_{b},y_{b})|=|\vec{a}||\vec{b}|\sin\theta =x_{a}y_{b}-x_{b}y_{a}\)

那么叉乘向量结果的方向到底是什么呢?它垂直原来两向量表示的平面。假设我们使用右手系,如果\(\vec{a}\)需要向逆时针旋转才能与\(\vec{b}\)同向,那么叉乘结果垂直向上,反之垂直向下。(换作左手系则全部相反)

所以,\(\vec{a}\times\vec{b}\)\(\vec{b}\times\vec{a}\)的结果是不同的

我觉得用图可以更好解释:

《【计算几何】线段相交判断》

讲到这里,是不是你已经有点懵了呢?【滑稽】

但是,我郑重地告诉你,以上对计算没有什么卵用,只能让你明白跨立实验的几何意义是什么。我们真正用于跨立实验的是一个叫拉格朗日恒等式的东西。


拉格朗日恒等式

只需要知道可以这样计算就行了。

\((\vec{a}\times\vec{b})\cdot(\vec{c}\times\vec{d})=(\vec{b}\cdot\vec{d})(\vec{a}\cdot\vec{c})-(\vec{b}\cdot\vec{c})(\vec{a}\cdot\vec{d})\)


真·跨立实验

我们已经知道了两条线段的四个点坐标,而且已经通过了快速排斥实验,那么我们以其中一个点为向量起点,以其他点为向量终点,构建出三个向量(如下):

《【计算几何】线段相交判断》

这时其实我们只需要判断(x1,y1)与(x2,y2)是否在向量b两边就行了,这时候拉格朗日恒等式就起作用了

我们分别计算\(\vec{a}\times\vec{b}\)\(\vec{c}\times\vec{b}\),根据叉乘的意义,如果(x1,y1)与(x2,y2)在向量b两边,这两个叉乘结果应该是反向的,这时候只需再点乘一下,如果结果为负,则两线段相交。

但是如果出现了以下这种情况呢?【滑稽】

《【计算几何】线段相交判断》

但如果我们换一条计算的话。。。

《【计算几何】线段相交判断》

这告诉我们要每条线段都算一遍,只有两次都小于0才可以认为它们相交。

最终判断代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct vec2{//向量结构体
    int x1,y1,x2,y2;

    vec2(int a,int b,int c,int d):x1(a),y1(b),x2(c),y2(d){}//构造函数
    int eX(){//转换向量基底
        return x1-x2;
    }
    int eY(){//转换向量基底
        return y1-y2;
    }
};
int dotProduct(vec2 a,vec2 b){//向量点乘
    return a.eX()*b.eX()+a.eY()*b.eY();
}
int lagrange(vec2 a,vec2 b,vec2 c,vec2 d){//拉格朗日恒等式计算
    return dotProduct(b,d)*dotProduct(a,c)-dotProduct(b,c)*dotProduct(a,d);
}
bool isIntersect(vec2 a,vec2 b){//相交判断
    if((min(a.y1,a.y2)<=max(b.y1,b.y2))&&(max(a.y1,a.y2)>=min(b.y1,b.y2))&&(min(a.x1,a.x2)<=max(b.x1,b.x2))&&(max(a.x1,a.x2)>=min(b.x1,b.x2)))//快速排斥
        if((lagrange(a,vec2(a.x1,a.y1,b.x1,b.y1),a,vec2(a.x1,a.y1,b.x2,b.y2))<0)&&(lagrange(b,vec2(b.x1,b.y1,a.x1,a.y1),b,vec2(b.x1,b.y1,a.x2,a.y2))<0))//跨立实验
            return true;
    return false;
}

【END】

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code