给定两个包含范围[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) 那么x1 <= y2 || x2 >= y1总是成立的。 作为
x1 ... x2
y1 .... y2
如果是x1 > y2，那么它们不重叠 或
x1 ... x2
y1 ... y2
如果x2 < y1，它们不重叠。
其他回答
这很容易扭曲正常人的大脑，所以我找到了一个更容易理解的视觉方法:
勒解释
如果两个范围“太胖”，无法放入正好是两者宽度之和的槽中，那么它们就会重叠。
对于范围[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!
}
重叠(X, Y):= if (X1 <= Y1) then (Y1 <= X2) else (X1 <= Y2)。
证明:
考虑X在Y之前或与Y左对齐的情况，即X1 <= Y1。那么Y要么在X内部开始，要么在X的末尾开始，即Y1 <= X2;或者Y远离x，第一个条件是重叠;第二个，不是。
在互补的情况下，Y在X之前，同样的逻辑适用于交换的实体。
So,
重叠(X, Y):= if (X1 <= Y) then (Y1 <= X2) else重叠(Y, X)。
但这似乎并不完全正确。在递归调用中，第一个测试是多余的，因为我们已经从第一个调用的第一个测试中知道了实体的相对位置。因此，我们实际上只需要测试第二个条件，即交换后(X1 <= Y2)。所以,
重叠(X, Y):= if (X1 <= Y1) then (Y1 <= X2) else (X1 <= Y2)。
QED.
Ada的实现:
type Range_T is array (1 .. 2) of Integer;
function Overlap (X, Y: Range_T) return Boolean is
(if X(1) <= Y(1) then Y(1) <= X(2) else X(1) <= Y(2));
测试程序:
with Ada.Text_IO; use Ada.Text_IO;
procedure Main is
type Range_T is array (1 .. 2) of Integer;
function Overlap (X, Y: Range_T) return Boolean is
(if X(1) <= Y(1) then Y(1) <= X(2) else X(1) <= Y(2));
function Img (X: Range_T) return String is
(" [" & X(1)'Img & X(2)'Img & " ] ");
procedure Test (X, Y: Range_T; Expect: Boolean) is
B: Boolean := Overlap (X, Y);
begin
Put_Line
(Img (X) & " and " & Img (Y) &
(if B then " overlap .......... "
else " do not overlap ... ") &
(if B = Expect then "PASS" else "FAIL"));
end;
begin
Test ( (1, 2), (2, 3), True); -- chained
Test ( (2, 3), (1, 2), True);
Test ( (4, 9), (5, 7), True); -- inside
Test ( (5, 7), (4, 9), True);
Test ( (1, 5), (3, 7), True); -- proper overlap
Test ( (3, 7), (1, 5), True);
Test ( (1, 2), (3, 4), False); -- back to back
Test ( (3, 4), (1, 2), False);
Test ( (1, 2), (5, 7), False); -- disjoint
Test ( (5, 7), (1, 2), False);
end;
以上程序输出:
[ 1 2 ] and [ 2 3 ] overlap .......... PASS
[ 2 3 ] and [ 1 2 ] overlap .......... PASS
[ 4 9 ] and [ 5 7 ] overlap .......... PASS
[ 5 7 ] and [ 4 9 ] overlap .......... PASS
[ 1 5 ] and [ 3 7 ] overlap .......... PASS
[ 3 7 ] and [ 1 5 ] overlap .......... PASS
[ 1 2 ] and [ 3 4 ] do not overlap ... PASS
[ 3 4 ] and [ 1 2 ] do not overlap ... PASS
[ 1 2 ] and [ 5 7 ] do not overlap ... PASS
[ 5 7 ] and [ 1 2 ] do not overlap ... PASS
return x2 >= y1 && x1 <= y2;
为什么这样做有效: 范围不重叠的唯一情况是当一个范围的结束在另一个范围的开始之前。所以我们想要!(x2 < y1 || x1 > y2)它等价于上面。
反过来思考:如何使这两个范围不重叠?给定[x1, x2]，则[y1, y2]应在[x1, x2]之外，即y1 < y2 < x1或x2 < y1 < y2，这等价于y2 < x1或x2 < y1。
因此，使两个范围重叠的条件是:不(y2 < x1或x2 < y1)，这相当于y2 >= x1和x2 >= y1(与Simon接受的答案相同)。
如果有人正在寻找计算实际重叠的一行程序:
int overlap = ( x2 > y1 || y2 < x1 ) ? 0 : (y2 >= y1 && x2 <= y1 ? y1 : y2) - ( x2 <= x1 && y2 >= x1 ? x1 : x2) + 1; //max 11 operations
如果你想要少一些操作，但多一些变量:
bool b1 = x2 <= y1;
bool b2 = y2 >= x1;
int overlap = ( !b1 || !b2 ) ? 0 : (y2 >= y1 && b1 ? y1 : y2) - ( x2 <= x1 && b2 ? x1 : x2) + 1; // max 9 operations
