상자 채우기 (2D bin packing) - (2) Maxrects 알고리즘①

에서 이어지는 포스트입니다.



지난 글에서의 순서를 다시 보면 아래와 같다.


1. 넣을 아이템을 불러온다

2. 남은 공간들 중에서 아이템을 넣을 수 있는 공간을 선택한다. (다양햔 휴리스틱 존재)

3. 해당 공간에 아이템을 넣는다.

4. 넣은 아이템과 겹치는 모든 공간들을 검사한다

5. 넣은 아이템과 겹치는 공간을 분할한다

6. 유효하지 않은 공간을 제거한다. (다른 공간 안에 포함된 공간이나, 높이나 너비 값이 음수인 공간.)

7. 넣을 아이템이 남아있으면 (1)로 돌아간다.


3,4,5,6 번 과정을 그림으로 그려봤을 때


아래 그림은

item1이 넣어져 있는 상태에서 남은 공간은 A와 B로 나누어져 있고,

item2를 넣는 상황이다.

[그림6]

위 그림과 같이 공간 A는 item2에 의해 3개의 새로운 공간으로 나위며

공간 B는 2개의 새로운 공간으로 나뉜다.



그러면 기존 A, B 공간은 사라지고 새로운 5개의 공간이 생기게 된다.

[그림7]




마지막으로, 공간들 사이에 포함관계가 있는 것을 찾아 제거하여 최적화를 한다.

[그림8]




 코드로 작성할 때는 넣을 아이템들의 정보와 분할될 공간들의 정보를 선형적으로 탐색하도록 코드를 작성할 것이기 때문에 링크드 리스트(linked list)구조를 사용하였다. 


 5번 단계를 보면, 아이템과 겹치는 부분이 있는 공간 하나당 0~3개의 새로운 나눠진 공간이 생길 수 있다. 새로 생긴 공간들을 임시 리스트에 넣어두고, 기존에 겹쳤던 공간은 제거한다. 의사코드로 쓰면 아래와 같다.

width>0, height>0 부분은 크기가 음수로 되어 있어 유효하지 않은 공간이 생기는 것을 방지하는 것이다.


for s in spaceList

    if isIntersect(item, s) {

        s_top, s_right, s_bottom, s_left 생성

        if(s_top.width>0 && s_top.height>0) newList.push(s_top)

        if(s_right.width>0 && s_right.height>0) newList.push(s_right)

        if(s_bottom.width>0 && s_bottom.height>0) newList.push(s_bottom)

        if(s_left.width>0 && s_left.height>0) newList.push(s_left)

        spaceList.erase(s)

    }

}


이제 새로운 공간 리스트 (newList)를 기존 리스트(spaceList)와 병합해야 하는데

그 전에 [그림8]처럼 최적화를 해야 한다.

다음과 같은 4가지 조건을 생각해 볼 수 있다.


1. 기존 공간들 간의 포함관계

2. 기존 공간이 새로운 공간을 포함하는 경우

3. 새로운 공간이 기존 공간을 포함하는 경우

4. 새로운 공간 간의 포함관계


여기서 1번은 이 최적화과정이 item을 하나 넣을 때 마다 일어나므로 발생하지 않고, 

3번 또한 발생하지 않아서 고려하지 않아도 된다


2번과 4번의 경우 공간을 제거하여 최적화한 뒤,

newList를 기존 리스트 뒤에 병합하면 된다.



다음은 적용예이다.


적용 예시

아이템들이 모두 같은 크기인 경우

*'잔여 면적'은 적재하지 못한 아이템들의 면적입니다.

[그림9]





작은 아이템부터 큰 아이템까지 고르게 있는 경우

아이템들이 비효율적으로 적재되며 모든 아이템을 넣는 것도 실패한다.

[그림10]

*'잔여 면적'은 적재하지 못한 아이템들의 면적입니다.





작은 아이템부터 큰 아이템까지 고르게 있는 경우

+ 큰 아이템부터 내림차순으로 정렬

아이템을 면적으로 내림차순 정렬하면 공간의 단편화가 적어져서 연산 횟수가 줄어들고, 공간을 효율적으로 차지하게 된다. (정렬은 O(nlogn)으로 할 수 있으므로..)

[그림11]

*'잔여 면적'은 적재하지 못한 아이템들의 면적입니다.






같은 크기의 아이템 집단이 있을 때

이 알고리즘을 알아보게 되었던 목적이 게임 그래픽 리소스 패킹을 위해서였는데,

그 때 가장 많이 볼 수 있을 경우로,

아이템들이 모두 같은 크기일 때처럼 공간을 빼곡히 차지할 수 있다.

[그림12]

*'잔여 면적'은 적재하지 못한 아이템들의 면적입니다.






무작위 + 정렬

이전 포스트에서의 shelf 알고리즘보다 더 좋은 공간효율을 보여준다.

하지만 전체공간의 크기가 고정되어 있어서 모든 아이템들을 넣을 수 없는데,

이 전체공간의 크기를 PO2로 늘려 주는 부분을 다음다음 글에서 작성할 것이다.

[그림13]

*'잔여 면적'은 적재하지 못한 아이템들의 면적입니다.






아이템의 수와 연산횟수의 관계

단위연산은 정렬 시 비교연산 수,

넣을 공간을 찾을 때의 검사 수,

분할할 공간을 찾을 때의 검사 수,

포함관계에 있는 공간을 찾을 때의 검사 수를 더한 것으로 정했다.



아래 그래프에서처럼 아이템이 적을 때는, 아이템의 수가 늘어날수록 연산횟수의 변화율이 커지지만, 일정 수 이상에서는 선형적인 모양이 나온다.

공간을 점점 채워갈수록 고려해야 할 공간의 수가 더이상 늘어나지 않기 때문이다.

따라서 아이템에 비해 상대적으로 충분히 큰 공간을 두고 공간에 아이템이 50%정도 채워질 때까지를 봐야 한다.



[그림14] 가로축은 아이템의 수, 세로축은 연산횟수이다





그렇게 하면 아이템의 수에 따른 연산횟수가 점근적으로 O(n^2)에 근사하는 것을 볼 수 있다.


[그림15] 가로축은 아이템의 수, 세로축은 연산횟수이다




소스코드


GitHub gist에서도 볼 수 있습니다.

https://gist.github.com/tibyte/c0ef27311005e0f2476d


 mxrc3_1.html




관련글

상자 채우기 (2D bin packing problem) - (1) Shelf 알고리즘

상자 채우기 (2D bin packing problem) - (2) Maxrects 알고리즘①




참고글 : http://clb.demon.fi/files/RectangleBinPack.pdf








+ Recent posts