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: ビル・ゲイツの面接試験－私の場合 * 長方形の重なりを判定する問題 - ザ

[lalala360]

リーダブルコードに載ってる「反対を考える」手法。重なるパターンを全部列挙しようとすると複雑になるが、重ならないパターンは2パターン(B < X || Y < A)しかない。これを否定すると、この記事の式になる。

[otchy210]

これ、毎回絵を描いて考えて納得してコーディングするのに、後でコードみるといつも不安になるやつだ！確かに名前はないような…。

[tanishiking24]

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

[n314]

絵がないと不安になる。

[ariteku]

カンニングさせて頂くでござる

[popio]

2つの期間が重ならない場合の背反と考えればいいらしい

[koseki]

今日 @gommmmmm に指摘されて、なるほどー！とおもったことを記事に書きました。見てねー