n个矩形的重叠面积问题及其变种-python实现

青旅半醒 2022-03-10 05:36 178阅读 0赞

问题：平面上有n个平行于坐标轴的矩形,他们总的覆盖面积是多少?重叠的面积只算一次

最佳参考：https://blog.csdn.net/u013480600/article/details/39503023

上面参考博客的讲解非常好，就是有点小错误，改正后的思路如下：

*  假设输入的矩阵中共有num1个不同的x坐标和num2个不同的y坐标,那么整个二维平面就被分割成了(num1-1)\*(num2-1)个小方格矩形，这些小方格矩形之间没有重叠.
 *  我们只要看上面(num1-1)\*(num2-1)个小方格矩形，哪些被某个大矩形覆盖，哪些没有被任何一个大矩形覆盖即可.
 *  我们需要把所有不同的x坐标和y坐标进行排序，得到对应的列表x和y，方便之后的遍历
 *  我们令mp\[i\]\[j\]=1表示以(x\[i\], y\[j\])点为左下角,以(x\[i+1\], y\[j+1\])点为右上角的那个小矩形被某个大矩形覆盖了.
 *  假设某个大矩形的x坐标范围在\[xi,xj\]之间而y坐标在\[yk,yh\]之间.那么该大矩阵肯定使得所有的mp\[a\]\[b\]+=1. 其中i<=a<j且k<=b<h.

这里最重要的要理解的一点是：mp\[i\]\[j\]的含义，这里0<= i<num1，0<=j<num2，mp矩阵中的每一个位置对应一个小方格矩形，即以(x\[i\], y\[j\])点为左下角,以(x\[i+1\], y\[j+1\])点为右上角的小矩形，因为x\[i\]和x\[i+1\]，y\[j\]和y\[j+1\]是x和y列表中相邻的两个数，之间没有坐标，因此只能形成一个矩形。在下面的程序中，mp\[i\]\[j\]的值表示被大矩形覆盖的次数。

# 下面的函数为求解函数，array为矩形的坐标矩阵，单个矩形表示为[x0,y0,x1,y1]，N为矩形的个数
    def func(array, N):
        list_x = []
        list_x.extend([x[0] for x in array])
        list_x.extend([x[2] for x in array])
        list_x = sorted(list(set(list_x)))
        list_y = []
        list_y.extend([x[1] for x in array])
        list_y.extend([x[3] for x in array])
        list_y = sorted(list(set(list_y)))
        numx, numy=len(list_x),len(list_y)
    
        mp = [[0 for i in range(numy-1)] for j in range(numx-1)]
        for i in range(N):
            L_x, R_x = list_x.index(array[i][0]), list_x.index(array[i][2])
            L_y, R_y = list_y.index(array[i][1]), list_y.index(array[i][3])
            for m in range(L_x,R_x):
                for n in range(L_y,R_y):
                    mp[m][n]+=1
        area = 0
        for i in range(numx-1):
            for j in range(numy-1):
                if mp[i][j]:
                    area += (list_x[i+1]-list_x[i])*(list_y[j+1]-list_y[j])
        return area
    
    # 这是一道笔试题，下面为输入部分
    N=int(input())
    array = []
    for i in range(N):
        str_in = input()
        nums = [int(n) for n in str_in.split()]		# [x0,y0,x1,y1]
        array.append(nums)
    print(func(array,N))

变种一：求被所有矩形都覆盖的面积大小，上面代码中判断条件 if mp\[i\]\[j\]: 改为 if mp\[i\]\[j\]==N: 即可

变种二：计算出平面内重叠矩形数量最多的地方,有多少个矩形相互重叠。 这个返回mp矩阵中最大的哪个数就可以了，当然要注意，如果最大数是1，说明没有矩形重叠，这种情况另外做输出。

上述代码是求n个矩形相关的重叠面积，如果只求两个矩形，那就有些大材小用了，下面给出计算两个矩形的重叠面积代码：

def commonArea(rec1,rec2):
        l_x = max(rec1[0],rec2[0])
        d_y = max(rec1[1],rec2[1])
        r_x = min(rec1[2],rec2[2])
        u_y = min(rec1[3],rec2[3])
        length = r_x-l_x
        wide = u_y-d_y
        if length>0 and wide>0:
            return length*wide
        return 0
    
    #rec = [x0,y0,x1,y1]
    rec1=[1,1,4,4]
    rec2=[2,2,5,5]
    print(commonArea(rec1,rec2))