欢迎访问
讨论版列表 - 算法集锦 - 主题数: 41 | 文章数: 47 | 管理员: homecox

算法集锦

版面 | 文摘区 | 马克区

文章数: 1 | 分页: << 1 >>
admin
[回复] [修改] [删除] [返回版面] 1  
作者: admin, 讨论版: 算法集锦, 发表时间: 2014-04-24 17:58:10 PST
标题: 判断矩形重叠/相交
关键字: Geometry

方法一:

假定矩形是用一对点表达的(minx, miny) (maxx, maxy),那么两个矩形
    rect1{(minx1, miny1)(maxx1, maxy1)}
    rect2{(minx2, miny2)(maxx2, maxy2)}  
相交的结果一定是个矩形,构成这个相交矩形rect{(minx, miny) (maxx, maxy)}的点对坐标是:  
    minx   =   max(minx1,   minx2)  
    miny   =   max(miny1,   miny2)  
    maxx   =   min(maxx1,   maxx2)  
    maxy   =   min(maxy1,   maxy2)  
   
如果两个矩形不相交,那么计算得到的点对坐标必然满足:  
  ( minx  >  maxx ) 或者 ( miny  >  maxy ) 
   
判定是否相交,以及相交矩形是什么都可以用这个方法一体计算完成。

从这个算法的结果上,我们还可以简单的生成出下面的两个内容:

㈠ 相交矩形:  (minx, miny) (maxx, maxy)

㈡ 面积: 面积的计算可以和判定一起进行
        if ( minx>maxx ) return 0;
        if ( miny>maxy ) return 0;
        return (maxx-minx)*(maxy-miny)

方法二:

两个矩形相交的条件:两个矩形的重心距离在X和Y轴上都小于两个矩形长或宽的一半之和.这样,分两次判断一下就行了.

bool CrossLine(Rect r1,RECT r2)
{
    return 
        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)
}

解法来自[1].

[1] 如何判断两个矩形相交
[2] 判断两矩形是否交叉(包括包含的情况)


--

最后修改: admin on 2014-04-24 18:01:13 PST
※ 来源: homecox.com  [来自: 128.]


Reply

Please log in first.