こんにちは、午睡チェックサーバーエンドエンジニアのちょうです。最近開発で見つかったちょっと難しい問題について話したいです。それは時間帯が被ってるかどうかのチェックです。
時間帯
例えば
- 午後3時から午後4時
- 午後5時から午後6時
という２つの時間帯は被らないとし、
- 午前10時から午後4時
- 午後3時から午後5時
が被るとしたら、どうやって時間帯が被るかをチェックしますか。
時間帯を表記しやすいために、[15:00, 16:00] は午後3時から午後4時の意味をします。なお、[15:00, 16:00] と [16:00, 17:00] は被らないとします。
個別のケースを考えるより、すべて可能なケースをここにリストアップしました。
２つの時間帯の関係は全部6ケースあります。以下金色の時間帯1は[S1, E1]、水色の時間帯2は[S2, E2]とします。
- 被らない、E1 <= S2
- 被る、S1 < S2 < E1
- 被る、S2 <= S1 < E1 <= E2
- 被る、S1 <= S2 < E2 <= E1
- 被る、S1 < E2 < E1
- 被らない、E2 <= S1
被るケースが4個あるので、4ケースの一つに当てはまれば被ります。とはいえ、４つのケースに共通点あまりないし、そのままコードにするのは分かりにくいです。
ここで一つのテクニックは被るケース以外のケース、つまり被らないケース、の逆にすれば簡単にできます。
ALL CASES - <CASE 1> - <CASE 6> =!<CASE 1> && !<CASE 6> =!(E1 <= S2) && !(E2 <= S1) = (E1 > S2) && (E2 > S1)
実際、↑の条件で被る４つのケース一つ一つチェックしてみれば、すべて合ってることが分かります。もし数学が強い人がちゃんと４つの被るケースの共通点を見つければ、たぶん同じ結果になるでしょう。我々一般人にとって、同じ結果に辿り着けるには、逆思考がキーになります。
長方形の衝突検知
もうひとつ自分が興味を持っていた問題を紹介します。長方形の衝突検知。
長方形の衝突検知はよくゲームで使われるらしいです。例えば、２つのオブジェクトがぶつかるかによってダメージを受けるかなどを決めます。
方法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軸の距離も２つの長方形の幅の半分より小さいでしたら２つの長方形が被る。つまり
長方形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))
条件は２つに減りました。
方法１と方法２が同じなのかは私が答えられないですが、中心の距離で判断するのを理解すればいいと思います。
さいご
いかがでしょうか。たまにこういう数学っぽい問題を解いてみましょうか。普段の開発ではあまりこういう問題が出ないですが、気分転換としていい勉強になると思います。
