이전 글
상자 채우기 (2D bin packing problem) - (1) Shelf 알고리즘
에서 이어지는 포스트입니다.
Maxrects(Maximal Rectangle)알고리즘
목차
1. 원리
2. First Fit
3. Best Fit
4. Maxrects-CP
이전 글에서의 문제점을 해결하기 위해서는 남은 공간의 정보를 저장해 두어야 한다.
처음 공간에 아이템이 하나 배치됐을 때 아래와 같은 3개의 영역이 생긴다.
그림1
그런데 위와 같이 세 부분으로 나누면 단편화(fragmentation)가 심해져서 크기가 큰 아이템을 추가로 넣을 수 없다.
따라서 두 부분으로 나누어야 하는데 아래 그림처럼 2가지 선택지가 있다. 이렇게 나누는 방법을 Guillotine Algorithm이라고 한다.
그림2
하지만 여전히 단편화 현상이 나타나게 된다. 왼쪽 그림에서 B영역과, 오른쪽 그림에서 A영역을 보면 알 수 있다.
따라서 두 공간을 직사각형 모양을 유지하며 최대한으로 확장하여 사용한다.
그림3
여기서 새 아이템을 넣을 때 아이템이 공간A와 공간 B 모두에 겹치는(intersect) 경우가 대부분이다.
겹치는지 아닌지를 판별하는 방법은 http://tibyte.kr/228 이 포스트의 return null 조건 참고.
그림4
다음 단계에서 공간A와 공간B 모두에 대해 새로운 공간을 다시 생성해야 하므로
상하좌우 4방향 모두 고려해야 한다.
그림5
그림에서 흰 부분이 아이템이고, 색이 칠해진 부분이 남은 공간이다.
속성으로 x, y ,w, h 값을 가지는 rectangle객체가 있다고 할 때
위 4개의 남은공간을 나타내는 rectangle객체는 쉽게 얻을 수 있다.
//r은 아이템, s는 아이템과 겹치는 공간.
rt = {x:s.x , y:s.y , w:s.w , h:r.y-s.y } //top
rb = {x:s.x , y:r.y+r.h , w:s.w , h:s.y+s.h-(r.y+r.h)} //bottom
rl = {x:s.x , y:s.y , w:r.x-s.x , h:s.h } //left
rr = {x:r.x+r.w , y:s.y , w:s.x+s.w-(r.x+r.w) , h:s.h } //right
위 rt, rb, rl, rr 객체 중에서 w(width)나 h(height)속성값이 음수인 객체는 지우면 된다.
▽ 자바스크립트와 canvas로 구현한 결과. 마우스로 조절점을 드래그해보세요.
(※인터넷 익스플로러 9이상 필요)
이제 Maxrects알고리즘으로 bin packing을 하는 단계를 보면 아래와 같다.
이번 포스트에서는 (4)번과 (5)번을 알아보았다.
(1) 넣을 아이템을 불러온다
(2) 남은 공간들 중에서 아이템을 넣을 수 있는 공간을 선택한다. (다양햔 휴리스틱 존재)
(3) 해당 공간에 아이템을 넣는다.
(4) 넣은 아이템과 겹치는 모든 공간들을 검사한다
(5) 넣은 아이템과 겹치는 공간을 분할한다
(6) 유효하지 않은 공간을 제거한다. (다른 공간 안에 포함된 공간이나, 높이나 너비 값이 음수인 공간.)
(7) 넣을 아이템이 남아있으면 (1)로 돌아간다.
참고로 실제 리소스 패킹 목적으로 구현할 때는 위 순서중 (2)번에서, 적당한 공간이 없으면 전체영역의 크기를 확장해야 한다.
다음 포스트에서 이어집니다..
이전글
상자 채우기 (2D bin packing problem) - (1) Shelf 알고리즘
다음글
상자 채우기 (2D bin packing problem) - (3) Maxrects 알고리즘②
참고글 : http://clb.demon.fi/files/RectangleBinPack.pdf