难？简单？判断两个区域是否有重叠部分

Question

这个问题我感觉不是太难，不过在我思考的同时，还是放上来让大家都讨论一下。看看是不是有高人的算法会非常简单。
--------------------
问题描述：
已知一个较大的矩形区域。任意给定其中的两个矩形区域（当然都属于这个大矩形区域的一部分啦），这两个区域的信息只有四个点的坐标。求一个算法，来判定这两个小区域是否有重叠部分。
为了统一大家讨论，我把这两个任意区域的坐标标一下吧。
rectA(leftupx,leftupy,rightdownx,rightdowny)
rectB(leftupx,leftupy,rightdownx,rightdowny)
//注，只标注了左上坐标和右下坐标，另两点其他也是可知的了。so,begin^ps:不会没解吧？？
判断两个区域是否有重叠部分c++算法

Answer 1

if(rectA.right<rectB.left)
return false;if(rectA.bottom<rectB.top)
return false;if(rectA.left>rectB.right)
return false;if(rectA.top>rectB.bottom)
return false;return true;写的比较烂

Answer 2

你错的bool IsOverlap(CPoint firstLeft,CPoint firstright,CPoint secondLeft,CPoint secondRight)
{
// 第二个点左横坐标有重合继续判断纵坐标是否有重合
if (secondLeft.x > firstLeft.x && secondLeft.x < firstright.x)
{
if (secondLeft.y > firstLeft.y && secondLeft.y < firstright.y)
{
return true;
} if (secondRight.y > firstLeft.y && secondRight.y < firstright.y)
{
return true;
}
} // 第二个点右横坐标有重合继续判断纵坐标是否有重合
if (secondRight.x > firstLeft.x && secondRight.x < firstright.x)
{
if (secondLeft.y > firstLeft.y && secondLeft.y < firstright.y)
{
return true;
} if (secondRight.y > firstLeft.y && secondRight.y < firstright.y)
{
return true;
}
} // 否则不重合 return false;
}

Answer 3

判断其中一个矩形的四个点是否在令外一个矩形内ptinrect * 4次

Answer 4

以一个矩形为参照，另外一个矩形的4个点，每个点使用PtInRect来判断

Answer 5

你错的bool IsOverlap(CPoint firstLeft,CPoint firstright,CPoint secondLeft,CPoint secondRight)
{
// 第二个点左横坐标有重合继续判断纵坐标是否有重合
if (secondLeft.x > firstLeft.x && secondLeft.x < firstright.x)
{
if (secondLeft.y > firstLeft.y && secondLeft.y < firstright.y)
{
return true;
} if (secondRight.y > firstLeft.y && secondRight.y < firstright.y)
{
return true;
}
} // 第二个点右横坐标有重合继续判断纵坐标是否有重合
if (secondRight.x > firstLeft.x && secondRight.x < firstright.x)
{
if (secondLeft.y > firstLeft.y && secondLeft.y < firstright.y)
{
return true;
} if (secondRight.y > firstLeft.y && secondRight.y < firstright.y)
{
return true;
}
} // 否则不重合 return false;
}你的这个我没看太懂，不过也是感觉 不可以。好像 也不能准确判断 6楼图A情况吧

Answer 6

嗯。发帖前，我也就在想和你这个类似的方法了，不过那时还没想通。我按这个方法做一下，稍后给大家结果。后一个矩形包含前一个矩形的情况没考虑到 最后再加个// 如果后一矩形包含前一矩形
if (secondLeft.x <= firstLeft.x && secondRight.x >= firstright.x)
{
return true；
}

Answer 7

问题：给定两个矩形A和B，矩形A的左上角坐标为（Xa1,Ya1），右下角坐标为（Xa2,Ya2），矩形B的左上角坐标为（Xb1,Yb1），右下角坐标为（Xb2,Yb2）。
（1）设计一个算法，确定两个矩形是否相交（即有重叠区域）
（2）如果两个矩形相交，设计一个算法，求出相交的区域矩形....只要同时满足下面两个式子，就可以说明两个矩形相交。
max(Xa1,Xb1) <= min(Xa2,Xb2)
max(Ya1,Yb1) <= min(Ya2,Yb2)matlab中的rectint函数用的也是这个思想.
update: matlab函数已经写好,见http://goo.gl/ofTY

Answer 8

嗯。发帖前，我也就在想和你这个类似的方法了，不过那时还没想通。我按这个方法做一下，稍后给大家结果。后一个矩形包含前一个矩形的情况没考虑到 最后再加个// 如果后一矩形包含前一矩形
if (secondLeft.x <= firstLeft.x && secondRight.x >= firstright.x)
{
return true；
}
我仔细看了一下，你的方法也还是不严谨的。6楼的图A情况，你的这个判断是错误的。
y方向上的判断是会出错的。根据图来看，肯定有重叠部分（这真是个废话，呵）。但是你下边的两个if，是不会返回 true的。
if (secondLeft.y > firstLeft.y && secondLeft.y < firstright.y)
{
return true;
} if (secondRight.y > firstLeft.y && secondRight.y < firstright.y)
{
return true;
}

Answer 9

嗯。发帖前，我也就在想和你这个类似的方法了，不过那时还没想通。我按这个方法做一下，稍后给大家结果。后一个矩形包含前一个矩形的情况没考虑到 最后再加个// 如果后一矩形包含前一矩形
if (secondLeft.x <= firstLeft.x && secondRight.x >= firstright.x)
{
return true；
}
我仔细看了一下，你的方法也还是不严谨的。6楼的图A情况，你的这个判断是错误的。
y方向上的判断是会出错的。根据图来看，肯定有重叠部分（这真是个废话，呵）。但是你下边的两个if，是不会返回 true的。
if (secondLeft.y > firstLeft.y && secondLeft.y < firstright.y)
{
return true;
} if (secondRight.y > firstLeft.y && secondRight.y < firstright.y)
{
return true;
}
我 是在我的程序上试了的，两个区域十字相交是判断错误的。

Answer 10

能否再细说一下这两行的具体含义？
max(Xa1,Xb1) <= min(Xa2,Xb2)
max(Ya1,Yb1) <= min(Ya2,Yb2)

Answer 11

可以试试 CRgn::CombineRgn(pRgn1, pRgn2, RGN_AND)

Answer 12

能否再细说一下这两行的具体含义？
max(Xa1,Xb1) <= min(Xa2,Xb2)
max(Ya1,Yb1) <= min(Ya2,Yb2)20楼正解。首先要明确一点，据题意，每个矩形只知道左上角和右下角的点，所以题目暗示（或者说默认）矩形的边与坐标轴平行，否则仅知两个顶点无法确定一个唯一的矩形。矩形A内的任意点(x,y)，包括四边上的点，应满足如下不等式组
Xa1 ≤ x ≤ Xa2   ①
Ya1 ≤ y ≤ Ya2   ②同理，B内的点满足
Xb1 ≤ x ≤ Xb2   ③
Yb1 ≤ y ≤ Yb2   ④若A、B有重合，则必定存在点同时满足①②③④，所以有
max(Xa1,Xb1) <= min(Xa2,Xb2)
max(Ya1,Yb1) <= min(Ya2,Yb2)

Answer 13

嗯。发帖前，我也就在想和你这个类似的方法了，不过那时还没想通。我按这个方法做一下，稍后给大家结果。后一个矩形包含前一个矩形的情况没考虑到 最后再加个// 如果后一矩形包含前一矩形
if (secondLeft.x <= firstLeft.x && secondRight.x >= firstright.x)
{
return true；
}
我仔细看了一下，你的方法也还是不严谨的。6楼的图A情况，你的这个判断是错误的。
y方向上的判断是会出错的。根据图来看，肯定有重叠部分（这真是个废话，呵）。但是你下边的两个if，是不会返回 true的。
if (secondLeft.y > firstLeft.y && secondLeft.y < firstright.y)
{
return true;
} if (secondRight.y > firstLeft.y && secondRight.y < firstright.y)
{
return true;
}两个if你的图A任意一个都返回true 怎么不返回？ 左上角的纵坐标不是在 前一个矩形的纵坐标范围内？ 右下角的纵坐标不是在前一个矩形的纵坐标范围内？

Answer 14

bool IntersectsWith(const RECT R1, const RECT R2)
{
return !( (R1.right < R2.left) |
  (R1.bottom < R2.top) |
  (R2.right < R1.left) |
  (R2.bottom < R1.top) );
}

Answer 15

rectA.left <= rectB.right&&
rectB.left<=rectA.right &&
rectA.top <= rectB.bottom&&
rectB.top <= rectA.bottom

Answer 16

嗯。发帖前，我也就在想和你这个类似的方法了，不过那时还没想通。我按这个方法做一下，稍后给大家结果。后一个矩形包含前一个矩形的情况没考虑到 最后再加个// 如果后一矩形包含前一矩形
if (secondLeft.x <= firstLeft.x && secondRight.x >= firstright.x)
{
return true；
}
我仔细看了一下，你的方法也还是不严谨的。6楼的图A情况，你的这个判断是错误的。
y方向上的判断是会出错的。根据图来看，肯定有重叠部分（这真是个废话，呵）。但是你下边的两个if，是不会返回 true的。
if (secondLeft.y > firstLeft.y && secondLeft.y < firstright.y)
{
return true;
} if (secondRight.y > firstLeft.y && secondRight.y < firstright.y)
{
return true;
}两个if你的图A任意一个都返回true 怎么不返回？ 左上角的纵坐标不是在 前一个矩形的纵坐标范围内？ 右下角的纵坐标不是在前一个矩形的纵坐标范围内？
---------------------------------
左上角的纵坐标不是在 前一个矩形的纵坐标范围内？ 右下角的纵坐标不是在前一个矩形的纵坐标范围内？
----------------------------------
这个的回答是：真不在。b点的纵坐标显然不在c d 两点的纵坐标内啊。

Answer 17

能否再细说一下这两行的具体含义？
max(Xa1,Xb1) <= min(Xa2,Xb2)
max(Ya1,Yb1) <= min(Ya2,Yb2)20楼正解。首先要明确一点，据题意，每个矩形只知道左上角和右下角的点，所以题目暗示（或者说默认）矩形的边与坐标轴平行，否则仅知两个顶点无法确定一个唯一的矩形。矩形A内的任意点(x,y)，包括四边上的点，应满足如下不等式组
Xa1 ≤ x ≤ Xa2   ①
Ya1 ≤ y ≤ Ya2   ②同理，B内的点满足
Xb1 ≤ x ≤ Xb2   ③
Yb1 ≤ y ≤ Yb2   ④若A、B有重合，则必定存在点同时满足①②③④，所以有
max(Xa1,Xb1) <= min(Xa2,Xb2)
max(Ya1,Yb1) <= min(Ya2,Yb2)这个方法其实也就是遍历点的意思吧。运算量会大。
不过，好像别的方法不太好（我感觉）。
再说一下，既然你们说这个方法是 matlab 上推荐的，那我想，也应该是没有别的简单的，别的准确点的方法了吧

Answer 18

嗯。发帖前，我也就在想和你这个类似的方法了，不过那时还没想通。我按这个方法做一下，稍后给大家结果。后一个矩形包含前一个矩形的情况没考虑到 最后再加个// 如果后一矩形包含前一矩形
if (secondLeft.x <= firstLeft.x && secondRight.x >= firstright.x)
{
return true；
}
我仔细看了一下，你的方法也还是不严谨的。6楼的图A情况，你的这个判断是错误的。
y方向上的判断是会出错的。根据图来看，肯定有重叠部分（这真是个废话，呵）。但是你下边的两个if，是不会返回 true的。
if (secondLeft.y > firstLeft.y && secondLeft.y < firstright.y)
{
return true;
} if (secondRight.y > firstLeft.y && secondRight.y < firstright.y)
{
return true;
}两个if你的图A任意一个都返回true 怎么不返回？ 左上角的纵坐标不是在 前一个矩形的纵坐标范围内？ 右下角的纵坐标不是在前一个矩形的纵坐标范围内？
---------------------------------
左上角的纵坐标不是在 前一个矩形的纵坐标范围内？ 右下角的纵坐标不是在前一个矩形的纵坐标范围内？
----------------------------------
这个的回答是：真不在。b点的纵坐标显然不在c d 两点的纵坐标内啊。
请问你这传的是第一个矩形的左上角和右下角？   第二个矩形的左上角和右下角？c、d点能确定一个矩形？  a、b点能确定一个矩形？？？？

Answer 19

Rectangle rectA = new Rectangle(100, 100, 10, 10);
Rectangle rectB = new Rectangle(111, 111, 10, 10);
MessageBox.Show(Rectangle.Intersect(rectA, rectB).IsEmpty.ToString());路过、、、、

Answer 20

大家都知道圆是否相交怎么判断吧？中心距离和与半径和作比较而已
矩形相交其实也是一样
只是拆分成横纵2种情况而已，也是判断中心距离
横：包含（0<横坐标差绝对值<较大半宽） 相离（横坐标差绝对值>半宽和） 相交（横坐标差绝对值>较大半宽<半宽和） 相切（横坐标差绝对值==半宽和） 重合（为零）
纵：包含 相离 相交 相切 重合横纵有一个相离就相离 ，都相切的时候同一顶点 1相切1重合则相叠（上下叠或左右） 1相切1相交（划离）等等  都重合的时候重合 考虑包含有正负（都正都负的时候内含，否则正交）  所以实际具体几种我知 总的规模是5*5 = 25只看是否有相交（有同点也算的话）
那就排除相离就行了  情况就少了
或者只看相交部分面积为零（同点同线也算相离的话），那可以去掉相切那种情况，也只需判断相离
碰撞引擎

Answer 21

bool IsOverlap(CPoint firstLeft,CPoint firstright,CPoint secondLeft,CPoint secondRight)
{
// 第二个点左横坐标有重合继续判断纵坐标是否有重合
if (secondLeft.x > firstLeft.x && secondLeft.x < firstright.x)
{
if (secondLeft.y > firstLeft.y && secondLeft.y < firstright.y)
{
return true;
} if (secondRight.y > firstLeft.y && secondRight.y < firstright.y)
{
return true;
}
} // 第二个点右横坐标有重合继续判断纵坐标是否有重合
if (secondRight.x > firstLeft.x && secondRight.x < firstright.x)
{
if (secondLeft.y > firstLeft.y && secondLeft.y < firstright.y)
{
return true;
} if (secondRight.y > firstLeft.y && secondRight.y < firstright.y)
{
return true;
}
} // 否则第二个点横坐标包含第一个点横坐标，只要判断纵坐标是否交叉
if (secondLeft.y > firstLeft.y && secondLeft.y < firstright.y)
{
return true;
} if (secondRight.y > firstLeft.y && secondRight.y < firstright.y)
{
return true;
} // 否则不重合 return false;
}用上图的坐标  直接用这个函数测试　随便那个矩形作为第一个矩形．．．

Answer 22

首先感谢一下你对这个问题的积极回复哈。
好，我们就按#38楼，你的图来说，cd矩形为第一个矩形（first),ab为第二个矩形。
先看你的第一个大if
------------------------------
// 第二个点左横坐标有重合继续判断纵坐标是否有重合
if (secondLeft.x > firstLeft.x && secondLeft.x < firstright.x)
{
//符合条件，到这儿
if (secondLeft.y > firstLeft.y && secondLeft.y < firstright.y)//按38楼图，括号内为假
{
//38楼图的情况，有相交，可是这个会判断为假。if根本进不来啊。
//用数据说就是b点的纵坐标不在cd点的纵坐标范围内啊
//这样的话是不是就会判断错误了？？
return true;
}if (secondRight.y > firstLeft.y && secondRight.y < firstright.y)
{
return true;
}
}
-------------------------------------------------------
也不知道 是不是我理解你的程序有方向性错误……不知道我33楼的说法，你同不同意。

Answer 23

// 否则第二个点横坐标包含第一个点横坐标，只要判断纵坐标是否交叉
if (secondLeft.y > firstLeft.y && secondLeft.y < firstright.y)
{
return true;
}if (secondRight.y > firstLeft.y && secondRight.y < firstright.y)
{
return true;
}

Answer 24

BOOL CheckOverlap(POINT *ptArray1, const int ptNum1, //区域1坐标点 坐标点数量
                      POINT *ptArray2, const int ptNum2) //区域2坐标点 坐标点数量
{
  CRgn rgn1, rgn2;
  if(rgn1.CreatePolygonRgn(ptArray1, ptNum1, WINDING)
    && rgn2.CreatePolygonRgn(ptArray2, ptNum2, WINDING))
  {
    CRgn rgnOvlap; rgnOvlap.CreateRectRgn(0,0,0,0);
    
    int iRet = rgnOvlap.CombineRgn(&rgn1, &rgn2, RGN_AND);
    if(iRet == COMPLEXREGION || iRet == SIMPLEREGION)
    {
      return TRUE;
    }
  }
  
  return FALSE;
}//测试代码
  {
    POINT pt1[] = {{0,2},{3,2},{3,1},{0,1}};
    POINT pt2[] = {{1,3},{2,3},{2,0},{0,0}};
    VERIFY(CheckOverlap(pt1, 4, pt2, 4));
  }

Answer 25

首先感谢一下你对这个问题的积极回复哈。
好，我们就按#38楼，你的图来说，cd矩形为第一个矩形（first),ab为第二个矩形。
先看你的第一个大if
------------------------------
// 第二个点左横坐标有重合继续判断纵坐标是否有重合
if (secondLeft.x > firstLeft.x && secondLeft.x < firstright.x)
{
//符合条件，到这儿
if (secondLeft.y > firstLeft.y && secondLeft.y < firstright.y)//按38楼图，括号内为假
{
//38楼图的情况，有相交，可是这个会判断为假。if根本进不来啊。
//用数据说就是b点的纵坐标不在cd点的纵坐标范围内啊
//这样的话是不是就会判断错误了？？
return true;
}if (secondRight.y > firstLeft.y && secondRight.y < firstright.y)
{
return true;
}
}
-------------------------------------------------------
也不知道 是不是我理解你的程序有方向性错误……不知道我33楼的说法，你同不同意。括号内为假就返回false  就不进后面所有的if了？

Answer 26

bool IsLineOverlap(int fL,int fR,int sL,int sR)
{
// 第一个点最小坐标大于第二个点最大坐标或者第一个点最大坐标小于第二个点最小坐标表示坐标无交叉
return !(fL > sR || fR < sL);
}bool IsOverlap(CPoint firstLeft,CPoint firstRight,CPoint secondLeft,CPoint secondRight)
{
if (IsLineOverlap(firstLeft.x,firstRight.x,secondLeft.x,secondRight.x))
{
// 表示两个矩形横坐标有交叉
if (IsLineOverlap(firstLeft.y,firstRight.y,secondLeft.y,secondRight.y))
{
// 表示两个矩形纵坐标也有交叉
return true;
}
} return false;
}
终极版...

Answer 27

如果返回False,则计算：矩形A的每条边在与矩形B的每条边是否有交点，如果有一个，则返回True。

Answer 28

如果返回False,则计算：矩形A的每条边在与矩形B的每条边是否有交点，如果有一个，则返回True。和我思考的结果一样,但是有个地方要说清楚,矩形A和矩形B,要同时确认A的4点在B外,且B的4点在A外,之后再作线段相交判断,而线段相交的简单方法是:A和B各取一条对角线看是否相交即可.同时本方法适用于任意2个4边形的相交判断.不知是否还有简便方法.

Answer 29

能否再细说一下这两行的具体含义？
max(Xa1,Xb1) <= min(Xa2,Xb2)
max(Ya1,Yb1) <= min(Ya2,Yb2)20楼正解。首先要明确一点，据题意，每个矩形只知道左上角和右下角的点，所以题目暗示（或者说默认）矩形的边与坐标轴平行，否则仅知两个顶点无法确定一个唯一的矩形。矩形A内的任意点(x,y)，包括四边上的点，应满足如下不等式组
Xa1 ≤ x ≤ Xa2   ①
Ya1 ≤ y ≤ Ya2   ②同理，B内的点满足
Xb1 ≤ x ≤ Xb2   ③
Yb1 ≤ y ≤ Yb2   ④若A、B有重合，则必定存在点同时满足①②③④，所以有
max(Xa1,Xb1) <= min(Xa2,Xb2)
max(Ya1,Yb1) <= min(Ya2,Yb2)这个方法其实也就是遍历点的意思吧。运算量会大。
不过，好像别的方法不太好（我感觉）。
再说一下，既然你们说这个方法是 matlab 上推荐的，那我想，也应该是没有别的简单的，别的准确点的方法了吧根本不需要遍历啊，就最后的那个不等式组成立就行了。

Answer 30

将两个矩形分别投影到XY轴，就会得到4条线，分别是XA,XB，YA，YB。
分别判断同轴的两条线（XA与AB,YA与YB）是否有交集。
如果两个轴上都有交集，则返回 True，否则返回 False

Answer 31

和max(Xa1,Xb1) <= min(Xa2,Xb2)  max(Ya1,Yb1) <= min(Ya2,Yb2)思想差不多
如果小矩形和大矩形各边分别平行，那不需要遍历点，只要2个矩形4点坐标满足上面俩条件就可以了

Answer 32

和max(Xa1,Xb1) <= min(Xa2,Xb2)  max(Ya1,Yb1) <= min(Ya2,Yb2)思想差不多
如果小矩形和大矩形各边分别平行，那不需要遍历点，只要2个矩形4点坐标满足上面俩条件就可以了
主矩正交，另一个可以随便