長方形の重なりを判定する問題

Fizz-Buzz問題に引き続き、面白い課題を見つけた。こちらも、さらにタイムリーではなく（2年くらい前かも）、既に多数の回答例が出ているが、まずは自分自身でやってみることにした。Fizu-Buzzよりも、制限時間30分のこちらの問題の方が、じっくり考えることが出来て面白そうだ！

［問題］
二次元座標上に、それぞれの辺がX軸・Y軸と平行に置かれた長方形Aと長方形Bがあるとする。その時、長方形Aと長方形Bが一部でも重なるかどうかを判断する条件式を書け。フォーマットは、CやJavaなどのコンピューター言語でも良し、単なる数式でも良い。制限時間は３０分。ただし、考えていることを声に出し、ホワイト・ボードを使って自分の考えのプロセスを説明しながら解くこと。

Life is beautiful: ビル・ゲイツの面接試験－私の場合

------ここから下は自分の思考の過程です。自分で考えてみたい場合はすぐに見ない方が...------

長方形を想像する。

  • 以下のような2次元座標と長方形を想像した。

  • 長方形は、左下の頂点を起点と考え、その座標(x,y)と幅w、高さhで表現することにした。そうすると...
    • 長方形Aは、(Ax, Ay, Aw, Ah)と表現できる。
    • 長方形Bは、(Bx, By, Bw, Bh)と表現できる。

座標系を移動する。

  • まずは空想の世界で単純に考えるために、長方形AまたはBの左下頂点(x,y)が、原点oに一致するように平行移動してみた。
  • ここでは便宜的に長方形Aの(Ax,Ay)を原点oに一致させるように平行移動してみた。そうすると...
    • 長方形Aは、(0, 0, Aw, Ah)と表現できる。
    • 長方形Bは、(Bx-Ax, By-Ay, Bw, Bh) と表現できる。
  • この状態で長方形Bが、原点oと(Aw, Ah)の四角い領域に一部でも存在すれば重なっていることになる。

紙一重の状況を想像する。

  • ギリギリ重なるかどうかの状況であれば、以下のような位置関係を想像できると考えた。（A、Bの大きさの関係は無視して）
B上
B左 A B右
B下
  • そうすると、長方形A(Ax, Ay)は原点oと一致しているのだから、以下のように表現できる。
    • B左の左辺は、-Bw
    • B右の左辺は、 Aw
    • B下の下辺は、-Bh
    • B上の下辺は、 Ah

左右と上下で分けて考える。

  • 紙一重の状況を想像しながら、X要素とY要素を分けて重なる条件を判定してみた。（図形が接している状態は、重なると見なさなかった場合）
    • 長方形Bの左辺Bx-Ax を中心に考えると...
      • -Bw < Bx-Ax < Aw
    • 長方形Bの下辺By-Ay を中心に考えると...
      • -Bh < By-Ay < Ah

ゆえに...

重なる条件は以下のようになった。

  • -Bw < Bx-Ax < Aw かつ -Bh < By-Ay < Ah
a = {:x=>100, :y=>120, :w=>40, :h=>30}
b = {:x=>130, :y=>140, :w=>50, :h=>20}

x = b[:x] - a[:x]
y = b[:y] - a[:y]
if -b[:w] < x && x < a[:w] && 
   -b[:h] < y && y < a[:h]
  puts "重なってるよ!"
else
  puts "...。"
end