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);
}
그러나 이것을 계산하는보다 효율적인 방법이있을 것으로 기대합니다.
가장 적은 작업 측면에서 가장 효율적인 방법은 무엇입니까?
답변
범위가 겹치는 것은 무엇을 의미합니까? 즉, 두 범위에있는 숫자 C가 있음을 의미합니다.
x1 <= C <= x2
과
y1 <= C <= y2
이제 범위가 잘 구성되어 있다고 가정하면 (x1 <= x2 및 y1 <= y2) 테스트하기에 충분합니다.
x1 <= y2 && y1 <= x2
답변
두 가지 범위 [x1, x2], [y1, y2]
def is_overlapping(x1,x2,y1,y2):
return max(x1,y1) <= min(x2,y2)
답변
이것은 정상적인 인간의 뇌를 쉽게 뒤틀 수 있기 때문에 이해하기 쉬운 시각적 접근 방식을 찾았습니다.
르 설명
두 범위가 “너무 뚱뚱해” 두 슬롯의 너비를 모두 합한 슬롯에 맞으면 겹쳐집니다.
범위의 경우 다음 [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!
}답변
Simon의 큰 대답 이지만 저에게는 반대 사례를 생각하는 것이 더 쉬웠습니다.
두 범위가 겹치지 않는 경우는 언제입니까? 그것들 중 하나가 다른 하나가 끝난 후에 시작될 때 겹치지 않습니다.
dont_overlap = x2 < y1 || x1 > y2
이제 겹칠 때 쉽게 표현할 수 있습니다.
overlap = !dont_overlap = !(x2 < y1 || x1 > y2) = (x2 >= y1 && x1 <= y2)
답변
시작의 최대 값에서 범위의 끝의 최소값을 빼면 트릭을 수행하는 것 같습니다. 결과가 0보다 작거나 같으면 겹칩니다. 이것은 그것을 잘 시각화합니다 :
답변
질문은 가장 짧은 코드가 아니라 가장 빠른 코드라고 생각합니다. 가장 빠른 버전은 가지를 피해야하므로 다음과 같이 작성할 수 있습니다.
간단한 경우 :
static inline bool check_ov1(int x1, int x2, int y1, int y2){
// insetead of x1 < y2 && y1 < x2
return (bool)(((unsigned int)((y1-x2)&(x1-y2))) >> (sizeof(int)*8-1));
};
또는이 경우 :
static inline bool check_ov2(int x1, int x2, int y1, int y2){
// insetead of x1 <= y2 && y1 <= x2
return (bool)((((unsigned int)((x2-y1)|(y2-x1))) >> (sizeof(int)*8-1))^1);
};
답변
return x2 >= y1 && x1 <= y2;
