判断两个矩形是否重叠

短命女 2022-05-20 02:10 268阅读 0赞

# 判断两个矩形是否重叠 #

关于如何判断两个矩形重叠，这是我在实际项目开发当中曾经遇到过的问题：“判断图像中检测到的两个人脸框矩形是否有重叠部分，并计算重叠大小，从而确认是否为同一个人脸”。后来，在浏览博客时，也发现也有人将这个问题当做面试题目，并进行过讨论，但是，列出的代码过于繁杂，不敢恭维。所以，写下这篇博文，并贴出代码，供大家参考。

## 前提 ##

1.  两个矩形的边均与x轴或y轴平行，即轴对齐的矩形
2.  将第一个矩形记做A，第二个矩形记做B
3.  判断矩阵A与矩阵B是否重叠（边沿重叠也认为是重叠）

## 讨论 ##

1.  第一种方案，正向思维   
    按照一般的思路，先列举出所有的矩形重叠的情况，然后，判断是否是其中一种，如图所示，共有四种重叠情况，我们使用紫色代表矩形A，红色代表矩形B，并分别用`p1`,`p2`,`p3`,`p4`代表对应的左上角与右下角。如果依次判断，过于复杂，而且容易出错，这里我们不再进行代码实现。   
    ![两矩形的重叠情况][20160108150840835]
2.  第二种方案，反向思维   
    反向思考，我们不妨先解决出“不重叠”的情况，如图，我们画出了一个并怎么漂亮的图，看起来十分复杂，但是，实际上，相比第一种方案，更易表示。即B矩阵，可能在A的左侧、右侧、上侧、下侧。如果用公式表示，即   
    (p2.y≤p3.y)∨(p1.y≥p4.y)∨(p2.x≤p3.x)∨(p1.x≥p4.xp2.y≤p3.y)∨(p1.y≥p4.y)∨(p2.x≤p3.x)∨(p1.x≥p4.x)   
    则，两个矩阵重叠时，公式为   
    ¬\[(p2.y≤p3.y)∨(p1.y≥p4.y)∨(p2.x≤p3.x)∨(p1.x≥p4.x)\]¬\[(p2.y≤p3.y)∨(p1.y≥p4.y)∨(p2.x≤p3.x)∨(p1.x≥p4.x)\]   
    根据[德·摩根定律][Link 1]可转换为   
    (p2.y>p3.y)∧(p1.y<p4.y)∧(p2.x>p3.x)∧(p1.x<p4.x)(p2.y>p3.y)∧(p1.y<p4.y)∧(p2.x>p3.x)∧(p1.x<p4.x)   
    ![两矩形不重叠情况][20160108152711050]

## 解决方案 ##

根据上述第二种情况分析，我们可以进行代码的实现，如下

#include <iostream>
    using namespace std;
    
    //矩阵位置坐标
    typedef struct Rect {
        Rect(int x, int y, int width, int height)
            : x(x), y(y), width(width), height(height)
        {}
        int x;          //矩形左上角x坐标
        int y;          //矩形左上角y坐标
        int width;      //矩形宽度
        int height;     //矩形高度
    } Rect;
    
    
    /** * @brief 判断两个轴对齐的矩形是否重叠 * @param rc1 第一个矩阵的位置 * @param rc2 第二个矩阵的位置 * @return 两个矩阵是否重叠（边沿重叠，也认为是重叠） */
    bool isOverlap(const Rect &rc1, const Rect &rc2)
    {
        if (rc1.x + rc1.width  > rc2.x &&
            rc2.x + rc2.width  > rc1.x &&
            rc1.y + rc1.height > rc2.y &&
            rc2.y + rc2.height > rc1.y
           )
            return true;
        else
            return false;
    }
    
    
    int main()
    {
        Rect rc1(0,0,10,10), rc2(11,11,2,2);
        if (isOverlap(rc1, rc2))
            cout << "Rectangles Overlap";
        else
            cout << "Rectangles Don't Overlap";
        return 0;
    }

*  1
 *  2
 *  3
 *  4
 *  5
 *  6
 *  7
 *  8
 *  9
 *  10
 *  11
 *  12
 *  13
 *  14
 *  15
 *  16
 *  17
 *  18
 *  19
 *  20
 *  21
 *  22
 *  23
 *  24
 *  25
 *  26
 *  27
 *  28
 *  29
 *  30
 *  31
 *  32
 *  33
 *  34
 *  35
 *  36
 *  37
 *  38
 *  39
 *  40
 *  41
 *  42
 *  43

## 附录 ##

此处，本文也提供一个计算该两个矩阵重叠面积比例的函数实现，虽然所用公式看起来不甚相同，但是，可以很容易推出来，实际上是一样的。（注意，此代码中使用了OpenCV内部结构）

/** * @brief 计算两个矩形的相交面积及组合面积，同时计算相交面积占组合面积的比例 * @param 第一个矩形的位置 * @param 第二个矩形的位置 * @param 两个矩阵相交的面积大小 * @param 两个矩阵组合的面积大小 * @return 两个矩阵相交面积占组合面积的比例,即重合比例。如果组合面积为0，则返回0 */
    float computRectJoinUnion(const CvRect &rc1, const CvRect &rc2, float& AJoin, float& AUnion)
    {
        CvPoint p1, p2;                 //p1为相交位置的左上角坐标，p2为相交位置的右下角坐标
        p1.x = std::max(rc1.x, rc2.x);
        p1.y = std::max(rc1.y, rc2.y);
    
        p2.x = std::min(rc1.x +rc1.width, rc2.x +rc2.width);
        p2.y = std::min(rc1.y +rc1.height, rc2.y +rc2.height);
    
        AJoin = 0;
        if( p2.x > p1.x && p2.y > p1.y )            //判断是否相交
        {
            AJoin = (p2.x - p1.x)*(p2.y - p1.y);    //如果先交，求出相交面积
        }
        float A1 = rc1.width * rc1.height;
        float A2 = rc2.width * rc2.height;
        AUnion = (A1 + A2 - AJoin);                 //两者组合的面积
    
        if( AUnion > 0 )
            return (AJoin/AUnion);                  //相交面积与组合面积的比例
        else
            return 0;
    }

[20160108150840835]: /images/20220520/a3e7765677414eb6b61c556d9a504e2d.png
[Link 1]: http://baike.baidu.com/link?url=EslPA4hUANkWeMpbxs7tazzU6AoKShdjNd2d1j3z9p60F0g8hTKU4qHMLPGIJQSYzBT6CJNZUNnGOukVtkXXs--1-fDBALmu9zVVZF1lG1RfopBsvFE-ulUFJUPRDCxFzFQ1pH37Kf7_4a1hGgbI0U8RALarcSZQDMDfCruFMTUhJdt1FccaK2bAivmUWHiN
[20160108152711050]: /images/20220520/b7eb4f4cfc94425e91c0e25547935a99.png