Sep
1
Automatic Magazine Layout
Filed Under Blog, News, Papermodels, Web2.0 | Leave a Comment
Flipboard를 접하고 나서 비슷한 효과를 낼 수 있는 방법에 관심을 가졌습니다. 지난 글에서는, 트랜지션 효과를 표현한 Quicksand와, 글에서는 남기지 않았지만, 바둑판 모양의 미리 설정된 격자를 이용한 Blueprint을 사용하여, 전개도들을 동적으로 정렬해주는 간단한 실험결과를 남겼습니다.
이번에는, 매거진 스타일로 정렬해주는 기능을 구현하는 것에 관해서 남길까 합니다.
사실 이런 기능에 대해서 웹검색을 시작했을때는, (회원 포인트나 도면 다운로드수에 따라서) 크기가 다른 이미지들의 모자이크 배열을 위한 코드를 찾으려고 했었는데, 어짜피 목표는 정해진 크기 (가로만, 또는 가로 세로 모두)의 박스에 여러 크기의 이미지/글문단을 잘 배열하는 것이기에 비슷한 시도들이 검색되었습니다.
BEFORE AFTER (from A List Apart)
우선, 가장 직관적이고, 아마 최초의 시도로서 A List Apart의 ‘Automatic Magazine Layout’이라는 글에서 제안하는 이미지 layout 방법입니다. 접근방법은, 입력 이미지 갯수는 2~4개로 한정하고 가능한 총 6개의 layout들을 정해놓고, 1) 이미지 갯수와 이미지들의 가로/세로 비율들에 따라서 적당한 layout을 선택하고, 
2) 선택된 layout에 잘 들어가도록 이미지들의 축소(확대)비율을 결정하는 것입니다. 이미지가 5개 이상인 경우는, 3+2로 나누어서 각각 적용하는 형태입니다. php 코드는 위 페이지에서 다운 받을 수 있으며, GD2.x가 필요합니다.
두번째 접근방법은, 보다 일반적인 문제를 해결하기 위한 방법으로, 여러 크기의 사각형들을 잘 배열하여 전체를 담을 수 있는 사각형의 크기를 작게 만드는 문제입니다. 이 문제는 NP-Complete로 증명된, 즉, 최적해를 구하기는 매우 어려운 문제이고, 최적해에 가까운 답을 빠른 시간안에 찾기위한 휴리스틱들이 존재합니다. (참조: Stackoverflow의 Optimal Layout Algorithm 쓰레드) 이 문제는, 2D bin packing 또는 rectangle packing 문제라고 정의되며, 전통적으로는 Operations Research에서 상품 보관/운송에서 비용을 최소화하는 문제입니다.
게임쪽에서는, 텍스쳐/폰트정보를 저장하는 이미지맵을 최소한으로 만들기 위해서, 그리고, 웹 분야에서는, 데스크탑, 스마트폰, 태블릿 등 여러가지 크기의 디스플레이에, 원래의 의미 (예를 들어 읽는 순서)를 최대한 유지한채 layout을 조정해야 하는 필요가 대두된것입니다. 재밌는 것은, 출판 만화의 칸 구분과 배치가 Manga layout 이라는 이름으로, video summarization 분야에서 사용된 다는 점입니다. 물론 출판 만화에서 만화가가 의도적으로 배치한 것을 자동으로 처리하는 것이 목적이고요.
이 문제정의는, 단순히 웹 layout뿐만 아니라, 전개된 도면의 배치에서도 풀어야 할 문제입니다.
(Blender plug-in: Export paper model)