给定两个包含范围[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);
}
但是我希望有更有效的方法来计算这个。
就最少的操作而言，哪种方法是最有效的?
当前回答
给定两个范围[x1,x2]， [y1,y2]
def is_overlapping(x1,x2,y1,y2):
return max(x1,y1) <= min(x2,y2)
其他回答
你已经有了最有效的表示——这是需要检查的最小值，除非你确定x1 < x2等，然后使用其他人提供的解决方案。
你可能应该注意到，一些编译器实际上会为你优化它——只要这4个表达式中的任何一个返回true就返回。如果其中一个返回true，那么最终结果也会返回true——因此可以跳过其他检查。
这很容易扭曲正常人的大脑，所以我找到了一个更容易理解的视觉方法:
勒解释
如果两个范围“太胖”，无法放入正好是两者宽度之和的槽中，那么它们就会重叠。
对于范围[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!
}
如果你正在处理，给定两个范围[x1:x2]和[y1:y2]，自然/反自然顺序范围同时存在:
自然顺序:x1 <= x2 && y1 <= y2或 反自然顺序:x1 >= x2 && y1 >= y2
然后你可能想用这个来检查:
它们重叠<=> (y2 - x1) * (x2 - y1) >= 0
其中只涉及四个操作:
2倍 一个乘法 一个比较
值域重叠是什么意思?这意味着存在一个在两个范围内的数C，即。
x1 <= C <= x2
and
y1 <= C <= y2
为了避免混淆，考虑范围为: [x1:x2]和[y1:y2]
现在，如果我们可以假设范围是构造良好的(因此x1 <= x2和y1 <= y2)，那么就足以进行测试
x1 <= y2 && y1 <= x2
OR
(StartA <= EndB)和(EndA >= StartB)
以下是我的看法:
int xmin = min(x1,x2)
, xmax = max(x1,x2)
, ymin = min(y1,y2)
, ymax = max(y1,y2);
for (int i = xmin; i < xmax; ++i)
if (ymin <= i && i <= ymax)
return true;
return false;
除非您正在对数十亿个宽间距整数运行一些高性能的范围检查器，否则我们的版本应该执行类似的操作。我的观点是，这是微观优化。
