由检测2个矩形框的重叠程度，来理理解决问题的思路

我报名参加金石计划1期挑战——瓜分10万奖池，这是我的第1篇文章，点击查看活动详情

---

大家好，我是TF男孩，一位编程表演艺术家。下面我给大家表演一段编程：用python来检测两个矩形框的重叠程度。

一、开场：应用场景

首先，什么是矩形框的重叠程度？

两个矩形框的重叠关系存在很多种可能性：横向有交集、纵向有交集、完全无交集、部分或全部重叠。

为什么要检测重叠程度？这其实是我在工作中遇到的一个问题。

1.1 散点值只能获坐标，规整行无法取蹊径

我刚刚完成了这么一个功能，就是把纸质试卷进行电子化，主要操作的，就是下面这样的试卷。

我把它变成html版本的。

还要能生成word文件并下载，对于里面的公式、表格也可以进行正常编辑。

这里涉及到目标检测、OCR识别、word写入等技术。不过，今天的重点是：识别后的数据结构是散点式的，识别结果是由字符块组成的。

[
  {
    "y2": 158,
    "x2": 86,
    "word": "有",
    "x1": 68,
    "y1": 144
  },
  {
    "h": 158,
    "w": 97,
    "word": "效",
    "x1": 73,
    "y1": 144
  },
  {
    "y2": 158,
    "x2": 101,
    "word": "值",
    "x1": 85,
    "y1": 144
  },
  {
    "y2": 158,
    "x2": 117,
    "word": "是",
    "x1": 97,
    "y1": 144
  },
  {
    "y2": 169,
    "x2": 164,
    "word": "（公式）\\frac { \\sqrt 2 } { 2 } N e _ { 0 }",
    "x1": 118,
    "y1": 133
  }
]

你需要根据坐标，将它们排列成如下的结构：

1.2 算重叠或许得排位，计包含定能获从属

因为每个字都是一个小矩形，我们只有它们的坐标数据。于是，判断两个矩形的重叠情况就很有必要了。

如下图所示，如果文本1的矩形区域和公式1的矩形区域，在横向上有一定比例的重叠，那我们可以认为，它们是处于同一行。 如果文本2的区域完全包含（重叠率100%）于表格1的区域中，那么我们可以认为文本2属于表格1内的内容。同样，文本2和文本3在纵向的重叠率，可以作为它俩是否位于同一列的指标。

二、表演：解决方案

我们要解决的这个问题，很有意思，我感觉它上升到了艺术的高度，非常唯美（你可能觉得我有些癫狂，但我真的就是这么认为的）。

之所以说它有艺术，就在于解决方案太多了，美不胜收，众里寻她。

2.1 用穷举分门别类，使判断千丝万缕

很简单啊，分情况做判断就行。

如果是完全包含，也就是这个情况：

以python代码举例：

if b_x1 > a_x1 and b_x2 < a_x2 and b_y1 > a_y1 and b_y2 < a_y2:
    print("重合率100%")

如果是完全无重叠，那就是这样：

if b_x1 > a_x2 and b_y1 > a_y2: # 右下角：b左超a右，b上超a下，则无交集
    print("重合率0%")

这是相对于右下角的情况。除此之外，还要考虑其他3个方位的判断。而且还要考虑两个目标互换位置的情况（谁是a框，谁是b框）。

上面只是判断重叠率为100%和重叠率为0%这两种极端情况，这还是比较简单的。但是，我们已然发现有了很多的if判断。

你可以试着想一下，如果要计算具体的重叠率，那需要怎么写？

谁在上来谁在下，谁在左来谁在右，下面的下多少，右面的又右多少……不知怎么地，我忽然想起了刘三姐对山歌……

反正我不敢采用分情况判断的写法，我害怕这样写，我和程序都会崩溃掉。

2.2 图形、数组两方斗，几何、代数一家亲

我们一直都在考虑空间的问题，谁左谁右，谁偏谁多少距离，这其实是几何问题。

当几何问题解决繁琐时，我们可以考虑用袋鼠……带数……对！就是你纠正的那个词语。

代数里面有个集合，集合和几何同音，可以试试从这个点切入。

我们拿矩形框在X轴方向的重叠来看，所谓重叠，其实就是有多少个相同元素。

矩形A和矩形B在X轴重叠情况，其实就是集合A和集合B，相同元素个数的占比。

我们看到，矩形A和矩形B是有相同元素的，集合C同前两者没有相同元素，即没有任何重叠。

这么一转，豁然开朗。

我们来计算一下X方向的重叠情况：

# a_x1, a_y1, a_x2, a_y2 = 矩形a的(左上角x, 左上角y, 右下角x, 右下角y)
# b_x1, b_y1, b_x2, b_y2 = 矩形b的(左上角x, 左上角y, 右下角x, 右下角y)
ax = [i for i in range(a_x1,a_x2+1)] # 生成a的元素集合
bx = [i for i in range(b_x1,b_x2+1)] # 生成b的元素集合
x_sam_len = len(set(ax) & set(bx)) # 求相同元素个数
x_len = min(a_x2-a_x1, b_x2-b_x1)+1 # 获取哪个集合更短
x_rate = x_sam_len/x_len # 相同元素个数/更短集合 = 重合率

注释很清晰，已经比代码多了，我也不敢再多嘴了。

看，这里面没有一个if语句，也实现了重叠情况的判断和计算。

总体的判断，下面一个方法就可以实现，可以直接复制来用，不用导入任何包：

# 两个矩形区域重叠比率，输入a[x1,y1,x2,y2] b[x1,y1,x2,y2],输出横纵方向
def get_same_rate(a,b):
    a_x1,a_y1,a_x2,a_y2 = a
    b_x1,b_y1,b_x2,b_y2 = b
    # X方向
    ax = [i for i in range(a_x1,a_x2+1)]
    bx = [i for i in range(b_x1,b_x2+1)]
    x_sam_len = len(set(ax) & set(bx))
    x_len = min(a_x2-a_x1, b_x2-b_x1)+1
    x_rate = x_sam_len/x_len
    # Y方向
    ay = [i for i in range(a_y1,a_y2+1)]
    by = [i for i in range(b_y1,b_y2+1)]
    y_sam_len = len(set(ay) & set(by))
    y_len = min(a_y2-a_y1, b_y2-b_y1)+1
    y_rate = y_sam_len/y_len

    return x_rate,y_rate

调用方法如下所示，我们实验几组看看效果：

# %% [左上角x, 左上角y, 右下角x, 右下角y]
ra = [0,0,10,10]
rb = [4,4,8,8]
x_rate,y_rate = get_same_rate(ra,rb)
x_rate,y_rate # (1.0, 1.0)

ra = [0,0,10,10]
rb = [20,20,28,28]
x_rate,y_rate = get_same_rate(ra,rb)
x_rate,y_rate # (0.0, 0.0)

ra = [0,0,10,10]
rb = [8,8,18,10]
x_rate,y_rate = get_same_rate(ra,rb)
x_rate,y_rate # (0.27, 1.0)

效果还是不错的，可单独X，可单独Y，可以结合XY做综合判断，可盐可甜。

三、谢幕：归纳总结

编程是门艺术，大家对艺术的理解不一样，追求也不一样。

今天快下班时，宝昌（一同事，你不认识不影响了解剧情）一直感叹：“哎呀~啧啧啧……fastapi太优雅了，优雅，好优雅！”。赞美之词，生于真心，溢于言表，晚上回去都会做美梦的那种赞赏。

编程之美就在于，对于同一个功能，有好多种实现方式：可以嵌套5层for循环，也可以混成map排序；可以写if、else通过参数走分支，也可以子类重写父类方法直接同一句代码调用。

说到这里，我又想起了一件事。你看，艺术家总是这么多愁善感。

想听的听，不想听的可以撤了，走前别忘了点赞。

话说，我回老家去买鸡，活鸡现宰。杀鸡店老板现场处理，因为过节，排队的人巨多，都催着赶紧弄。老板带着口罩，全身心投入，摘毛，冲洗，掏内脏，如入无人之境。在巨大工作量面前，他得心应手，弯腰捡个地下的工具，起身还要单独冲冲手。装袋前，会把肉重新冲一遍，擦干净手，装两层袋子。活鸡宰杀切割，送到你手里时，你接触不到任何油污。我敢说，济南任何一家超市都做不到这一点。

真的非得是慢工才能出细活吗？

习惯也很重要吧。

我们老说时间不够，时间不够，所以代码写的不规范。但是，假设，假设有一天，时间给得很充足，那时你是否会，突然变出那个习惯去写注释、去思考效率问题。这就像，你放假了，有空闲了，屋子就会变干净吗？你自己回答。但是，对于爱干净的人来说，即便很忙，房子依然是整洁的。

再就是，解决问题思路还得开放些，几何不行就用代数，代数不行就找我，我是编程表演艺术家TF男孩，擅长编程表演。提醒你早撤，现在晚了。下一次我表演的节目是：人工智能训练音频文件，实现语音识别，并控制LED灯转向。欢迎关注。