日期:2014-05-20  浏览次数:20840 次

发一个面试题:如何判断两个矩形有相交的部分?

假设两个矩形都是平行于坐标轴的,如何判断两个矩形有相交的部分?

当时没没有思路,就放弃了,看看大家是不是有好的实现方法

------解决方案--------------------
判断一个矩形的四个顶角是否在另一个矩形内部
------解决方案--------------------
楼主你上面贴的还是有问题
只判断矩形A的4个顶点在不在矩形B中还不够
还要反过来再判断下矩形B的4个顶点在不在矩形A中
------解决方案--------------------
Java code
package test;

public class Test {
    public static void main(String[] args) {
        Rect r1 = new Rect(0, 0, 5, 5);
        Rect r2 = new Rect(2, 2, 2, 2);
        Rect r3 = new Rect(6, 6, 2, 2);
        Rect r4 = new Rect(-2, -2, 1, 2);
        
        System.out.println(r1.intersection(r2));
        System.out.println(r1.intersection(r3));
        System.out.println(r1.intersection(r4));
    }
}

class Rect {
    int x, y;
    int w, h;

    public Rect(int x, int y, int w, int h) {
        this.x = x;
        this.y = y;
        this.w = w;
        this.h = h;
    }

    public boolean intersection(Rect r) {
        // 两个矩形的水平与垂直区间都相交,两个矩形才相交
        if ((interval(x, x + w, r.x) || interval(x, x + w, r.x + r.w))
                && (interval(y, y + h, r.y) || interval(y, y + h, r.y + r.h))) { return true; }

        return false;
    }

    // 判断value是否在区间[start, end]之中
    public static boolean interval(int start, int end, int value) {
        if (start <= value && value <= end) { return true; }
        return false;
    }
}

------解决方案--------------------
假设这俩个矩形分别是A和B。只要保证 A的最右边坐标 > B的最左边坐标 && A的最左边坐标 < B 的最右边坐标。就可以了吧。
以前做过一个碰撞检测就是这样实现的。
------解决方案--------------------
假设矩形A和B分别有(p1, p2)和(p3, p4)确定(主对角线上的两个点),p1,p3分别是A、B的左上角点,p2、p4分别是A、B的右下角点

那么两个矩阵不相交的情况是:p1.y<p2.y(A在B的下方)或p1.x>p4.x(A在B的右边)或p2.y>p3.y(A在B的上方)或p2.x<p3.x(A在B的左边)
所以
不相交:p1.y<p2.y || p1.x>p4.x || p2.y>p3.y || p2.x<p3.x
相交:!(p1.y<p2.y || p1.x>p4.x || p2.y>p3.y || p2.x<p3.x)
由德摩根定律知相交的情况是:
p1.y>=p2.y && p1.x<=p4.x && p2.y<=p3.y && p2.x>=p3.x

所以:
boolean isIntersected(p1, p2, p3, p4) {
return p1.y>=p2.y && p1.x<=p4.x && p2.y<=p3.y && p2.x>=p3.x;
}