読者です 読者をやめる 読者になる 読者になる

2つの期間が重なり合うかどうかを判定する。

2つの期間 A〜B と X〜Y が重なっているかどうかを判定したい場合。

のように4つのパターンがある。これを単純に、

A <= X && Y <= B ||
X <= A && Y <= B ||
A <= X && B <= Y ||
X <= A && B <= Y

のように判定してはいけない。

Xは青い線の上を、Yは赤い線の上を動くとき、A〜B と X〜Y は重なり合う。この条件は、

X <= B && A <= Y

これで4つのパターンをカバーできる。ORは不要。始点と終点をわかりやすく書くと以下になる。

始点2 <= 終点1 && 始点1 <= 終点2

アルゴリズムに名前がありそうな気がするけど、見つけられなかった。


(追記) 矩形の重なり判定の方が情報が見つかった。

* Life is beautiful: ビル・ゲイツの面接試験-私の場合
* 長方形の重なりを判定する問題 - ザリガニが見ていた...。