ユニファ開発者ブログ

ユニファ株式会社プロダクトデベロップメント本部メンバーによるブログです。

時間帯被るかどうかから長方形の衝突検知

こんにちは、午睡チェックサーバーエンドエンジニアのちょうです。最近開発で見つかったちょっと難しい問題について話したいです。それは時間帯が被ってるかどうかのチェックです。

時間帯

例えば

  • 午後3時から午後4時
  • 午後5時から午後6時

という２つの時間帯は被らないとし、

  • 午前10時から午後4時
  • 午後3時から午後5時

が被るとしたら、どうやって時間帯が被るかをチェックしますか。

時間帯を表記しやすいために、[15:00, 16:00] は午後3時から午後4時の意味をします。なお、[15:00, 16:00] と [16:00, 17:00] は被らないとします。

個別のケースを考えるより、すべて可能なケースをここにリストアップしました。

f:id:unifa_tech:20190603190445p:plain

２つの時間帯の関係は全部6ケースあります。以下金色の時間帯1は[S1, E1]、水色の時間帯2は[S2, E2]とします。

  1. 被らない、E1 <= S2
  2. 被る、S1 < S2 < E1
  3. 被る、S2 <= S1 < E1 <= E2
  4. 被る、S1 <= S2 < E2 <= E1
  5. 被る、S1 < E2 < E1
  6. 被らない、E2 <= S1

被るケースが4個あるので、4ケースの一つに当てはまれば被ります。とはいえ、４つのケースに共通点あまりないし、そのままコードにするのは分かりにくいです。

ここで一つのテクニックは被るケース以外のケース、つまり被らないケース、の逆にすれば簡単にできます。

  ALL CASES - <CASE 1> - <CASE 6>
=!<CASE 1>   && !<CASE 6>
=!(E1 <= S2) && !(E2 <= S1)
= (E1 > S2)  &&  (E2 > S1)

実際、↑の条件で被る４つのケース一つ一つチェックしてみれば、すべて合ってることが分かります。もし数学が強い人がちゃんと４つの被るケースの共通点を見つければ、たぶん同じ結果になるでしょう。我々一般人にとって、同じ結果に辿り着けるには、逆思考がキーになります。

長方形の衝突検知

もうひとつ自分が興味を持っていた問題を紹介します。長方形の衝突検知。

f:id:unifa_tech:20190604113432p:plain

長方形の衝突検知はよくゲームで使われるらしいです。例えば、２つのオブジェクトがぶつかるかによってダメージを受けるかなどを決めます。

方法1

時間帯と同じ方法を使えます。金色長方形を長方形1とし、水色長方形は長方形2とする。X軸に長方形1と長方形2が被るかつY軸に長方形1と長方形2が被れば長方形1と長方形2が被る。つまり

長方形1: (x1, y1), (x2, y2)
長方形2: (x3, y3), (x4, y4)
[x1, x2] と [x3, x4] 被る -> (x2 > x3) && (x4 > x1)
[y1, y2] と [y3, y4] 被る -> (y2 > y3) && (y4 > y1)
よって衝突の条件は
(x2 > x3) && (x4 > x1) && (y2 > y3) && (y4 > y1)
方法2

↑以外に、もう一つ方法があります。２つの円が被るかどうかの条件を考えてみましょう。円でしたら中心と中心の距離が２つの円の半径の和より大きいでしたら被らない、小さいでしたら被るということになります。同じように、長方形の中心と中心のX軸の距離が２つの長方形の高さの半分より小さいかつY軸の距離も２つの長方形の幅の半分より小さいでしたら２つの長方形が被る。つまり

f:id:unifa_tech:20190604140657p:plain

長方形1: (x1, y1), (x2, y2)
長方形2: (x3, y3), (x4, y4)
w1 = (x2 - x1), h1 = (y2 - y1)
w2 = (x4 - x3), h2 = (y4 - y3)
中心1 ((x2 + x1) / 2, (y2 + y1) / 2)
中心2 ((x4 + x3) / 2, (y4 + y3) / 2)
ABSは絶対値関数
中心の距離: (
    ABS((x4 + x3) / 2 - (x2 + x1) / 2), 
    ABS((y4 + y3) / 2 - (y2 + y1) / 2)
)
衝突の条件
ABS((x4 + x3) / 2 - (x2 + x1) / 2) < (w1 + w2) / 2 && 
    ABS((y4 + y3) / 2 - (y2 + y1) / 2)) < (h1 + h2) / 2
ABS((x4 + x3) - (x2 + x1)) < (w1 + w2) && 
    ABS((y4 + y3) - (y2 + y1))) < (h1 + h2)
ABS((x4 + x3) - (x2 + x1)) < ((x2 - x1) + (x4 - x3)) && 
    ABS((y4 + y3) - (y2 + y1))) < ((y2 - y1) + (y4 - y3))

条件は２つに減りました。

方法１と方法２が同じなのかは私が答えられないですが、中心の距離で判断するのを理解すればいいと思います。

さいご

いかがでしょうか。たまにこういう数学っぽい問題を解いてみましょうか。普段の開発ではあまりこういう問題が出ないですが、気分転換としていい勉強になると思います。