관련글

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

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

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




 상자 채우기 문제 (bin packing problem)는 최소한의 공간에 최대한의 아이템을 채워넣는 문제로 NP-hard분류에 속한다.

 이 문제를 적용할 수 있는 것은 1차원(linear)에서는 메모리(segmentation) 관리,  2차원에서는 그래픽 리소스 최적화, 3차원에서는 화물 적재 등 주변에서 쉽게 찾아볼 수 있다.

 게임 텍스쳐들을 모아 놓는 스프라이트 시트(sprite sheet)제작 툴에 활용하기 위해 이 알고리즘을 구현해보게 되었다. 참고글 : (http://clb.demon.fi/files/RectangleBinPack.pdf)

 이 글의 마지막에는 JS와 html5 canvas로 구현한 코드를 첨부했다.

 테스트할 사각형들은 미리 무작위로 생성해놓았다.




Shelf 알고리즘

 가장 간단한 해결방법은 Shelf(선반) 알고리즘을 사용하는 것이다. 평행한 선반 위에 물건(이하 아이템)을 올려놓듯이 순서대로 배치하는 것이다. 아이템의 배치 순서를 결정할 때  다양한 휴리스틱(heuristic)들을 적용할 수 있다.


목차

1. Next Fit

2. Smaller Height First

3. Lager Height First

4. Rotate - 회전하기

5. Shelf 알고리즘의 한계

6. Javascript 코드



1. Next Fit

 아이템들을 특별한 기준 없이 순서대로 배치한다. 좌측 상단부터 시작하여 오른쪽으로 아이템들을 배치해나가다가 오른쪽 변에 다다르면 그 층(row)의 최대 높이만큼 내려서 배치한다.

아래 그림과 같이 상당히 비효율적인 것을 확인할 수 있다. 

그림1


의사코드로 작성해 보면 아래와 같다.

nextPos = {x:0, y:0}

for i from 0 to items.length

    if(nextPos + items[i].width > spaceWidth)

        nextPos.x = 0

        nextPos.y += maxHeight

        maxHeight = 0; //reset

    end if

    if(nextPos.y + items[i].height > spaceHeight)

        break;

    end if

    /*allocating item*/

    /*finding a value of max height in this row*/

end for







2. Smaller height first


 넣을 아이템을 높이가 작은 순서대로 정렬한다.

시간복잡도가 O(nlogn)인 정렬 알고리즘으로 정렬한다면, 아이템 배치 부분은 O(n)이므로 총 시간복잡도는 O(nlogn)이다.

 이 테스트케이스에 크기가 더 큰 아이템들도 있지만 더 이상 넣을 공간이 없으므로 끝나게 되었다.

그림2







3. Lager height first


넣을 아이템을 높이가 큰 순서대로 정렬한다. 1.2에서 적재되지 못했던 아이템들을 볼 수 있다. 큰 순서대로 배치하였기 때문에 아래층에 넓은 공간이 남아버리게 된다.



따라서 높이가 맞지 않는 다음 아이템은 건너뛰고, 그 다음 아이템을 적재한다.

1번에 있는 의사코드를 다음과 같이 고칠 수 있다.

if(nextPos.y + items[i].height > spaceHeight)

    ++i;

end if

그림3

이제 아래쪽 빈 공간을 활용할 수 있게 되었다.




그러나 아직도 우측에 빈 공간이 남게 되는데, 아이템의 너비를 생각하지 않고

높이순으로만 정렬했기 때문이다. 

현재 층(row)에서 다음 아이템을 너비 때문에 넣지 못할 경우, 잠시 멈춰 두고 넣을 수 있는 아이템이 나올 때까지 순차탐색한다.  최악의 경우(아이템의 너비가 내림차순으로 정렬되어 있을 때 등)에는 이 때문에 시간복잡도가 O(n^2)가 된다.

다음 층로 넘어갔을 때는 공간이 많이 있으므로 멈췄던 인덱스부터 다시 배치를 시작한다.



배열을 탐색하면서 중간요소들을 지워야 하기 때문에 뒤에서부터 탐색하였다.

그래서 이번에는 items 배열을 높이가 작은 순서대로 정렬해두어야 한다. 

nextPos = {x:0, y:0}

i - items.length

while(i--)

    for j from i to 0

        if(nextPos + items[j].width >= spaceWidth)

            break

        end if

    end for

    if(j>0)

        j = i;

        nextPos.x = 0

        nextPos.y += maxHeight

        maxHeight = 0

    end if

    if(nextPos.y + items[j].height > spaceHeight)

        continue

    end if

    /*allocating item*/

    /*finding a value of max height in this row*/

    items.splice(j,1)

end while

그림4







4. rotate - 회전하기


3번에 있는 휴리스틱을 적용하면 채우기 효율이 매우 완벽해 보인다. 그러나 이런 경우도 있다.

그림5

이 포스트에서 구현한 선반 알고리즘은 높이에 관계없이 한 층 안에서 여러 개의 아이템을 쌓을 수 없기 때문에 위와 같이 두가지 아이템의 높이 차이가 많이 날 경우 빈 공간이 많이 남을 수 있다.


이 문제를 해결하기 위해 사각형을 회전할 수 있다.

현재 쓰고 있는 휴리스틱이 높이 순서 기반으로 되어 있기 때문에 너비가 높이보다 큰 사각형은

90도 돌려서 적재한다. 회전된 아이템은 파란색으로 표시하였다.

그림6

그림5에서 남았던 우측의 빈 공간들은 메워졌으나, 아이템이 수직으로 길게 되어버려서 이번에는 아래쪽 공간이 낭비된다.


 이 공간을 활용하려면 아래쪽 선반을 검사할 때, 회전한 아이템을 다시 원래대로 돌려야 한다.

위에 있는 의사코드에서 해당 부분을 수정했다.

if(nextPos.y + items[j].height > spaceHeight)

    if(items[j].w <= h-p.y)

        swap(items[j].w, items[j].h)

    end if

    else continue

end if

그림7


이제 두 가지 아이템의 크기가 다를 때 나타날 수 있는 문제도 해결된 것처럼 보인다!


한 가지 주의할 점은 회전을 쓸 수 없는 상황도 많다는 것이다. 이미지 리소스를 이 방식으로 저장해 두었다가 불러들일 때 적은 연산으로 다시 90도 복구할 수 없는 상황이라면 회전하지 않고 저장하는것이 더 나을 수도 있다.

그렇지만 OpenGL 등에서는 텍스쳐를 바인딩할 때 텍스쳐 좌표를 자유롭게 지정할 수 있으므로 문제가 되지 않는다. 저장할 이미지 리소스의 정보 파일에 x,y,w,h 및 회전 여부도 같이 저장해 두면 된다.





5. Shelf 알고리즘의 한계


4번까지의 결과를 보면 효율이 나쁠 수 있는 상황에서도 어느 정도 만족할 만한 해답을 이끌어낸 것 같다. 그러나 이 글에서 작성한 Shelf 알고리즘은 한 층 안에서 아이템을 수직으로 쌓을 수 없다는 결점이 있다.

가령 아래와 같이 사각형들의 크기차이가 심할 경우 그 차이만큼의 공간이 낭비될 수밖에 없다.

그림8


이 문제를 개선하려면 단순히 층을 나눠서 아이템을 적재하는 대신에

빈 공간에 대한 정보를 전체적으로 관리할 필요가 있다.

하지만 아이템의 크기가 다양하다면 빈 공간의 정보도 자잘하게 조각나서 매우 많아질 것이기 때문에 역시 문제가 된다.


다음 포스트에서 빈 공간의 정보를 최적화하는 Maxrects (Maximal rectangle) 알고리즘에 대해 알아본다! 



▽ Maxrects 알고리즘으로 그림8에서 사용했던 테스트케이스를 실행한 결과






6. Javascript code

이미지를 그리기 위해 작성한 자바스크립트 코드.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
<html>
    <meta charset="utf-8">
    <body>
    <canvas id="canvas1", width=256, height=256, style="border:1px solid #000000"></canvas>
    <script type = "text/javascript">
        var c = document.getElementById("canvas1");
        var ctx = c.getContext("2d");
 
        //var testCase = [11, 21, 43, 39, 13, 52, 35, 25, 28, 20, 66, 55, 54, 62, 50, 61, 49, 16, 60, 51, 39, 27, 54, 62, 65, 13, 34, 50, 48, 63, 19, 41, 18, 61, 23, 51, 39, 58, 35, 14, 35, 31, 67, 58, 25, 24, 58, 63, 59, 57, 69, 57, 34, 28, 61, 30, 18, 57, 10, 26, 42, 66, 31, 50, 63, 13, 42, 10, 57, 63, 61, 54, 50, 53, 20, 54, 66, 31, 48, 35, 28, 25, 37, 54, 32, 50, 42, 49, 62, 37, 31, 24, 63, 44, 66, 29, 25, 51, 52, 17, 67, 55, 27, 48, 23, 39, 38, 41, 46, 15, 46, 68, 24, 41, 38, 20, 33, 42, 12, 12, 51, 31, 53, 41, 25, 28, 39, 69, 61, 12, 55, 59, 35, 60, 13, 60, 22, 41, 60, 68, 28, 33, 31, 60, 27, 48, 38, 60, 19, 63, 28, 50, 24, 31, 42, 38, 11, 17, 50, 36, 27, 59, 42, 25, 16, 61, 35, 19, 32, 67, 40, 53, 33, 42, 15, 40, 62, 23, 42, 19, 57, 42, 43, 59, 12, 10, 45, 68, 16, 15, 15, 34, 67, 33, 27, 54, 53, 64, 18, 22];
        
        //var testCase = [20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,6,15,6,15,6,15,6,15,6,15,6,15,6,15,6,15,6,15,15,6,15,6,15,6,15,6,15,6,15,6,15,6,15,6,15,6,15,6,15,6];
        
        //var testCase = [10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11];
 
        var testCase = [160,160,80,80,80,80,60,60,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10];
 
        //var testCase = [67,75,67,75,67,75,67,75,67,75,67,75,67,75,67,75,67,75,67,75,67,75,67,75,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11];
 
        var numCase = testCase.length/2;
 
 
        var w = c.width;
        var h = c.height;
 
        var r = new Array();
        var s = new Array();
        for(var i = 0; i<numCase; i++) {
            r[i] = {};
            r[i].w = testCase[i*2];
            r[i].h = testCase[i*2+1];
            r[i].r = false;
 
            //rotation
            if(r[i].w > r[i].h) {
                var temp = r[i].w;
                r[i].w = r[i].h;
                r[i].h = temp;
                r[i].r = true;
            }
        }
        s.push({x:0, y:0, w:w, h:h, v:true});
 
        //sorting
        for(var i=0; i<numCase-1; i++) {
            for(var j=0; j<numCase-1-i; j++) {
                if(r[j].h > r[j+1].h) {
                    var temp = r[j];
                    r[j] = r[j+1];
                    r[j+1] = temp;
                }
            }
        }
        var u = 0; //used space
        var p = {x:0, y:0}; //next point
        var m = 0; //max height
        var i = r.length;
        var j;
        while(i--) {
            //find item for next column
            for(j=i; j>=0; j--) {    
                if(r[j].w <= w-p.x) {
                    break;
                }
            }
            //go to the next row
            if(j<0) {
                j=i;
                p.x = 0;
                p.y += m;
                m=0;
            }
 
            //find item for bottom of space
            if(r[j].h > h-p.y) {
                if(r[j].w <= h-p.y) {
                    var temp = r[i].w;
                    r[i].w = r[i].h;
                    r[i].h = temp;
                    r[i].r = false;                    
                } 
                else continue;
            }
 
            //draw
            var fillStyle;
            if(r[j].r) fillStyle = "#6699CC";
            else fillStyle = "#CC6699";
            drawRect(ctx, {
                x:p.x,
                y:p.y,
                w:r[j].w,
                h:r[j].h}, fillStyle);
            p.x += r[j].w;
            u += r[j].w*r[j].h;
            if(r[j].h>m) m=r[j].h;
 
            //remove item from array
            r.splice(j,1);
        }
        //efficiency
        var e = Math.floor(u/(w*h)*10000)/100; 
        ctx.font="20px Consolas";
        ctx.fillStyle = "#000000";
        ctx.fillText(e+"%",w-70,h-18);


function drawRect(ctx, rect, fillStyle) { ctx.beginPath(); ctx.rect(rect.x, rect.y, rect.w, rect.h); ctx.fillStyle = fillStyle; ctx.fill(); ctx.stroke(); }
    </script>
    </body>
</html>
cs







관련글

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

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

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








+ Recent posts

티스토리툴바