경계 사각형 충돌 테스트?

Question

나는 최소 x, 최소 y, 최대 x, 최대 y를 알고있는 복잡한 다각형을 가지고있다. 또한 왼쪽 위와 오른쪽 아래 꼭지점을 알고있는 또 다른 직사각형이 있습니다. 이 정보를 알면이 경계 상자가 충돌하는지 어떻게 알 수 있습니까? 감사 :

Answer 1

시도 뭔가 :

typedef struct rect { 
    int top;  // maximum y-coord 
    int bottom; // minimum y-coord 
    int left; // minimum x-coord 
    int right; // maximum x-coord 
} rectangle; 

// Returns 1 if the point (x, y) lies within the rectangle, 0 otherwise 
int is_point_in_rectangle(rectangle r, int x, int y) { 
    if ((r.left <= x && r.right >= x) && 
     (r.bottom <= y && r.top >= y)) 
     return 1; 
    return 0; 
} 

// Returns 1 if the rectangles overlap, 0 otherwise 
int do_rectangles_intersect(rectangle a, rectangle b) { 
    if (is_point_in_rectangle(a, b.left , b.top ) || 
     is_point_in_rectangle(a, b.right, b.top ) || 
     is_point_in_rectangle(a, b.left , b.bottom) || 
     is_point_in_rectangle(a, b.right, b.bottom)) 
     return 1; 
    if (is_point_in_rectangle(b, a.left , a.top ) || 
     is_point_in_rectangle(b, a.right, a.top ) || 
     is_point_in_rectangle(b, a.left , a.bottom) || 
     is_point_in_rectangle(b, a.right, a.bottom)) 
     return 1; 
    return 0; 
} 

당신은 단지 그것의 모든 사항을 반복하고 그들과 함께 is_point_in_rectangle를 호출, 어떤 다각형 동일한 기능을 수행 할 수 있습니다. 복합 다각형에 대한 경계 상자 만 있기 때문에이 방법을 사용하면 거짓 긍정을 얻을 수 있습니다. 즉, 사각형은 복합 다각형의 경계 상자 안에 있지만 다각형 자체 외부에 있습니다. 그러나이 제한은 복잡한 모양이 경계 상자로 단순화되는 모든 방법에 적용됩니다.

Answer 2

간격 [Ax1, Ax2] 및 [Bx1, Bx2]가 겹치면 및 간격 [Ay1, Ay2] 및 [By1, By2]이 겹쳐있는 경우 사각형 A와 B가 충돌합니다.

Answer 3

나는 다음과 같이 작동한다고 생각합니다. 대부분의 경우이지만 더 복잡한 것은 사실이지만 바운딩 박스 검사보다 정확합니다. 다음과 같은 질문에 봐 : 포인트 다각형 내부에있는 경우가

Polygon in rectangle algorithm?

, 당신은 알아 내기위한 알고리즘을 참조하십시오. 이 테스트는 첫 번째 폴리 w.r.t의 각 지점에 적용 할 수 있습니다. 제 2의 것. 반대편. 테스트가 적어도 한 번 이상 통과하면 충돌이 발생합니다.

Answer 4

직사각형의 왼쪽 및 오른쪽 가장자리의 x 좌표 정렬 된 배열을 만듭니다. 그런 다음 "스캔 라인"을 사용하여 사각형을 왼쪽에서 오른쪽으로 이동합니다. 주사선과 겹치는 사각형의 위쪽 및 아래쪽 가장자리의 y 좌표를 포함하는 2 진 탐색 트리를 유지하십시오. 배열의 각 요소에 대해 왼쪽 또는 오른쪽 가장자리인지 확인합니다. 오른쪽 모서리 인 경우 BST에서 상응하는 상단 및 하단 모서리를 제거하십시오. 왼쪽 모서리 인 경우 BST에서 현재 사각형과 겹치는 사각형을 검색합니다. 하나가 있으면 겹침을 반환합니다. 그런 다음 사각형의 위쪽 및 아래쪽 가장자리의 y 좌표를 BST에 추가하십시오. 검색에는 O (n log n) 시간이 걸리므로 직사각형을 정렬하는 데 O (n log n) 시간이 걸리고 2n 반복마다 O (log n) 시간이 걸립니다. Google 검색 결과에서 복사됩니다. 이 같은