1. ホーム
  2. パフォーマンス

[解決済み】2つの範囲が重なっているかどうかをテストする最も効率的な方法は何ですか?

2022-03-27 19:50:52

質問

2つの包含範囲 [x1:x2] と [y1:y2] があり、ここで x1 ≤ x2y1 ≤ y2 2つの範囲が重なっているかどうかを調べる最も効率的な方法は何でしょうか?

簡単な実装は以下の通りです。

bool testOverlap(int x1, int x2, int y1, int y2) {
  return (x1 >= y1 && x1 <= y2) ||
         (x2 >= y1 && x2 <= y2) ||
         (y1 >= x1 && y1 <= x2) ||
         (y2 >= x1 && y2 <= x2);
}

しかし、もっと効率的に計算する方法があると期待しています。

どのような方法が最も少ない演算量で効率的なのでしょうか?

解決方法は?

範囲が重なるとはどういうことでしょうか?両方の範囲に含まれる数Cが存在することを意味します、つまり

x1 <= C <= x2

そして

y1 <= C <= y2

混乱を避けるために、範囲がそうであると考える。 [x1:x2] と [y1:y2] です。

さて、もし範囲が整形式である(x1 <= x2、y1 <= y2)と仮定することが許されるなら、次のテストをすれば十分である。

x1 <= y2 && y1 <= x2

または

(StartA <= EndB)かつ(EndA >= StartB)