Java-JAVA面试题,判断两个矩形是否相交的方法

Java-JAVA面试题,判断两个矩形是否相交的方法

甜柠檬 发布于 2017-06-14 字数 111 浏览 2855 回复 21

JAVA面试题,写一方法,判断两个矩形是否相交,矩形的坐标分别是(x1,y1),(x2,y2),(x3,y3),(x4,y4),求代码!

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(21

清晨说ぺ晚安 2017-10-26 21 楼

假设(x1,y1),(x2,y2)分别表示第一个矩形的左下角和右上角的坐标;(x3,y3),(x4,y4)分别表示第二个矩形的左下角和右上角的坐标。若这两个矩形有重叠的区域,则重叠区域必为矩形区域,不妨设重叠区域矩形坐标为(x5,y5),(x6,y6),则有GIS相关的算法理论有:x5=max(x1,x3),y5=max(y1,y3);x6=min(x2,x4),y6=min(y2,y4).反之,若这两个矩形没有重叠区域,那么判断条件就是:求出的(x5,y5),(x6,y6)中x6<x5,y6<y5

甜柠檬 2017-10-18 20 楼

一个矩形A有四个顶点(x1,y1),(x2,y2),(x3,y3),(x4,y4)。在A上任意一点D存在
x1<=Dx<=x2
y1<=Dy<=y3
另一个矩形B(x5,y5),(x6,y6),(x7,y7),(x8,y8)。在B上任意一点存在D
x5<=Dx<=x6
y5<=Dy<=y7
所以我们只需要
不等式x1<=Dx<=x2和x5<=Dx<=x6交集K
不等式y1<=Dy<=y3和y5<=Dy<=y7交集M
判断K和M是否为空集就可以了,如果两个都不是空集才说明有焦点,反之则没有焦点。
当然有种简便的办法:
例如交集K,计x1,x5最大值为O,x2,x6最小值为P
判断O是否大于P,如果大于则为空集,如果不大于再判断两个不等式是否属于O<=Dx<=P的集合
即条件(O==x1&&P==x2||O==x5&&P==x6)为真的话说明一个集合属于另一个集合
剩下的我就不用说了吧。。。。。。。。。。。
ps:不要把问题搞得复杂化,这种是初中数学问题,没有那么难的。
长篇大论的,实在看不下去。

晚风撩人 2017-10-11 19 楼

通过顶点来算的只能满足短形边与坐标轴平行的情况。
为了考虑到所有情况,我建议思路如下:

矩形A与矩形B相交,必定会有A至少其中一边所在的直线,与B至少其中一边所在的直线相交。
根据这个结论可以按如下步骤解答
1.根据顶点分别求出A,B两矩形的每一边的直线方程式
2.用简到的直接线方程式分别判断A中的边所在直线是否与B中的边所在直线相交的点。
3.如果一个点也没有,说明矩形不相交
4.如果有有相交点P,在得到P的同时,需要判断P是否在计算出该点的两条边的线段之上,
如果P都不在两条边的线段之上,说明此处无相交之处,如果P点被包含在任意一边,说明
两矩形有相交(包含一条边在另一矩形这中的情况)。

泛泛之交 2017-10-11 18 楼

 //框2四个角只要有一个在框1中间 即可判断是否相交
if(y1>Y1&&y1<Y2&&x1<X1&&x1>X3){
return true;
}else if(y2>Y1&&y2<Y2&&x2<X1&&x2>X3){
return true;
}else if(y3>Y1&&y3<Y2&&x3<X1&&x3>X3){
return true;
}else if(y4>Y1&&y4<Y2&&x4<X1&&x4>X3){
return true;
}else{
return false;
}

瑾兮 2017-09-14 17 楼

懒惰的人,不要随便贴上代码, 告诉他思路就可以了

清晨说ぺ晚安 2017-09-12 16 楼

思路:
判断平面矩形相交的话,只要判断是不是一个矩形的4点是否不全在另一矩形内或外即可,其他算法多少有差池;
算法:
1.判断一个点是否在矩形内
isInRect(float x,float y,float rx1,float ry1,float rx2,float ry2){
return(((x>rx1)^(x>rx2))&&((y>ry1)^(y>ry2)))
}
2.判断4个点是否不全在另一矩形内或外(包含不算相交)
isInRect(x1,...)^isInRect(x2,...)^isInRect(x3,...)^isInRect(x4,...)
扩展:
大家可以想想,如果不是矩形而是其他图形呢?圆、三角形、任意凸多边形、凹多边形?

归属感 2017-09-01 15 楼

矩形的边不一定是水平和垂直的
如果只考虑边是水平和垂直的

瑾兮 2017-08-28 14 楼

用java.awt.geom.Rectangle2D的intersects(double x, double y, double w, double h) 方法就可以了吧??

清晨说ぺ晚安 2017-08-21 13 楼

只需要判断其中的一个矩形的一条边与另一个矩形的两条边相交或一个矩形的两条平行边包含另一个矩形的一条边;这样两个矩形就相交了

瑾兮 2017-08-20 12 楼

简单的思路,如果两个四边形相交,则必然有两条边相交,所以只需要判断任意两条边不相交,则两个四边形不相交,以下是代码。但是有一个问题,没有判断一个四边形在另一个四边形里面的情况!

 package com.phoenix;

public class JudgeRectCross {

/**
* @param args
*/
public static void main(String[] args) {
// 定义点
// 第一个四边形
PhoenixPoint f1 = new PhoenixPoint(15, 20);
PhoenixPoint f2 = new PhoenixPoint(20, 30);
PhoenixPoint f3 = new PhoenixPoint(30, 20);
PhoenixPoint f4 = new PhoenixPoint(20, 0);
// 第二个四边形
PhoenixPoint s1 = new PhoenixPoint(20, 5);
PhoenixPoint s2 = new PhoenixPoint(50, 40);
PhoenixPoint s3 = new PhoenixPoint(60, 10);
PhoenixPoint s4 = new PhoenixPoint(45, -5);
// 定义线段
// 第一个四边形的线段
PhoenixLine lf1 = new PhoenixLine(f1, f2);
PhoenixLine lf2 = new PhoenixLine(f2, f3);
PhoenixLine lf3 = new PhoenixLine(f3, f4);
PhoenixLine lf4 = new PhoenixLine(f4, f1);
// 第二个四边形的线段
PhoenixLine ls1 = new PhoenixLine(s1, s2);
PhoenixLine ls2 = new PhoenixLine(s2, s3);
PhoenixLine ls3 = new PhoenixLine(s3, s4);
PhoenixLine ls4 = new PhoenixLine(s4, s1);
// 定义四边形
PhoenixRect quadrangle1 = new PhoenixRect(lf1, lf2, lf3, lf4);
PhoenixRect quadrangle2 = new PhoenixRect(ls1, ls2, ls3, ls4);
//
boolean isCross = false;
if (quadrangle1.l1.isCrossover(quadrangle2.l1)) {
isCross = true;
}
if (quadrangle1.l1.isCrossover(quadrangle2.l2)) {
isCross = true;
}
if (quadrangle1.l1.isCrossover(quadrangle2.l3)) {
isCross = true;
}
if (quadrangle1.l1.isCrossover(quadrangle2.l4)) {
isCross = true;
}
if (quadrangle1.l2.isCrossover(quadrangle2.l1)) {
isCross = true;
}
if (quadrangle1.l2.isCrossover(quadrangle2.l2)) {
isCross = true;
}
if (quadrangle1.l2.isCrossover(quadrangle2.l3)) {
isCross = true;
}
if (quadrangle1.l2.isCrossover(quadrangle2.l4)) {
isCross = true;
}
if (quadrangle1.l3.isCrossover(quadrangle2.l1)) {
isCross = true;
}
if (quadrangle1.l3.isCrossover(quadrangle2.l2)) {
isCross = true;
}
if (quadrangle1.l3.isCrossover(quadrangle2.l3)) {
isCross = true;
}
if (quadrangle1.l3.isCrossover(quadrangle2.l4)) {
isCross = true;
}
if (quadrangle1.l4.isCrossover(quadrangle2.l1)) {
isCross = true;
}
if (quadrangle1.l4.isCrossover(quadrangle2.l2)) {
isCross = true;
}
if (quadrangle1.l4.isCrossover(quadrangle2.l3)) {
isCross = true;
}
if (quadrangle1.l4.isCrossover(quadrangle2.l4)) {
isCross = true;
}
if (isCross) {
System.out.println("两个四边形相交!");
} else {
System.out.println("两个死变相不相交");
}
}

}
package com.phoenix;

public class PhoenixPoint {

public int x;
public int y;

public PhoenixPoint(int x, int y) {
this.x = x;
this.y = y;
}

public boolean equalPoint(PhoenixPoint p) {
if (this.x == p.x && this.y == p.y) {
return true;
} else {
return false;
}
}

}
package com.phoenix;

public class PhoenixLine {

public PhoenixPoint p1;
public PhoenixPoint p2;

public PhoenixLine(PhoenixPoint p_start, PhoenixPoint p_end) {
this.p1 = p_start;
this.p2 = p_end;
}

/**
* 判断本事是否和另一条线交叉
*
* @param l
* @return
*/
public boolean isCrossover(PhoenixLine l) {
// 先求本线段的斜率
double tan1 = (this.p2.y - this.p1.y) / (this.p2.x - this.p1.x);
double tan2 = (l.p2.y - l.p1.y) / (l.p2.x - l.p1.x);
// 如果斜率相等,则两线平行
if (tan1 == tan2) {
return false;
} else {
// 请两条线段的截距
double b1 = this.p2.y - this.p2.x * tan1;
double b2 = l.p2.y - l.p2.x * tan2;
// 两条线重合, 则认为相交
if (b1 == b2) {
return true;
} else {
// 求相交点坐标
double p_x = (b2 - b1) / (tan1 - tan2);
// double p_y = tan1 * p_x + b1;
// 如果坐标点都不在两条线段上,则认为两条线段不相交
// 即满足(p_x - x2)*(p_x -x1) < 0
if (((p_x - this.p1.x) * (p_x - this.p2.x) < 0)
&& ((p_x - l.p1.x) * (p_x - l.p2.x) < 0)) {
return true;
} else {
return false;
}
}
}

}

}
package com.phoenix;

public class PhoenixRect {
public PhoenixLine l1;
public PhoenixLine l2;
public PhoenixLine l3;
public PhoenixLine l4;

public PhoenixRect(PhoenixLine l_1st, PhoenixLine l_2nd, PhoenixLine l_3rd,
PhoenixLine l_4th) {
if (l_1st.p2.equalPoint(l_2nd.p1) && l_2nd.p2.equalPoint(l_3rd.p1)
&& l_3rd.p2.equalPoint(l_4th.p1)
&& l_4th.p2.equalPoint(l_1st.p1)) {
this.l1 = l_1st;
this.l2 = l_2nd;
this.l3 = l_3rd;
this.l4 = l_4th;
} else {
System.out.println("illegal quadrangle!");
}

}
}

想挽留 2017-08-13 11 楼

假设是矩形A和B,满足AB相交的条件是:A有点在B当中,且B有点在A中....

PS做为面试题的话 正正方方的矩形的确没意义
考虑不是正正方方的矩形的话可以改掉pointInRect的写法:可以参考这里http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

虐人心 2017-08-13 10 楼

上面的答案都有点问题……前几天看到的时候我以为是比较简单的问题,应该很快就有正确答案了就没答,结果⊙﹏⊙b汗

实际上两个矩形相交包含了很多种情况,至少有一个顶点在形内的只是其中一种。考虑相反的情况比较容易,即一个矩形什么情况下与另一个矩形不相交(矩形的边与坐标轴平行)?

对一个矩形(x1,y1) - (x2,y2)来说,有上面、下面、左边、右边四个区域,即
x < x1 (左边)
x > x2 (右边)
y < y1 (上边)
y > y2 (下边)

四个区域相互间有重叠。

而另一个矩形如果和这个矩形不相交,那么一定至少处于这四个区域中的一个。

所以条件应该写成:
!((x3 < x1) && (x4 < x1) || (x3 > x2) && (x4 > x2) || (y3 < y1) && (y4 < y1) || (y3 > y2) && (y4 > y2))

当然也可以用布尔代数法则将整个表达式化成没有取反的形式

清晨说ぺ晚安 2017-08-10 9 楼

为什么我觉得判断的条件应该是矩形A的任意顶点在B的范围内,或者矩形B的任意顶点在A的范围内?

甜柠檬 2017-08-06 8 楼

判断A矩形的四条边有没有和B矩形的四条边有没有相交行不行?

泛泛之交 2017-08-03 7 楼

站在题目表示的矩形为平行于坐标轴的,并且给定的两个坐标为对定点这个角度上,大致可以理解为如图所示的情形:

红色点的矩形是原始矩形,蓝色点是用于测试的矩形,斑驳最初的算法如下:
1. 确定两个矩形的左上点坐标以及右下点坐标
2. 根据图片我们可以得出,若果两个矩形有交集,必定会有一个矩形的四个顶点之一会在另外的矩形的范围内。
3. 判断四个顶点是否符合 2 的逻辑,有一个为真即可
4. 若 3 不成立,可能会存在另外的一个矩阵包含前一个的情况,即 反过来 再跑一个 2 和 3。

具体的 java 实现如下,直接保存成 Rect.java 编译运行即可:

public class Rect {
    private float x1;
    private float y1;
    private float x2;
    private float y2;

    public Rect(float x1, float y1, float x2, float y2)
    {
        // [Neo] 确保存储的点为 坐上坐标(x1, y1) 以及 右下坐标(x2, y2)
        float tmp;
        if(x1 > x2)
        {
            tmp = x1;
            x1 = x2;
            x2 = tmp;
        }

        if(y1 > y2)
        {
            tmp = y1;
            y1 = y2;
            y2 = tmp;
        }

        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
    }

    /** 判断点是否在矩形范围内 */
    private boolean isPointInner(float x, float y)
    {
        if(x > x1 && x < x2 && y > y1 && y < y2)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    public float getLeftTopX() {return x1;}
    public float getLeftTopY() {return y1;}
    public float getRightBottomX() {return x2;}
    public float getRightBottomY() {return y2;}

    /** 判断与指定的矩形是否有交集 */
    public boolean isRectIntersect(Rect rect)
    {
        return (isPointInner(rect.getLeftTopX(), rect.getLeftTopY()) ||
                isPointInner(rect.getLeftTopX(), rect.getRightBottomY()) ||
                isPointInner(rect.getRightBottomX(), rect.getLeftTopY()) ||
                isPointInner(rect.getRightBottomX(), rect.getRightBottomY()));
    }

    public static void main(String argv[])
    {
        Rect rect1 = new Rect(1, 1, 3, 3);
        Rect rect2 = new Rect(2, 2, 4, 4);

        System.out.println("result: " + (rect1.isRectIntersect(rect2) || rect2.isRectIntersect(rect1)));
    }
}

发现自己的算法漏掉了一种情况,对代码做了如下的变动:

public class Rect {
    private float x1;
    private float y1;
    private float x2;
    private float y2;

    /**
     * 构造
     * 
     * @param x1
     *            第一个点 x 坐标
     * @param y1
     *            第一个点 y 坐标
     * @param x2
     *            第二个点 x 坐标
     * @param y2
     *            第二个点 y 坐标
     */
    public Rect(float x1, float y1, float x2, float y2) {
        // [Neo] 确保存储的点为 左上坐标(x1, y1) 以及 右下坐标(x2, y2)
        float tmp;
        if (x1 > x2) {
            tmp = x1;
            x1 = x2;
            x2 = tmp;
        }

        if (y1 > y2) {
            tmp = y1;
            y1 = y2;
            y2 = tmp;
        }

        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
    }

    public float getLeftTopX() {
        return x1;
    }

    public float getLeftTopY() {
        return y1;
    }

    public float getRightBottomX() {
        return x2;
    }

    public float getRightBottomY() {
        return y2;
    }

    /**
     * 判断是否与指定的矩形有交集
     * 
     * @param rect
     *            另外的矩形
     * @return 是否
     */
    public boolean isRectIntersect(Rect rect) {
        return ((rect.getLeftTopX() > getLeftTopX() && rect.getRightBottomX() > getLeftTopX()) ||
                (rect.getLeftTopX() < getLeftTopX() && rect.getRightBottomX() < getLeftTopX()) ||
                (rect.getLeftTopY() > getLeftTopY() && rect.getRightBottomY() > getLeftTopY()) ||
                (rect.getLeftTopY() < getLeftTopY() && rect.getRightBottomY() < getLeftTopY()));
    }

    public static void main(String argv[]) {
        Rect rect1 = new Rect(1, 1, 3, 3);
        Rect rect2 = new Rect(2, 2, 4, 4);

        System.out.println("result: " + (rect1.isRectIntersect(rect2)));
    }
}
灵芸 2017-07-18 6 楼

假设a,b矩形

如果他们相交,情况其实很简单
a和b矩形在x轴的投影相交,同时他们在y轴上的投影也相交...即可..

夜无邪 2017-07-14 5 楼

谁能用四个坐标点,表示笛卡尔坐标系中的两个任意矩形?无疑是数学界的一代宗师。。。

夜无邪 2017-07-05 4 楼

两个矩形,又是平行于坐标轴的,假设x1234,y1234 依次增大 ,那么 (x2-x1)+(x4-x3)>x4-x1并且(y2-y1)+(y4-y3)>y4-y1,就说明两矩形相交

灵芸 2017-06-23 3 楼

反证:不相交的两个矩形条件是-任意一个矩形的四个顶点都在另一个矩形四个顶点的一侧!
主要是在确定两个矩形的最小顶点和最大顶点之后,相邻的两边的顶点比较!那么自然需以一个矩形为参考点!判断之前需确定两个都是矩形,即X坐标和Y坐标的值不能相同;之后简单采用绝对平行比较。
看代码:

/// <summary>
/// 矩形
/// </summary>
public class Rectangle
{
private double _x1;
private double _y1;
private double _x2;
private double _y2;

public double X1
{
get { return _x1; }
}
public double Y1
{
get { return _y1; }
}
public double X2
{
get { return _x2; }
}
public double Y2
{
get { return _y2; }
}

public Rectangle(double x1, double y1, double x2, double y2)
{
this._x1 = x1;
this._y1 = y1;
this._x2 = x2;
this._y2 = y2;

this.SortPoint();
}

/// <summary>
/// 确定最小顶点和最大顶点
/// </summary>
private void SortPoint()
{
double temp;
if (_x1 > _x2)
{
temp = _x1;
_x1 = _x2;
_x2 = temp;
}

if (_y1 > _y2)
{
temp = _y1;
_y1 = _y2;
_y2 = temp;
}
}

/// <summary>
/// 判断是否为矩形
/// </summary>
/// <returns></returns>
public bool IsRectangle()
{
if (X1 == X2 || Y1 == Y2)
return false;

return true;
}

/// <summary>
/// 判断是否出现重叠区域
/// </summary>
/// <param name="rect"></param>
/// <returns></returns>
public bool IsOverlap(Rectangle rect)
{
//以执行比较者为参考点,简单采用绝对的四面平行判断
bool left = (rect.X2 < this.X1);
bool right = (rect.X1 > this.X2);
bool top = (rect.Y1 > this.Y2);
bool bottom = (rect.Y2 < this.Y1);

return !(left || right || top || bottom);
}
}

示例:

static void Main(string[] args)
{
Rectangle rect1 = new Rectangle(0, 0, 2, 2);
Rectangle rect2 = new Rectangle(1, 3, 4,5);

if (rect1.IsRectangle() && rect2.IsRectangle())
{

if (rect2.IsOverlap(rect1))
Console.WriteLine("相交");
else
Console.WriteLine("不相交");
}
else
{
Console.WriteLine("其中一个不是矩形,不能比较");
}

Console.ReadKey();
}
}

按几何的理解,矩形的边确实不一定是水平或垂直的,假如给出的两点是矩形的对角线顶点,那么矩形的区域是不确定的!
但是,按图形编程来理解,两点需要确定唯一矩形区域,那么矩形的边必然是水平和垂直的;

清晨说ぺ晚安 2017-06-20 2 楼

(x1,y1),(x2,y2) 表示第一个矩形,(x3,y3),(x4,y4)表示第二个矩形。
以下代码都是我现写的,你测试以下:

class Point
{
public Point(int x = 0, int y = 0 )
{
this.x = x;
this.y = y;
}
public int x;
public int y;
};
class Rect
{
public Point p1;
public Point p2;
};

// 判断一个点 point 是否在 矩形 rect 内,如果是返回 true
boolean PointInRect ( Rect rect, Point point )
{
Point p1 = rect.p1;
Point p2 = rect.p2;

if ( point.x >= p1.x
&& point.x <= p2.x
&& point.y >= p1.y
&& point.y < p2.y )
return true;

return false;
}

boolean intersectRect ( Rect rect1, Rect rect2 )
{
// 判断两个矩形中的点,其中一个矩形的一个点在另一个矩形内,就表示两个矩形相交
// 先算出 rect2 的四个点
Point p1 = rect2.p1; // 左上角

Point p2 = rect2.p2; // 右下角

Point p3 = new Point(); // 左下角
p3.x = rect2.p1.x;
p3.y = rect2.p2.y;

Point p4 = new Point(); // 右上角
p4.x = rect2.p2.x;
p4.y = rect2.p1.y;

if( PointInRect( rect1, p1 ) ||
PointInRect( rect1, p2 ) ||
PointInRect( rect1, p3 ) ||
PointInRect( rect1, p4 ) )
return true;

return false;
}

void func( int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4 )
{
Point p1 = new Point(x1, y1);
Point p2 = new Point(x2, y2);
Rect rect1 = new Rect();
rect1.p1 = p1;
rect1.p2 = p2;

Point p3 = new Point(x3, y3);
Point p4 = new Point(x4, y4);
Rect rect2 = new Rect();
rect2.p1 = p3;
rect2.p2 = p4;

if ( intersectRect ( rect1, rect2 ) || intersectRect(rect2, rect1) )
{
// 相交
}
}

虐人心 2017-06-20 1 楼

可不可以试一下计算面积来判定,两矩形面积之和与坐标组成的面积比较。