Pythonで2つの長方形の重なり（オーバーラップ）を判定する方法

長方形のオーバーラップとは

ここでは、長方形をリスト [x1, y1, x2, y2] として表します。このとき、(x1, y1) は長方形の左下の角の座標、(x2, y2) は右上の角の座標を意味します。

2つの長方形が「オーバーラップ（重なり）している」とは、それらの共通部分（交差領域）の面積が正であることを指します。したがって、角や辺だけが接しているような場合（面積がゼロになる接触）は、重なっているとはみなされません。

問題の定義

2つの軸に平行な長方形（axis-aligned rectangles）が与えられたとき、それらが互いに重なっているかどうかを判定します。

たとえば、入力が R1 = [0,0,2,2]、R2 = [1,1,3,3] の場合、2つの長方形は部分的に重なっているため、出力は True になります。

解法のアプローチ

この問題は「逆に考える」と非常にシンプルになります。つまり、2つの長方形が重なっていないための条件を列挙し、そのいずれかに該当すれば False を返すのです。具体的には、次の4つのケースがあります。

• R1 の左端が R2 の右端以上にある（R1[0] >= R2[2]）→ R1 が完全に R2 の右側にある
• R1 の右端が R2 の左端以下にある（R1[2] <= R2[0]）→ R1 が完全に R2 の左側にある
• R1 の上端が R2 の下端以下にある（R1[3] <= R2[1]）→ R1 が完全に R2 の下側にある
• R1 の下端が R2 の上端以上にある（R1[1] >= R2[3]）→ R1 が完全に R2 の上側にある

これらの条件のいずれかが成立していれば、2つの長方形は上下左右のいずれかの方向に完全に離れているため False を返します。逆に、どの条件も成立しなければ、両者は面積を持つ共通部分を持つことになり、True を返します。

なお、辺や角がちょうど接している場合（例：R1 = [0,0,1,1]、R2 = [1,0,2,1]）は、共通部分の面積がゼロになるため、このアルゴリズムでは False が返される点に注意してください。

実装例

class Solution:
    def isRectangleOverlap(self, R1, R2):
        if (R1[0]>=R2[2]) or (R1[2]<=R2[0]) or
           (R1[3]<=R2[1]) or (R1[1]>=R2[3]):
           return False
        else:
    return True
ob = Solution()
print(ob.isRectangleOverlap([0,0,2,2],[1,1,3,3]))

入力

[0,0,2,2],[1,1,3,3]

出力

True

計算量について

このアルゴリズムは座標同士の比較のみを行うため、時間計算量・空間計算量ともに O(1) という非常に効率的な処理になります。長方形の数が増える場合でも、各ペアの判定自体は定数時間で完了します。