计算几何:线段相交判定 跨立试验和快速排斥试验 木灵的炼金工作室

引例

给出线段AB和CD的端点A, B, C, D的坐标,请判断线段AB和CD是否存在一个交点?

跨立试验

因为我们的算法是面向计算机的,所以我们不能简单地说“把它画出来不就好了吗”这样的话,我们需要给出一个切实可行的算法,我们可以操作的数只有上述给出的四个点的总共八个坐标。

由坐标判断线段的关系,我们可以非常自然地想到使用向量运算。我们又想到,若线段AB与CD相交,则点A和B一定分别在直线CD的两侧,而点C和D一定分别在直线AB的两侧。

但又如何描述这个”两侧”呢?这个是简单的。
如果A和B同在CD的一侧,$\vec{ CD }$ 与 $\vec{ CA }$的叉积 和 $\vec{ CD }$ 与 $\vec{ CB }$的叉积的方向一定相同;而若A和B不在CD的同一侧,$\vec{ CD }$ 与 $\vec{ CA }$的叉积 和 $\vec{ CD }$ 与 $\vec{ CB }$的叉积的方向一定相反。

(什么?你说你不知道什么叫叉积?

二维向量的叉积的实现是简单的:若向量$\vec{ a }$是(Xa, Ya, 0), 向量$\vec{ b }$是(Xb, Yb, 0),则二者之叉积是(0, 0, Xa * Yb - Xb * Ya)

因此我们判断A和B点是否在直线CD两端的算法就是:

  1. 求出向量$\vec{ CA }$、$\vec{ CB }$、$\vec{ CD }$
  2. 做$\vec{ CA }$ × $\vec{ CD }$和$\vec{ CB }$ × $\vec{ CD }$
  3. 判断上述两个结果向量的点乘是否为正,为正则不跨立,为负则跨立,为零则A或B点与CD共线
  4. 对于C和D点与AB直线重做上述的试验,若两者均显示跨立,则两线段相交

实现为C++程序则是:

struct point{
    double x, y;
};

bool Straddle(point Pa, point Pb, point Pc, point Pd) { //true表示相交,false表示不相交
    auto crossProduct = [&] (point VectorA, point VectorB) {
        return VectorA.x * VectorB.y - VectorA.y * VectorB.x;
    };
    point VectorAC = { Pc.x - Pa.x, Pc.y - Pa.y };
    point VectorBC = { Pc.x - Pb.x, Pc.y - Pb.y };
    point VectorDC = { Pc.x - Pd.x, Pc.y - Pd.y };
    bool res = (crossProduct(VectorAC, VectorDC) * crossProduct(VectorBC, VectorDC) <= 0);

    point VectorCA = { Pa.x - Pc.x, Pa.y - Pc.y };
    point VectorDA = { Pa.x - Pd.x, Pa.y - Pd.y };
    point VectorBA = { Pa.x - Pb.x, Pa.y - Pb.y };
    res = res && (crossProduct(VectorCA, VectorBA) * crossProduct(VectorDA, VectorBA) <= 0);

    return res;
}

快速排斥试验

但是,我们也可以看到,用跨立试验计算两个点还可以接受,但在实际的计算几何或者游戏开发的应用场景下,这种算法可能就显得有一点慢了。
那么我们可以进行一些剪枝,比如把明显不可能相交的线段排除掉。

如何排除?两线段相交,则以他们为对角线的矩形一定相交。那么它的逆否命题就是以两线段为对角线的矩形不相交,则两线段一定不相交。为了方便程序运行,我们使这些矩形的两条边分别与x轴和y轴平行:

bool RR(point Pa, point Pb, point Pc, point Pd) {
    bool res = max(Pa.x, Pb.x) > min(Pc.x, Pd.x);
    res = res && min(Pa.x, Pb.x) < max(Pc.x, Pd.x);
    res = res && max(Pa.y, Pb.y) > min(Pc.y, Pd.y);
    res = res && min(Pa.y, Pb.y) < max(Pc.y, Pd.y);
    return res;
}

一般我们将快速排斥试验和跨立试验联合使用,通过快速排斥者进行跨立试验,这样会使得算法的效率提升。


Copyright AmachiInori 2017-2021. All Right Reserved.
Powered By Jekyll.
amachi.com.cn