`
deng131
  • 浏览: 672756 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

判断矩形相交以及求出相交区域

阅读更多
问题:给定两个矩形A和B,矩形A的左上角坐标为(Xa1,Ya1),右下角坐标为(Xa2,Ya2),矩形B的左上角坐标为(Xb1,Yb1),右下角坐标为(Xb2,Yb2)。
          (1)设计一个算法,确定两个矩形是否相交(即有重叠区域)
          (2)如果两个矩形相交,设计一个算法,求出相交的区域矩形

(1)       对于这个问题,一般的思路就是判断一个矩形的四个顶点是否在另一个矩形的区域内。这个思路最简单,但是效率不高,并且存在错误,错误在哪里,下面分析一下。
            
           如上图,把矩形的相交(区域重叠)分成三种(可能也有其他划分),对于第三种情况,如图中的(3),两个矩形相交,但并不存在一个矩形的顶点在另一个矩形内部。所以那种思路存在一个错误,对于这种情况的相交则检查不出。

           仔细观察上图,想到另一种思路,那就是判断两个矩形的中心坐标的水平和垂直距离,只要这两个值满足某种条件就可以相交。
           矩形A的宽 Wa = Xa2-Xa1 高 Ha = Ya2-Ya1
           矩形B的宽 Wb = Xb2-Xb1 高 Hb = Yb2-Yb1
           矩形A的中心坐标 (Xa3,Ya3) = ( (Xa2+Xa1)/2 ,(Ya2+Ya1)/2 )
           矩形B的中心坐标 (Xb3,Yb3) = ( (Xb2+Xb1)/2 ,(Yb2+Yb1)/2 )
           所以只要同时满足下面两个式子,就可以说明两个矩形相交。
                 1) | Xb3-Xa3 | <= Wa/2 + Wb/2
                 2) | Yb3-Ya3 | <= Ha/2 + Hb/2
           即:
                   | Xb2+Xb1-Xa2-Xa1 | <= Xa2-Xa1 + Xb2-Xb1
                   | Yb2+Yb1-Ya2-Ya1 | <=Y a2-Ya1 + Yb2-Yb1

(2) 对于这个问题,假设两个矩形相交,设相交之后的矩形为C,且矩形C的左上角坐标为(Xc1,Yc1),右下角坐标为(Xc2,Yc2),经过观察上图,很显然可以得到:
            Xc1 = max(Xa1,Xb1)
            Yc1 = max(Ya1,Yb1)
    Xc2 = min(Xa2,Xb2)
            Yc2 = min(Ya2,Yb2)
   这样就求出了矩形的相交区域。
     另外,注意到在不假设矩形相交的前提下,定义(Xc1,Yc1),(Xc2,Yc2),且Xc1,Yc1,Xc2,Yc2的值由上面四个式子得出。这样,可以依据Xc1,Yc1,Xc2,Yc2的值来判断矩形相交。
     Xc1,Yc1,Xc2,Yc2只要同时满足下面两个式子,就可以说明两个矩形相交。
       3) Xc1 <= Xc2
       4) Yc1 <= Yc2
    即:
             max(Xa1,Xb1) <= min(Xa2,Xb2)
             max(Ya1,Yb1) <= min(Ya2,Yb2)

参考:
http://hi.baidu.com/hytjfxk/blog/item/32348c35c6637b8ca61e12c8.html
http://www.cnblogs.com/nicolaszhao/archive/2011/01/24/1943276.html
分享到:
评论

相关推荐

    矩形相交以及求出相交的区域的原理解析

    总结来说,解决矩形相交问题的关键在于判断中心距离和计算相交区域。通过检查中心距离是否小于半尺寸之和,我们可以确定是否存在重叠;然后通过比较边界值,我们能够找到相交部分的矩形。这种算法不仅适用于二维空间...

    易语言矩形相交并生成相交矩形源码

    在这个“易语言矩形相交并生成相交矩形源码”资源中,我们可以深入探讨几个重要的IT知识点,特别是与图形处理和算法相关的部分。 首先,我们要理解矩形相交的基本原理。在计算机图形学中,矩形的相交检测是一个常见...

    求两个矩形求范围交集的快速算法

    两个矩形相交有三种情况: 1. 相离,可以通过判断两个矩形的X最大值,最小值以及Y最大值,最小值的大小比较判定。(空间搜索外包矩形常用算法) 2. 包含与被包含,也是通过两个矩形的X最大值,最小值以及Y最大值,...

    矩形相交并生成相交矩形源码-易语言

    通过阅读和分析源码,我们可以学习到易语言中的API调用方式,矩形相交的判断逻辑,以及如何在图形界面上动态显示结果。对于学习易语言和图形编程的开发者来说,这是一个非常有价值的高级教程示例。同时,这个源码也...

    dhe.rar_生物技术_相交矩形面积

    尽管“生物技术”通常与生物学、遗传学和分子生物学等领域相关,但在这个特定情境下,它可能是指在生物信息学或生物计算中的应用,例如在分析基因组区域或细胞结构时可能会用到矩形相交的概念。 描述提到“判断坐标...

    python射线法判断一个点在图形区域内外

    总的来说,Python射线法判断点在图形区域内外是一种实用的几何算法,适用于地图应用、游戏开发等场景。它能够有效地检测点与复杂形状的关系,而无需构建复杂的图形数据结构。在实际应用中,还可以进一步优化,例如...

    Unity实现图形相交检测

    比如2D格斗游戏中使用的矩形包围盒(AABB),一些动作游戏中常常出现的扇形攻击。 2D的图形相交检测能够满足大部分的需求,且可以拓展成为柱状的3D物体,2D比3D的计算复杂度会低很多,3D的图形检测原理与2D相似,...

    两个矩形求交快速算法

    在计算机科学领域,特别是在图形学、游戏开发以及空间数据处理中,两个矩形求交集的快速算法是一项基础且关键的技术。本文旨在深入探讨这一算法的原理与实现,特别是针对不同矩形相对位置下的交集计算策略。 ### ...

    蓝桥杯 BASIC-18 基础练习 矩形面积交代码

    4. 矩形相交判断:接着,程序判断两个矩形是否有交集。若一个矩形的左边界大于另一个的右边界,或者一个矩形的右边界小于另一个的左边界,或者一个矩形的下边界大于另一个的上边界,或者一个矩形的上边界小于另一个...

    提供的点是否在圆,矩形,多边形内部的方法.txt

    提供的点是否在圆,内部的方法 提供的点是否在矩形内部的方法 提供的点是否在多边形内部的方法

    简易矩形拼板

    新矩形的位置可以通过坐标系统来确定,并检查其对角线是否与已有矩形相交,以避免重叠或间隙。 接着,我们要引入“区间判断”来进一步完善这个方法。区间判断通常指的是在特定的数值范围内进行检查,以确保新矩形的...

    C#绘制相交圆

    这里的`rect`参数是一个`Rectangle`,表示圆弧所在的矩形区域,`startAngle`和`sweepAngle`分别代表圆弧的起始角度和扫过角度。 在实际应用中,可能需要遍历一组圆,检查每对圆之间是否相交,并根据相交情况绘制...

    矩形分割

    例如,你可以使用CRect的IntersectRect()方法来找到两个矩形的交集,UnionRect()来得到它们的并集,SubtractRect()来剪裁一个矩形以排除另一个矩形,或者PtInRect()来判断一个点是否位于矩形内。 GDI+则提供了更...

    快速四边形交集:计算任意两个四边形的相交面积。-matlab开发

    在实际应用中,`quadintersect`函数会自动执行以上步骤,并返回交集区域的顶点坐标以及相交面积。用户只需提供两个四边形的顶点坐标,函数将返回一个结构体,包含交集区域的多边形数据。 MATLAB的`quadintersect`...

    python射线法判断检测点是否位于区域外接矩形内

    ### Python射线法判断检测点是否位于区域外接矩形内 #### 概述 本文主要介绍了Python中如何使用射线法来判断一个检测点是否位于特定区域的外接矩形内部。这个问题在地理信息系统(GIS)、计算机图形学以及游戏开发...

    计算机图形学区域填充

    总的来说,区域填充在计算机图形学中扮演着核心角色,无论是简单的矩形填充还是复杂多边形的内部填充,都需要精确且高效的算法来实现。这些技术广泛应用于图形用户界面、图像处理、游戏开发等领域,确保了我们日常...

    C#-矩形-Rectangle

    2. `Intersect(Rectangle rect)`: 返回与另一个矩形相交的部分,如果无交集则返回一个空的矩形。 3. `Union(Rectangle rect)`: 返回包含两个矩形的最小矩形。 4. `IsEmpty`: 检查矩形是否为空,即其宽高都为零。 5. ...

    python计算两个矩形框重合百分比的实例

    2. 矩形相交判断:通过计算中心点距离和半边长比较来确定两个矩形是否相交。 3. 交集计算:找到两个矩形的共同部分,计算其面积。 4. 重合度计算:根据交集面积和总面积来求取重合百分比。 5. 函数设计与调用:定义...

    计算几何常用算法:点、线、面

    15. **判断两条直线是否相交及求直线交点** - **定义**:判断两条直线是否相交,并计算它们的交点。 - **算法原理**:通过解联立方程组求得交点坐标。 - **应用场景**:适用于图形学中的几何图形分析。 16. **...

Global site tag (gtag.js) - Google Analytics