一级棒(Eachfun)
偷猫的个人主页
一级棒(Eachfun) - 编程园地 - 源码放送 - 如何判断两个矩形是否相交
RSS订阅
如何判断两个矩形是否相交
发表时间:2006-09-16 00:51:00 关键词:C++,VC,MFC,编程,算法,源码

  有朋友在论坛上提问,如何判断两个矩形是否相交,他自己的初步想法是这样的:
  1、一个矩形只有一个角的点在另一个矩形内;
  2、一个矩形a只一条边上的2个顶角在另一个矩形b内(这种情况对于另一个矩形b来说却是4个顶角都在矩形a之外,所以要交换判断)。
  3、一个矩形穿过另一个矩形;
  这位朋友想了这么三种情形之后,觉得把这些情形写成代码过于复杂,这才跑到论坛上来提问。
  首先说明,我本人比较喜欢思考,也喜欢陪喜欢思考的人一起思考。我好久没有在论坛上做什么了,因为一眼看去都是问作业的,一气之下关掉窗口生闷气了。呵呵。

  其实,解决一个问题的方法可以有多种,不同的人应该从不同的方向去考虑。就拿这个“矩形相交”的问题来说,如果从纯几何上考虑,提问者的分析不错,但是从程序算上上看,却未必是好办法。因为这三种情形的细分是从眼睛看的角度出发的,不利于算法的实现。
  有的时候,程序员考虑问题的方向就得跟别人不一样,换一个角度考虑,这个问题将变得简单:
  如果两个矩形相交,则必然存在线条交叉,而能交叉的线条只有横线和竖线,两根横线或两根竖线都不可能交叉。所以,这个问题就转化成寻找是否存在交叉的横线与竖线。
  另外,A线与B线交叉等价于B线与A线交叉,所以,只要写一个函数就足够用了,多调用几次,反正计算机是专门做简单而又烦琐的工作的。

  下面是这个函数:判断一条横线和一条竖线是否交叉。该函数的参数分别是:横线左、横线右,横线Y,竖线上,竖线下,竖线X。

bool CrossLine(left, right, y, top, bottom, x)
{
 //判断一根横线和一根竖线是否交叉
 //横线有三个参数:left, right和y
 //竖线有三个参数:top, bottom和x
 return (top < y) && (bottom > y)
  && (left < x) && (right > x);
}

  下面是判断两个矩形是否相交的函数,把同一个函数多调用几篇就OK了。
bool CrossRect(CRect &r1, CRect &r2)
{
 //判断两个矩形是否相交,
 //从一个矩形中取出一条横线,与另一矩形中的一条竖线判断是否交叉
 return CrossLine(r1.x1, r1.x2, r1.y1, r2.y1, r2.y2, r2.x1)
   || CrossLine(r1.x1, r1.x2, r1.y1, r2.y1, r2.y2, r2.x2)
   || CrossLine(r1.x1, r1.x2, r1.y2, r2.y1, r2.y2, r2.x1)
   || CrossLine(r1.x1, r1.x2, r1.y2, r2.y1, r2.y2, r2.x2)
   || CrossLine(r2.x1, r2.x2, r2.y1, r1.y1, r1.y2, r1.x1)
   || CrossLine(r2.x1, r2.x2, r2.y1, r1.y1, r1.y2, r1.x2)
   || CrossLine(r2.x1, r2.x2, r2.y2, r1.y1, r1.y2, r1.x1)
   || CrossLine(r2.x1, r2.x2, r2.y2, r1.y1, r1.y2, r1.x2);
}

本站特约顾问律师常州东晟律师事务所朱立律师(电话13915029670,QQ646146109)提醒您:
本站文章皆为作者原创,其它媒体(包括但不限于报刊、杂志、网站、电视、电台)未经作者书面许可严禁转载(或部分摘录)!
相关评论
  • 如果2个矩形边是平行于X轴的

    直接R1左上》R2右下&&R1右下《R2左上就行了啊

    person5555 link5555 QQ5555 email5555@q.com 时间:2011-04-12 20:01:00
  • 你这只是矩形水平或垂直的情况
    矩形的边不一定非要平行于x轴或y轴
    这种判断的适用性太小了
    person哈哈 link未填 QQ未填 email未填 时间:2010-07-19 10:32:00
  • 为什么不直接判断(right,top)或者(left,bottom)在矩形内呢?
    person123 link123564 QQ1234 email123456@126.com 时间:2010-05-10 09:30:00
  • 矩阵也可以是倾斜的,没有这么简单,你这只是平行于坐标系的两个矩阵
    personyi link未填 QQ未填 email未填 时间:2008-12-07 21:18:00
  • BOOL IsIntersect(CRect &rect1, CRect &rect2)
    {
    if(rect1.right <= rect2.left) return FALSE;
    if(rect1.left >= rect2.right ) return FALSE;

    if(rect1.bottom <= rect2.top ) return FALSE;
    if(rect1.top >= rect2.bottom ) return FALSE;

    return TRUE;
    }
    personSunDog link未填 QQ9725507 email未填 时间:2007-12-11 14:04:00
  • question朋友提的问题很好,我的程序的确没有考虑到这一情况,
    “包含算不算相交”这是一个逻辑学的问题,
    如果算,就用狗屎的算法,
    如果不算,那我的算法也可行。
    呵呵。
    person偷猫 link未填 QQ33751 email未填 时间:2007-11-19 20:15:00
  • 包含算不算相交?
    personquestion link未填 QQ未填 email未填 时间:2007-11-19 15:39:00
  • 呵呵.
    *2和/2是一样的.本来我用的是右移一位(>=1).
    person狗屎 link未填 QQ未填 email未填 时间:2006-09-20 11:57:00
  • 你的程序至少可以有两点优化:
    1、几何学的语言直转为计算机的语言并不是最好的计算机语句,最明显的就是if中有那么多的“/2”可以全部去掉,不等式两边同时乘以2,与原来是等价的。两边乘以2之后虽然失去了几何学的直观,程序却优化了。
    2、“if(条件) return true; return false”如果让我来写,我一定写成“return 条件;”
    person偷猫 link未填 QQ33751 email未填 时间:2006-09-20 11:45:00
  • 另一个算法:
    两个矩形相交的条件:两个矩形的重心距离在X和Y轴上都小于两个矩形长或宽的一半之和.这样,分两次判断一下就行了.
    bool CrossLine(Rect r1,RECT r2)
    {
    if(abs((r1.x1+r1.x2)/2-(r2.x1+r2.x2)/2)<((r1.x2+r2.x2-r1.x1-r2.x1)/2) && abs((r1.y1+r1.y2)/2-(r2.y1+r2.y2)/2)<((r1.y2+r2.y2-r1.y1-r2.y1)/2))
    return true;
    return false;
    }
    person狗屎 link未填 QQ未填 email未填 时间:2006-09-20 08:02:00
1
发表评论
称呼:
QQ:
邮箱:
链接:
内容:
搜索: 百度搜索 Google搜索
Copyright©2000 - 2011 Eachfun.Com, All Rights Reserved 一级棒网络
备案号忘了带来
一级棒建站系统 http://www.eachfun.com 一级棒版权所有,未经许可不得商用!