직사각형 교차 및 교차 구역 의 원리 해석 구하 기

(1)하나의 알고리즘 을 설계 하여 두 사각형 이 교차 하 는 지 확인(즉 중첩 구역 이 있 음)(2)만약 에 두 사각형 이 교차 하면 하나의 알고리즘 을 설계 하여 교차 하 는 구역 사각형(1)을 구한다.이 문제 에 대해 일반적인 사 고 는 한 사각형 의 네 개의 정점 이 다른 사각형 의 구역 안에 있 는 지 판단 하 는 것 이다.이 사고방식 이 가장 간단 하지만 효율 이 높 지 않 고 오류 가 존재 한다.오류 가 어디 에 있 는 지 아래 에서 분석 해 보 자위의 그림 과 같이 사각형 의 교차(구역 중첩)를 세 가지 로 나 누 었 다.(다른 구분 도 있 을 수 있다)세 번 째 상황 에 대해 그림 속 의(3)와 같이 두 사각형 이 교차 하지만 한 사각형 의 정점 은 다른 사각형 내부 에 존재 하지 않 는 다.그래서 그런 생각 에 오류 가 존재 하 는데 이런 상황 에 대한 교 제 는 검사 할 수 없다.위의 그림 을 자세히 살 펴 보면 다른 생각 이 떠 오른다.그것 은 바로 두 사각형 의 중심 좌표 의 수평 과 수직 거 리 를 판단 하 는 것 이다.이 두 값 이 특정한 조건 을 만족 시 키 기만 하면 교차 할 수 있다.직사각형 A 의 너비 Wa=Xa2-Xa1 높이 Ha=Ya2-Ya1 사각형 B 의 너비 Wb=Xb2-Xb1 높이 Hb=Yb2-Yb1 사각형 A 의 중심 좌표(Xa3,Ya3)=(Xa2+Xa1)/2,(Ya2+Ya1)/2)사각형 B 의 중심 좌표(Xb3,Yb3)=((Xb2+Xb1)/2,(Yb2+Yb1)/2)아래 두 식 을 동시에 만족 시 키 면 두 사각형 이 교차 하 는 것 을 설명 할 수 있다.1)|Xb3-Xa3|<=Wa/2+Wb/2 2)|Yb3-Ya3|<=Ha/2+Hb/2::|Xb2+Xb1-Xa2-Xa2-Xa1|<=Xa2-Xa1+Xb2+Xb2-Xb2-Yb1-Ya2-Ya2-Ya1|<=Y a2-Ya1+Yb22-Yb2-Yb1(2)이 문제 에 대해 두 직사각형 이 교차 한 후의 직사각형 을 C 로 설정 하고,직사각형 C 의 왼쪽 상단 좌 좌 표 는(Xc1,Yc1),오른쪽 아래 각 좌 표 는(Xc2,Yc2,Yc2,Yc2,Yc2,Yc2,Yc2,Yc2,Yc2)위의 그림 을 살 펴 보면,분명히 얻 을 수 있다:XC1=max(Xa1,Xb1)Yc1=max(Ya1,Yb1)Xc2=min(Xa2,Xb2)Yc2=min(Ya2,Yb2)이렇게 사각형 의 교차 구역 을 구 했다.또한 직사각형 이 교차 하 는 것 을 가정 하지 않 는 전제 에서 정의(XC1,Yc1),(XC2,Yc2),그리고 XC1,Yc1,XC2,Yc2 의 값 은 위의 네 가지 식 에서 나 온 다 는 것 을 알 게 되 었 다.이렇게 하면 XC1,Yc1,XC2,Yc2 의 값 에 따라 직사각형 의 교 류 를 판단 할 수 있다.Xc1,Yc1,Xc2,Yc2 는 아래 두 식 을 동시에 만족 시 키 면 두 직사각형 이 교차 하 는 것 을 설명 할 수 있다.3)Xc 1<=Xc 2 4)Yc 1<=Yc 2 즉:max(Xa1,Xb1)<=min(Xa2,Xb2)max(Ya1,Yb1)<=min(Ya 2,Yb2)