특정 방식으로 배치 된 두 개의 사각형에 대한 알고리즘

Question

특정 사각형 배치로 내 문제를 해결하는 적절한 방법을 찾는 데 시간을 할애했습니다.

직접 문제가 발생합니다.

크기가 고정 된 두 개의 사각형이 있습니다. 그 중 하나는 잠겨있어 움직일 수 없으며 다른 하나는 자유롭게 움직일 수 있습니다.

두 가지가 고정 너비와 높이 캔버스에 배치되어 있습니다. 1000x1000이라고합시다.

움직일 수있는 사각형이 1000x1000 캔버스 범위를 벗어날 수없는 반면, 두 번째 움직일 수있는 사각형을 다른 하나의 고정 된 사각형과 수평 또는 수직 정렬로 배치해야합니다.

수평/수직 정렬의 정의에서 알 수있는 것은 X 축 (수평 축) 또는 Y 축 (수직 축) 만 보았을 때 움직일 수있는 축 또는 다른 축 .

내가 해킹으로 문제를 해결할 수 있음을 알고 있지만 더 똑똑한 해결책을 찾고 싶습니다.

제안 사항?

EDIT : 두 개의 직사각형에 대한 모든 정보가 알려져 있습니다. 코너, 너비/높이.

Answer 1

일부 X [-inf, + inf] 축과 공칭 Y [-inf, + inf] 축에 대한 좌표 평면이 주어지면 두 점은 수평 축의 좌표 우리는 X를 선택한다). 수직 축 (Y)의 좌표가 같으면 수평 정렬이라고 할 수 있습니다.

사각형은 x1 < = x2 및 y1 < = y2와 같은 두 쌍의 좌표 (x1, y1) 및 (x2, y2)로 설명 할 수 있습니다. (쌍이 섞여 있다면 실제로이 형식을 사용하도록 다시 배열 할 수 있습니다. 더 편리 할 것입니다.)

경우에만 사각형 (r1)은 다른 사각형 (INSERT)에 존재한다고 할 수 있습니다 if r1.x1> = r2.x1, r1.y1> = r2.y1, r1.x2 < = r2.x2 및 r1.y2 < = r2.y2가 모두 true 인 경우. 이것은 당신이 속한 사분면이나 축이 어느 방향으로 움직여도 상관 없습니다.

사각형 (r1)은 r1.x1과 r1.x2가 모두 범위 (r2.x1, r2.x2)를 벗어나면 r1.y1 인 경우에만 다른 사각형 (r2)을 벗어나서 상주한다고 말할 수 있습니다. r1.y2가 범위를 벗어납니다 (r2.y1, r2.y2). 여기에는 r2가 INSIDE r1 인 경우도 포함됩니다.

직사각형 (r1)은 직사각형 바깥쪽에 있고 그 직사각형이 내부에없는 경우에만 다른 직사각형 (r2)에서 분리 될 수 있습니다. (즉 : R2 & & NOT R2 INSIDE R1 OUTSIDE R1)

사각형 (R1)는 그 어느 INSIDE이나 그 사각형 벗어나는 경우에만, 다른 직사각형 (R2)를 중첩하도록 상기 수있다. (다른 방법으로 다른 사각형 내부의 사각형이 유효한 겹침이라고 주장하고 OVERLAP =! SEPARATE, 응용 프로그램에 따라 다름).

직사각형의 정렬이 훨씬 더 어렵습니다. 동일한 크기의 직사각형은 점과 동일한 방식으로 정렬됩니다 (각 점의 (x1, y1)을 참조 점으로 사용). 다른 크기의 직사각형의 경우 중심점을 참조로 사용하는 것이 좋습니다 : 직사각형은 (r1.x1 + r1.(r1.y1 + r1.y2)/2 = (r2.y1 + r2.y2)/2이면 수평 정렬된다.

나는이 규칙들을 포함하는 클래스를 작성하고, 세 개의 사각형 (앞에서 언급 한 두 개의 사각형과 세 번째 사각형의 경계 상자)을 사용하여 각 운동을 검사하는 데 사용합니다.

CLASS rectangle 
    x1 
    x2 
    y1 
    y2 

    CONSTRUCT(xx1, yy1, xx2, yy2): 
     Ensure xx1 <= xx2 and yy1 <= yy2 - swap them if you like 
     x1 = xx1, y1 = yy1, x2 = xx2, y2 = yy2 

    IS_INSIDE(rectangle r2): 
     IF r2.x1<=x1 && r2.y1<=y1 && y2 <= r2.y2 && x2 <= r2.x2: 
      RETURN TRUE 
     RETURN FALSE 

    IS_OUTSIDE(rectangle r2): 
     IF r2.x1 <= x1 <= r2.x2 || r2.x1 <= x2 <= r2.x2 || r2.y1 <= y1 <= r2.y2 || r2.y1 <= y2 <= r2.y2 : 
      RETURN FALSE 
     RETURN TRUE 

    IS_SEPARATE(rectangle r2): 
     IF IS_OUTSIDE(r2) && ! r2.IS_INSIDE(me): 
      RETURN TRUE 
     RETURN FALSE 

    IS_OVERLAPPED(rectangle r2): 
     IF ! IS_OUTSIDE(r2) && ! IS_INSIDE(r2): 
      RETURN TRUE 
     RETURN FALSE 

    IS_VERTICALLY_ALIGNED(rectangle r2): 
     IF (x1+x2)/2 = (r2.x1+r2.x2)/2: 
      RETURN TRUE 
     RETURN FALSE 

    IS_HORIZONTALLY_ALIGNED(rectangle r2): 
     IF (y1+y2)/2 = (r2.y1+r2.y2)/2: 
      RETURN TRUE 
     RETURN FALSE 

그러면 R1은 하나를 고정, R2 가정하면 가동 직사각형이고, R2가 유효하게 배치되어 있는지 매우 간단한 함수를 작성할 수 있고, 상자 캔버스의 바운딩 박스를 나타내는 미표시 직사각형 :

IS_VALID_PLACEMENT(r2, r1, box): 
    //In the bounding box 
    IF r2.IS_OUTSIDE(box): 
     RETURN FALSE 

    //Aligned with r1 
    IF ! r2.IS_VERTICALLY_ALIGNED(r1) && ! r2.IS_HORIZONTALLY_ALIGNED(r1): 
     RETURN FALSE 

    //Not overlapping r1 
    IF ! r2.IS_SEPARATE(r1): 
     RETURN FALSE 

    RETURN TRUE 

상자가 움직일 때마다 실행하십시오. false를 반환하면 이동을 취소하거나 경계 논리를 사용하여 지대치를 수행합니다.

편집하는 것은

나는 질문을 다시 읽고 있었다, 나는 수직 정렬의 당신의 정의를 발견했습니다. 완전히 할 수있는 :

IS_VERTICALLY_ALIGNED(rectangle r2): 
     IF x1 <= r2.x1 <= r2.x2 <= x2 || r2.x1 <= x1 <= x2 <= r2.x2: 
      RETURN TRUE 
     RETURN FALSE 

    IS_HORIZONTALLY_ALIGNED(rectangle r2): 
     IF y1 <= r2.y1 <= r2.y2 <= y2 || r2.y1 <= y1 <= y2 <= r2.y2: 
      RETURN TRUE 
     RETURN FALSE