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

Question

lZ 多看点API  里面 我记得好像有一个 实现这个的方法，自己写也可以

Answer 1

use intersects(Rectangle r) method of Rectangle 
or contains method

Answer 2

http://topic.csdn.net/u/20110509/14/6d2303b8-dc6c-4d74-9f82-d06e3b5fbcd2.html
看看

Answer 3

public class RectangleTest {
static final class Point{
private final int x;
private final int y;
public int getX() {
return x;
}
public int getY() {
return y;
}
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
static final class Rectangle{
private final Point p1;
private final Point p2;
public Rectangle(Point p1,Point p2){
this(p1.getX(),p1.getY(),p2.getX(),p2.getY());
}
public Rectangle(int x1,int y1,int x2,int y2){
p1 = new Point(x1,y1);
p2 = new Point(x2,y2);
}
public Point getP1() {
return p1;
}
public Point getP2() {
return p2;
}
public boolean containsPoint(Point p){
int x1 = p1.getX();
int x2 = p2.getX();
int y1 = p1.getY();
int y2 = p2.getY();
int x = p.getX();
int y = p.getY();
return (x>=x1 && x<=x2)&&(y>=y1 && y<=y2);
}
public boolean hasCommonPart(Rectangle r){
Point leftDown = this.p1;
Point rightUp = this.p2;
Point leftUp = new Point(p1.getX(),p2.getY());
Point rightDown = new Point(p2.getX(),p1.getY());
return r.containsPoint(leftDown)||r.containsPoint(rightUp)||r.containsPoint(leftUp)||r.containsPoint(rightDown);
}
}
public static void main(String[] args) {
Rectangle r1 = new Rectangle(0,0,5,5);
Rectangle r2 = new Rectangle(5,5,7,7);
System.out.println(r1.hasCommonPart(r2));
}}
//原来大家都会，这是我回来以后得出的答案，就是看四个顶点是不是在另一个矩形内部
//面试的时候，很明显人家是在考你思路，你告诉人家API里面提供了，你觉得合适吗？
//类似的题目，还经历过：写一个字符串形式表示的大数的加法，你给搞成BigInteger有意思吗？

Answer 4

如果不用现成的相交API的话，思路可以这样：
新建一个包含2个矩形的最小矩形
新矩形的两个边长如果都大于2个旧矩形的边长之和，则不相交

Answer 5

楼主你上面贴的还是有问题
只判断矩形A的4个顶点在不在矩形B中还不够
还要反过来再判断下矩形B的4个顶点在不在矩形A中

Answer 6

有必要吗？
又想到一个简单的办法：只需要判断最远的两个点的距离小于两个矩形的边长之和不就可以了吗？求验证！public boolean intersects(Rectangle r){
int x1 = p1.x;
int y1 = p1.y;
int x2 = p2.x;
int y2 = p2.y;
int x3 = r.p1.x;
int y3 = r.p1.y;
int x4 = r.p2.x;
int y4 = r.p2.y;
return (Math.abs(x4-x1)<=x2-x1+x4-x3) && (Math.abs(y4-y1) <= y2-y1+y4-y3);
}

Answer 7

你想到的办法跟我说的建新矩形是一回事Math.abs(x4-x1)<=x2-x1+x4-x3) && (Math.abs(y4-y1) <= y2-y1+y4-y3abs(x4-x1) 新矩形宽
x2-x1+x4-x3 俩旧矩形宽度之和高度类似

Answer 8

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;
    }
}

Answer 9

名字没取好，应该使用动词intersects

Answer 10

    public boolean intersects(Rectangle r) {
        int tw = this.width;
        int th = this.height;
        int rw = r.width;
        int rh = r.height;
        if (rw <= 0 || rh <= 0 || tw <= 0 || th <= 0) {
            return false;
        }
        int tx = this.x;
        int ty = this.y;
        int rx = r.x;
        int ry = r.y;
        rw += rx;
        rh += ry;
        tw += tx;
        th += ty;
        //      overflow || intersect
        return ((rw < rx || rw > tx) &&
                (rh < ry || rh > ty) &&
                (tw < tx || tw > rx) &&
                (th < ty || th > ry));
    }这个。不怎么明白呢 = =

Answer 11

假设这俩个矩形分别是A和B。只要保证   A的最右边坐标 > B的最左边坐标  && A的最左边坐标 < B 的最右边坐标。就可以了吧。
以前做过一个碰撞检测就是这样实现的。

Answer 12

这个确实是最简单高效的：
    public boolean intersects(Rect r) {
        // 只要保证: A的最左边坐标 <= B的最右边 && A的最右边坐标 >= B的最左边坐标
        if ((x <= r.x + r.w && x + w >= r.x) && (y <= r.y + r.h && y + h >= r.y)) { return true; }
        return false;
    }

Answer 13

两个矩形的x轴上的中心距离  >  两个矩形的长度之和的一半
两个矩形的y轴上的中心距离  >  两个矩形的高度之和的一半

Answer 14

假设矩形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;
}

Answer 15

//综合诸位大仙的结果如下：
public class Rectangle2Test {
private static final class Rectangle {
final int x, y;// 左下角的点的x和y坐标
final int w, h;// 矩形的宽度和高度
/*   Y
 *\ /|\ 
 *   |  假设坐标系是这样：
 *   |
 *   |--------->X
 * */
public Rectangle(int x, int y, int w, int h) {
this.x = x;
this.y = y;
this.w = w;
this.h = h;
}
/*
 * 第一种方法
 */
public boolean intersects1(Rectangle 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]之中
private static boolean interval(int start, int end, int value) {
if (start <= value && value <= end) {
return true;
}
return false;
}
/*
 * 第二种方法
 */
public boolean intersects2(Rectangle r) {
// 只要保证: A的最左边坐标 <= B的最右边 && A的最右边坐标 >= B的最左边坐标
if ((x <= r.x + r.w && x + w >= r.x)
&& (y <= r.y + r.h && y + h >= r.y)) {
return true;
}
return false;
}
/*
 * 第三种方法
 * 
 * 假设矩形A和B分别有(p1, p2)和(p3,p4)确定（主对角线上的两个点），
 * p1,p3分别是A、B的左下角点，p2、p4分别是A、B的右上角点
 * 那么两个矩阵不相交的情况是：
 * p2.y<p3.y（A在B的下方）或p4.x<p1.x（A在B的右边）或p4.y<p1.y（A在B的上方）或p2.x<p3.x（A在B的左边）
 * 所以: 
 * 不相交：p2.y<p3.y || p4.x<p1.x || p4.y<p1.y || p2.x<p3.x
 * 相交：!(p2.y<p3.y || p4.x<p1.x || p4.y<p1.y || p2.x<p3.x) 
 * 由德摩根定律知相交的情况是：
 * p2.y>=p3.y && p4.x>=p1.x && p4.y>=p1.y && p2.x>=p3.x 
 * 所以：
 */
public boolean intersects3(Rectangle r) {
int x1 = this.x;
int y1 = this.y;
int x2 = x1 + w;
int y2 = x2 + h;
int x3 = r.x;
int y3 = r.y;
int x4 = x3 + r.w;
int y4 = y3 + r.h;
return y2 >= y3 && x4 >= x1 && y4 >= y1 && x2 >= x3;
}
} public static void main(String[] args) {
Rectangle r1 = new Rectangle(0, 0, 5, 5);
Rectangle r2 = new Rectangle(2, 2, 2, 2);
Rectangle r3 = new Rectangle(6, 6, 2, 2);
Rectangle r4 = new Rectangle(-2, -2, 1, 2); System.out.println(r1.intersects1(r2));
System.out.println(r1.intersects1(r3));
System.out.println(r1.intersects1(r4)); System.out.println(r1.intersects2(r2));
System.out.println(r1.intersects2(r3));
System.out.println(r1.intersects2(r4)); System.out.println(r1.intersects3(r2));
System.out.println(r1.intersects3(r3));
System.out.println(r1.intersects3(r4));
}
}

Answer 16

突然想到错了, 是&&, 汗颜

Answer 17

看这里,矩形相交合并分析
http://goo.gl/90FW

Answer 18

经分析，
两个矩形的x轴上的中心距离 > 两个矩形的长度之和的一半
两个矩形的y轴上的中心距离 > 两个矩形的高度之和的一半
以上是 || 的关系，则两矩阵不相交，反之相交
这个方法比较简单，而且考虑全面

Answer 19

若是两个矩形大小嵌套，
( 两个矩形的x轴上的中心距离 > 两个矩形的长度之和的一半 || 两个矩形的y轴上的中心距离 > 两个矩形的高度之和的一半 )  结果为依然为1，判断相交。矩阵的相交类型 还得具体再判断。