랩핑 된 좌표로 양방향으로 유한 한 2D 공간이 있습니다. (왼쪽으로 가면 오른쪽 가장자리로 갈 것이고 위쪽/아래쪽으로가는 경우도 마찬가지입니다).wrap 된 2D 공간에 상자 집합을 둘러싸는 가장 작은 경계 상자
또한 축에 정렬 된 상자 세트가 있습니다. 이 박스들은 공간 내부에 플로트 좌표를 가지고 있습니다.
문제점 : 모든 상자를 둘러싸는 축에 정렬 된 최소 경계 상자 찾기. 경계 상자 포장하십시오.
샘플 :
이
A는 청소 알고리즘을 사용할 수 있습니다
(핑크 동봉해야 할 공간의 경계, 빨간색 상자이고, 파란색 테두리는 의미 가능한 가장 작은 경계 상자)이를 찾을 수 가장 큰 수직 간격, 즉 상자 사이에 상자가없는 가장 먼 두 개의 수직선.
마찬가지로, 스위핑 알고리즘을 사용하여 가장 큰 수평 간격을 찾을 수 있습니다. 분명히 두 틈이 모서리를 감쌀 수 있습니다.
2D 공간에서 틈을 제거하여 남겨진 모양은 모든 상자를 포함하는 최소 경계 상자입니다. 영역이 포함 된 모든 상자 중이 보장되는지는 확실치 않지만 이 모두 크기보다 작은 경계 상자는 없습니다. 존재한다면 두 개의 갭 (수직 방향 & 수평)이 최대 값보다 큽니다.
두 갭을 모두 탐지하는 스위핑은 O (N * log N)에서 수행 할 수 있습니다. 여기서 N은 상자의 수입니다.
경계 박스로 둘러싸인 면적의 %가 될 것이다 = (수평 경계로 둘러싸인 수평 범위 %), 수직 범위 (* %의 바운딩 박스에 의해 둘러싸인 면적의
퍼센트 수직으로 둘러싸 범위)
분명히 고려해야 할 사항. 따라서 총 면적을 최소화하기 위해 수평 및 수직 경계를 독립적으로 최소화 할 수 있습니다.
수평 경계를 최소화하려면 한 사각형의 오른쪽 가장자리와 다음 왼쪽 가장자리 사이에 가장 큰 간격을 찾아야합니다. 모든 가장자리 (왼쪽 및 오른쪽)를 단일 목록으로 정렬하고이를 반복하여 왼쪽으로 이동할 때 카운트를 증가시키고 오른쪽으로 이동할 때 감소시킵니다. 가장 큰 차이는 x 값이 0에서 1로 갈 때 가장 큰 차이입니다. 랩 어라운드 경우를 특별히 처리해야합니다. 사각형을 수평으로 한 번 반복하고 너비만큼 간격을 띄우면 쉽게 할 수 있습니다 총 면적의. 또한 시작시 카운트를 초기화 할 때 랩핑 된 사각형을 고려해야합니다.
그런 다음 세로 경계에 대해서도 마찬가지입니다.