给定两个包含范围[x1:x2]和[y1:y2],其中x1≤x2和y1≤y2,测试这两个范围是否有重叠的最有效方法是什么?

一个简单的实现如下:

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);
}

但是我希望有更有效的方法来计算这个。

就最少的操作而言,哪种方法是最有效的?


当前回答

这很容易扭曲正常人的大脑,所以我找到了一个更容易理解的视觉方法:

勒解释

如果两个范围“太胖”,无法放入正好是两者宽度之和的槽中,那么它们就会重叠。

对于范围[a1, a2]和[b1, b2],这将是:

/**
 * we are testing for:
 *     max point - min point < w1 + w2    
 **/
if max(a2, b2) - min(a1, b1) < (a2 - a1) + (b2 - b1) {
  // too fat -- they overlap!
}

其他回答

西蒙的回答很好,但对我来说,相反的情况更容易思考。

什么时候两个范围不重叠?当其中一个开始后另一个结束时,它们不会重叠:

dont_overlap = x2 < y1 || x1 > y2

当它们重叠时,很容易表示:

overlap = !dont_overlap = !(x2 < y1 || x1 > y2) = (x2 >= y1 && x1 <= y2)

考虑到: (x1, x2) (y1, y2) 那么x1 <= y2 || x2 >= y1总是成立的。 作为

      x1 ... x2
y1 .... y2

如果是x1 > y2,那么它们不重叠 或

x1 ... x2
    y1 ... y2

如果x2 < y1,它们不重叠。

如果你正在处理,给定两个范围[x1:x2]和[y1:y2],自然/反自然顺序范围同时存在:

自然顺序:x1 <= x2 && y1 <= y2或 反自然顺序:x1 >= x2 && y1 >= y2

然后你可能想用这个来检查:

它们重叠<=> (y2 - x1) * (x2 - y1) >= 0

其中只涉及四个操作:

2倍 一个乘法 一个比较

我相信min(upper(A),upper(B))>=max(lower(A),lower(B))将是一个很好的解决方案,不仅因为它的简单性,而且因为它超越了两个范围的可扩展性。

这很容易扭曲正常人的大脑,所以我找到了一个更容易理解的视觉方法:

勒解释

如果两个范围“太胖”,无法放入正好是两者宽度之和的槽中,那么它们就会重叠。

对于范围[a1, a2]和[b1, b2],这将是:

/**
 * we are testing for:
 *     max point - min point < w1 + w2    
 **/
if max(a2, b2) - min(a1, b1) < (a2 - a1) + (b2 - b1) {
  // too fat -- they overlap!
}