Pythonで2つの長方形が重なっているかどうかを判定するプログラム

長方形を4つの要素を持つリスト [x1, y1, x2, y2] で表すことを考えます。ここで、(x1, y1) は左下の角の座標、(x2, y2) は右上の角の座標を表します。

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

問題例

例えば、入力が R1 = [0,0,2,2]、R2 = [1,1,3,3] の場合、2つの長方形は面積を持つ共通領域を持つため、出力は True になります。一方、R1 = [0,0,1,1]、R2 = [1,1,2,2] のように角だけで接している場合は False となります。

解決のアプローチ

この問題を解くには、「重なっていない条件」を考えるのが効果的です。次のいずれかの条件が成り立つ場合、2つの長方形は重なっていません。

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

上記の条件のどれにも当てはまらない場合は、2つの長方形は重なっていると判断できます。アルゴリズムの手順は以下の通りです。

• R1[0] >= R2[2] または R1[2] <= R2[0] または R1[3] <= R2[1] または R1[1] >= R2[3] の場合 → False を返す
• それ以外の場合 → True を返す

実装例

以下にPythonでの実装例を示します。

class Solution:
    def solve(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.solve([0,0,3,3],[1,1,4,4]))

入力

[0,0,3,3],[1,1,4,4]

出力

True

計算量について

このアルゴリズムは比較演算を定数回行うだけなので、時間計算量は O(1)、空間計算量も O(1) と非常に効率的です。衝突判定やゲーム開発、図形処理などの場面で広く使われる基本的なテクニックです。