2维平面相交（一）：两矩形区域相交

最近遇到几种相交问题，看似简单的逻辑，却有多种不同的算法，不知你是否考虑过所用的算法好不好的问题。

两矩形区域相交

在写随机展示的一个模块时,需要判断随机生成的区域与原有区域是否相交

cross-region

最初想到的方法是：

算法一：如果一个区域有一点在另一区域中，那么两个区域一定相交

js实现代码：

// 判断点在矩形内
function _inRegion(point, region) {

    return point[0] < region.right && point[0] > region.left
        && point[1] < region.top && point[1] > region.bottom;

}
// 判断矩形1是否有点在矩形2中
function _isCross(region1, region2) {

    return  _inRegion([region1.left,region1.top], region2) ||
        _inRegion([region1.right,region1.top], region2) ||
        _inRegion([region1.right,region1.bottom], region2) ||
        _inRegion([region1.left,region1.bottom], region2);

}

function isCross(region1, region2) {

    return _isCross(region1, region2) || _isCross(region2, region1);

}

看到上面的代码觉得实现太麻烦了吧，再来看一种算法：

算法二：如果两个矩形相交，则必然存在线条交叉，而能交叉的线条只有横线和竖线，两根横线或两根竖线都不可能交叉。所以，这个问题就转化成寻找是否存在交叉的横线与竖线。

实现代码：

// 判断横线1是否与竖线2相交
function _crossLine(line1, line2) {
    return line1.from[1] < line2.from[1] && line1.to[1] > line2.to[1] &&
        line1.from[0] < line2.from[0] && line1.to[0] > line2.to[0];
}
//判断矩形1横线是否与矩形2竖线相交
function _isCross(r1, r2) {
    return _crossLine({from:[r1.left,r1.top],to:[r1.right,r1.top]},
        {from:[r2.left,r2.top],to:[r2.left,r2.bottom]}) ||
        _crossLine({from:[r1.left,r1.bottom],to:[r1.right,r1.bottom]},
            {from:[r2.left,r2.top],to:[r2.left,r2.bottom]}) ||
        _crossLine({from:[r1.left,r1.top],to:[r1.right,r1.top]},
            {from:[r2.right,r2.top],to:[r2.right,r2.bottom]}) ||
        _crossLine({from:[r1.left,r1.bottom],to:[r1.right,r1.bottom]},
            {from:[r2.right,r2.top],to:[r2.right,r2.bottom]});
}
function isCross(region1, region2) {
    return _isCross(region1, region2) || _isCross(region2, region1);
}

这种看起来也不简单，但至少是一种思路，还有其他算法吗？有

算法三：如果两个矩形相交，相交区域一定是个点或者矩形

实现代码：

function isCross(region1, region2) {
    var left = Math.max(region1.left, region2.left),
        right = Math.min(region1.right, region2.right),
        top = Math.min(region1.top, region2.top),
        bottom = Math.max(region.bottom, region.bottom);
    return left < right && bottom < top;
}

我靠，代码瞬间减少了很多，再看一种算法：

算法四：如果矩形1的一边距离到矩形2对应边的距离小于等于矩形1的宽度或高度 =>两矩形相交

实现代码：

function isCross(region1, region2) {
    return (region2.left > region1.left &&
            region2.left - region1.left < region1.right - reigon1.left) ||
        (region2.top > region1.top &&
            region2.top - region1.top < region2.top - region2.bottom) ||
        (region1.left > region2.left &&
            region1.left - region2.left < region2.right - reigon2.left) ||
        (region1.top > region2.top &&
            region1.top - region2.top < region1.top - region1.bottom);
}

貌似代码有优化的空间，先不管，考虑还有没有更简练的算法？

算法五：如果一个矩形在另一矩形所形成的四个区间外 <=> 两个矩形不想交

实现代码：

function isCross(region1, region2) {
    return !(region1.left > region2.right || region1.right<region2.left||
        region1.bottom > region2.top || region1.top < region2.bottom);
}

看到这种算法时，我震惊了，无论从代码量还是性能上都优于上面的算法，当然如果需要获取相交区域，算法3更好。

回头看看上面5种算法，从不同的角度出发得到不同的算法：算法1从点的角度触发，算法2从线的角度，
算法3从区域的角度，算法4从一维距离角度，算法5从区间的角度；思量一下，前4种算法都是正向思维，第5种逆向思维；
逆向思维，也许自己太多过程式编程脑子秀逗了，好的算法醍醐灌顶。

结束，下一篇关于如何判断两个线段是否相交，你如何实现？

回顶部