(57)【要約】【課題】詰め込み問題として、複数の部品の最適な配置（レイアウト）決定を、高速かつ効率的に探索する。【解決手段】サイズと縦横比の属性を持つ矩形オブジェクトである部品を、矩形ボックスに詰め込む部品レイアウト方法であって、部品を面積降順で一つずつ矩形ボックスに詰め込み、矩形ボックスを根とし、葉の空間に部品を配置して二分木となる分割木を構築するステップと、矩形ボックス内に詰め込まれた部品を包含する境界ボックス内で部品が移動可能な最大スペースである隙間について、該隙間の情報を面積降順で保持し、全ての部品を隙間に詰め込むまで、隙間の情報を更新するステップとを有する。【選択図】図１
2011113509.tif 000002
【特許請求の範囲】
【請求項１】
サイズと縦横比の属性を持つ矩形オブジェクトである部品を、矩形ボックスに詰め込む部品レイアウト方法であって、
前記部品を面積降順で一つずつ前記矩形ボックスに詰め込み、前記矩形ボックスを根とし、葉の空間に前記部品を配置して二分木となる分割木を構築するステップと、
前記矩形ボックス内に詰め込まれた前記部品を包含する境界ボックス内で前記部品が移動可能な最大スペースである隙間について、該隙間の情報を面積降順で保持し、全ての前記部品を前記隙間に詰め込むまで、前記隙間の情報を更新するステップと、
を有することを特徴とする部品レイアウト方法。
【請求項２】
サイズと縦横比の属性を持つ矩形オブジェクトである部品を、矩形ボックスに詰め込む部品レイアウト方法であって、
前記部品を面積降順で一つずつ前記矩形ボックスに詰め込み、前記矩形ボックスを根とし、葉の空間に前記部品を配置して二分木となる分割木を構築するステップと、
前記矩形ボックス内に詰め込まれた前記部品を包含する境界ボックス内で前記部品が移動可能な最大スペースである隙間について、該隙間の情報を面積降順で保持し、前記部品を前記隙間に詰め込むステップと、
前記隙間に前記部品が詰め込めない場合に、前記境界ボックス外のスペースである未充填領域を前記分割木から探索して、該未充填領域に前記部品を詰め込むステップと、
全ての前記部品を前記隙間又は前記未充填領域に詰め込むまで、前記隙間の情報を更新するステップと、
を有することを特徴とする部品レイアウト方法。
【請求項３】
前記未充填領域の大きさが前記部品の詰め込みに不足する場合には、前記未充填領域を拡大して前記部品を詰め込むステップを有することを特徴とする請求項２記載の部品レイアウト方法。
【請求項４】
前記部品を前記矩形ボックスに詰め込む処理は、前記矩形ボックスを縦横比固定したままサイズを任意に拡大しつつ、前記矩形ボックスのサイズを最小化するように詰め込むことを特徴とする請求項１乃至３のいずれか１項に記載の部品レイアウト方法。
【請求項５】
前記隙間の情報は、平衡木で保持することを特徴とする請求項１乃至４のいずれか１項に記載の部品レイアウト方法。
【請求項６】
全ての前記部品を前記矩形ボックスに詰め込んだ後、前記矩形ボックスを、表示装置の表示画面サイズにリサイズし、構築された分割木のＴＯＰ−ＤＯＷＮ順に沿って、前記部品の座標を視座標系で計算するステップを有することを特徴とする請求項１乃至５のいずれか１項に記載の部品レイアウト方法。
【請求項７】
サイズと縦横比の属性を持つ矩形オブジェクトから成る部品のデータを記憶した記憶手段と、前記記憶手段に接続された部品レイアウト生成手段と、前記部品レイアウト生成手段に接続された出力手段とを有する部品レイアウトシステムであって、
前記部品レイアウト生成手段は、前記部品を面積降順で一つずつ前記矩形ボックスに詰め込み、前記矩形ボックスを根とし、葉の空間に前記部品を配置して二分木となる分割木を構築し、
前記矩形ボックス内に配置された前記部品を包含する境界ボックス内で、前記部品が移動可能な最大スペースである隙間についての情報を面積降順で保持して、前記部品を前記隙間に詰め込み、
前記隙間に前記部品が詰め込めない場合に、前記境界ボックス外のスペースである未充填領域を確保して、当該未充填領域に前記部品を詰め込み、
全ての前記部品を詰め込むまで、前記隙間の情報を更新することによりレイアウトを決定し、
前記矩形ボックスを前記出力手段の表示画面サイズにリサイズし、前記分割木のＴＯＰ−ＤＯＷＮ順に沿って、前記部品の座標を視座標系で計算して生成されるデータを前記出力手段に出力させることを特徴とする部品レイアウトシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、部品レイアウト方法及びそのシステムに係り、特に複数の部品を矩形領域にレイアウトする部品レイアウト方法及び部品レイアウトシステムに関する。
【背景技術】
【０００２】
デジタル情報量の増大に伴い、大量の情報を一画面に重ならないように表示し、全体を俯瞰しながら重要な情報を容易に発見できる視覚化技術の重要性が高くなっている。部品で表現される大量の情報を矩形領域内にレイアウトする手法は、いわゆる詰め込み問題と呼ばれ、その解決手法は、ＶＬＳＩの設計、フロアプランの策定、工業用母材の最適利用化などに応用されている。
【０００３】
限られたスペース（画面）を最大限に利用して、全てのデータを視覚化する技術として、treemapがよく使われている。treemapはデータごとの属性（例えば、重要度）を画面に占める面積にマッピングして全てのデータを一画面に表示する。一画面に各データの占めるスペースを割り当てるため、縦横比を維持したいとの要求を満たすことができない。
【０００４】
そこで、画面上におけるデータ（画像）の配置を工夫した提案がなされている（例えば、特許文献１参照。）。
【０００５】
これは、評価関数をベースに、個々のデータを矩形から成る部品として配置する方法で、全てのデータを、相対的なサイズと縦横比を維持しながら、１画面における総部品の占める面積を最大になるようにレイアウトするものである。
【０００６】
また、面積の大きい部品から順にレイアウトする手法が提案されている（例えば、特許文献２参照。）。これは、面積順に従って１つの印刷用紙にレイアウトして印刷するためのレイアウト候補を作成して、ベストレイアウトを選ぶものである。詰め込み問題の最適解を求める手法の１つであるテンプレート法は、有限のテンプレートを事前に用意して、実のデータを用いて、最適テンプレートを選択するものである。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００８−３０１２６４号公報
【特許文献２】特開２００７−２９９２８６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上記した特許文献１の技術は、評価関数をベースに最適解に近いレイアウトを探すことを行うもので、計算複雑度がＯ(Ｎ^３)（Ｎはデータ数）となり、データ数が増えれば配置を完了させるまでのパフォーマンスに影響を与える。
【０００９】
また、特許文献２の技術では、予め多くのレイアウト候補（テンプレート）を用意する必要がある。部品数の増加により、無限に近いレイアウト候補を有限のテンプレートに適応させるため、誤差が大きくなるだけでなく、テンプレートの数が増えるので、選択も容易でない。
【００１０】
このように、部品数の増加により、詰め込み問題の最適解を得るために要する計算量は爆発的に増え（累乗で増える）、パフォーマンスがボトルネックになる。
【００１１】
一方において、情報を視覚化する分野においては、ユーザの操作とほぼ同時に表示できる配置性能が要求される。
【００１２】
そこで、本発明は、上記した問題に鑑みてなされたもので、詰め込み問題として、複数の矩形オブジェクトの矩形ボックスへの最適な配置（レイアウト）決定を、高速かつ効率的に探索する部品レイアウト方法および部品レイアウトシステムを提供するものである。
【課題を解決するための手段】
【００１３】
本発明の一態様によれば、サイズと縦横比の属性を持つ矩形オブジェクトである部品を、矩形ボックスに詰め込む部品レイアウト方法であって、前記部品を面積降順で一つずつ前記矩形ボックスに詰め込み、前記矩形ボックスを根とし、葉の空間に前記部品を配置して二分木となる分割木を構築するステップと、前記矩形ボックス内に詰め込まれた前記部品を包含する境界ボックス内で前記部品が移動可能な最大スペースである隙間について、該隙間の情報を面積降順で保持し、全ての前記部品を前記隙間に詰め込むまで、前記隙間の情報を更新するステップと、を有することを特徴とする部品レイアウト方法が提供される。  
また、本発明の別の一態様によれば、サイズと縦横比の属性を持つ矩形オブジェクトである部品を、矩形ボックスに詰め込む部品レイアウト方法であって、前記部品を面積降順で一つずつ前記矩形ボックスに詰め込み、前記矩形ボックスを根とし、葉の空間に前記部品を配置して二分木となる分割木を構築するステップと、前記矩形ボックス内に詰め込まれた前記部品を包含する境界ボックス内で前記部品が移動可能な最大スペースである隙間について、該隙間の情報を面積降順で保持し、前記部品を前記隙間に詰め込むステップと、前記隙間に前記部品が詰め込めない場合に、前記境界ボックス外のスペースである未充填領域を確保して、該未充填領域に前記部品を詰め込むステップと、全ての前記部品を前記隙間又は前記未充填領域に詰め込むまで、前記隙間の情報を更新するステップと、を有することを特徴とする部品レイアウト方法が提供される。
【発明の効果】
【００１４】
本発明によれば、複数の矩形オブジェクトをレイアウトする際のパフォーマンスを向上させることが出来、リアルタイムに大量のデータを視覚化させることができる。
【図面の簡単な説明】
【００１５】
【図１】本発明の実施形態に係る部品レイアウトシステムの構成例を示す部品図である。
【図２】部品レイアウト生成装置の概略構成を示す機能部品図である。
【図３】分割木の構築を説明する図である。
【図４】部品レイアウト計算部におけるレイアウト処理の流れを示すフローチャートである。
【図５】分割木を構築する初期状態を示す図である。
【図６】部品Ｂ１を画面に詰め込んだ状態を示す図である。
【図７】部品Ｂ２を画面に詰め込んだ状態を示す図である。
【図８】部品Ｂ３を画面に詰め込んだ状態を示す図である。
【図９】部品Ｂ４を画面に詰め込んだ状態を示す図である。
【図１０】部品Ｂ５を画面に詰め込んだ状態を示す図である。
【図１１】子ノードペアを持つ親ノードのサイズ計算を説明する図である。
【図１２】隙間リストが、平衡木で保持されることを説明する図である。
【図１３】仮想画面をリサイズして、未充填領域を確保する処理の流れを示すフローチャートである。
【図１４】未充填領域のサイズ計算を説明する図である。
【図１５】仮想画面のリサイズ方法を説明する図である。
【図１６】部品の座標の計算を説明する図である。
【発明を実施するための形態】
【００１６】
以下、本発明の一実施の形態について、図面を参照して説明する。尚、各図において同一箇所については同一の符号を付すとともに、重複した説明は省略する。
【００１７】
本発明は、所定の領域である矩形ボックス内に、複数の部品（矩形オブジェクト）を、相対サイズ（幅、高さ）と縦横比を維持しながら、面積降順に１つずつ詰め込んでレイアウトするものである。矩形ボックスは、例えば、所定の表示領域を有する携帯電話機の液晶ディスプレイや、モニタ等のディスプレイ装置が該当する。
【００１８】
図1は、本発明の実施形態に係る部品レイアウトシステムの構成例を示す部品図である。図１に示すように、部品レイアウトシステム１は、部品レイアウト生成装置１０と、部品レイアウト生成装置１０に接続された記憶装置２０と、部品レイアウト生成装置１０に接続された出力装置３０とを備えている。部品レイアウト生成装置１０、記憶装置２０、出力装置３０は必ずしもそれぞれ別の装置でなくともよい。例えば、部品レイアウト生成装置１０、記憶装置２０はパーソナルコンピュータ、出力装置３０はパーソナルコンピュータに接続されたモニタとすることができる。
【００１９】
記憶装置２０は、部品を生成する元となる複数のデータを記憶保持しており、それらのデータを部品レイアウト生成装置１０に出力する機能を有する。記憶装置２０は、例えば、ＨＤＤレコーダ、ＤＶＤプレーヤ、ハードディスク記憶装置などである。ここで、「データ」は静止画像でも動画でもよく、静止画には、文書作成ソフトウエアで作成された電子文書も含まれる。
【００２０】
出力装置３０は、部品レイアウト生成装置１０が出力したレイアウト後の部品をユーザが画像として視認可能な内容で出力する装置である。例えば、液晶ディスプレイ装置、プリンタ装置、携帯電話機などである。
【００２１】
部品レイアウト生成装置１０は、記憶装置２０から入力されたデータから、複数の部品を生成し、各部品の大きさができる限り大きくなるように部品のレイアウトを決定し、各部品間の隙間が小さくなるように各部品サイズを調整したレイアウトデータを出力装置３０に出力する。
【００２２】
部品レイアウト生成装置１０は、演算処理装置（ＣＰＵ）４０、主メモリ（ＲＡＭ）５０、読出し専用メモリ（ＲＯＭ）６０、入力装置（例えば、キーボード、操作パネルなど）７０、必要な場合にはハードディスク装置等の外部記憶装置（図示しない）を具備している。例えば、コンピュータ、ワークステーションなどの情報処理装置、或いは家電製品に搭載可能なマイクロコンピュータなどである。演算処理装置（ＣＰＵ）４０、主メモリ（ＲＡＭ）５０、読出し専用メモリ（ＲＯＭ）６０、及び入力装置７０はバス８０を介して互いにデータの受け渡しが可能に接続されている。また、バス８０にはグラフィック・ボード９０が接続されており、グラフィック・ボード９０は、ＣＰＵ４０からの制御に従ってレイアウトを表示させるため、例えば、ビットマップ形式の画像データを生成する。ＲＯＭ６０、若しくは外部記憶装置（図示しない）などに、情報処理装置を部品レイアウト生成装置１０として機能させるためのプログラム、又はレイアウト生成方法をコンピュータに実行させるためのプログラムが記憶されており、このプログラムを主メモリ５０上に載せ、ＣＰＵ４０がこれを実行することにより部品レイアウト生成装置１０が実現され、若しくはレイアウト生成方法が実行される。
【００２３】
次に、以上のように構成された部品レイアウトシステムによるレイアウト生成について説明する。
【００２４】
まず、本実施形態で用いる主要な用語について説明する。
【００２５】
「部品」とは、分割された矩形区間に置かれる、縦横のサイズや縦横比などの基本属性を有する矩形のオブジェクトである。
【００２６】
「分割木」とは、矩形ボックスを繰り返して２分割するために構築された二分木である。個々のノードは、矩形を持っている。葉の領域に部品が置かれる。
【００２７】
「平衡木：バランスツリー(balanced tree)」とは、データ構造の一種であるツリー構造(木構造)のうち、根ノードから子を持たない末端の葉ノードまでの高さ(深さ)がなるべく等しくなるように構築されたものである。根からどの葉まで辿ってもほぼ同じ数のノードを経由するため、探索などの処理をする平均の計算複雑度はlog ｎである。ツリーを平衡木に保つには、ノードの挿入や削除が行われる際に再構築して高さが等しく保たれるようにする処理が必要となる。平衡木の代表例としては、ＡＶＬ木や赤黒木がある。平衡木の初期値は、ＮＵＬＬである。
【００２８】
平衡木は、次の特徴を持つ。  
（１）２つの子を持つ各節点において、左側部分子木と右側部分子木の高さの差が１以内である（子木がＮＵＬＬの場合は高さを０とする）。  
（２）右の子の持つ値(Left)は親の持つ値(Parent)より小さくない；親の持つ値は左の子の持つ値(Right)がより小さくない。
【００２９】
「境界ボックス」とは、矩形ボックス内に配置された部品を包含する最小矩形領域をいう。本発明においては、分割木の根ノードは、境界ボックスである。
【００３０】
「隙間」とは、境界ボックス内に、部品が移動できる最大矩形スペースである。部品の上下や左右のスペースの合計で表わされる。隙間の一覧は、例えば、平衡木構造に保持される。
【００３１】
「実画面」とは、レイアウトされた部品を表示する、例えば、ディスプレイ装置の実際の画面を指す。
【００３２】
「仮想画面」とは、実画面と同じ縦横比で、境界ボックスを含む最小の矩形領域である。
【００３３】
「未充填領域」とは、境界ボックス以外の仮想画面内のスペースである。
【００３４】
図２は、部品レイアウト生成装置１０の概略構成を機能部品で示したものである。部品レイアウト生成装置１０は、矩形ボックスパラメータ入力部１１、部品パラメータ入力部１２、部品レイアウト計算部１３、部品座標出力部１４から構成されている。
【００３５】
矩形ボックスパラメータ入力部１１は、矩形ボックスのパラメータを入力するものである。矩形ボックスは、情報を視覚化するディスプレイ装置の表示画面や工業用母材などを表わす抽象的な概念である。矩形ボックスは少なくとも、縦横のサイズの積である面積と縦横比の基本的な属性を有し、それらがパラメータとして表わされる。
【００３６】
部品パラメータ入力部１２は、複数の部品のパラメータを入力するものである。情報の視覚化においては、データは矩形にマッピングすることができる。各部品は少なくとも、縦横のサイズの積である面積と縦横比の基本属性を有し、それらがパラメータとして表わされる。部品は、特段限定されたものではなく、例えば、画像は部品の一例である。画像の場合、面積と縦横比のパラメータの他に、画素の集合も重要な意味を持つことが多い。情報をよりメリハリを付けて視覚化させるため、部品の内部に色彩や線を施したり、グラフ化して部品の特性を示すことができる。本実施形態では、矩形ボックスや部品の有する属性のうち、縦横のサイズの積である面積と縦横比を使用してレイアウトを決定するもので、他の属性は、個々の部品の内部表現としてよく使えるが、レイアウトを決定する過程では使用しない。
【００３７】
部品レイアウト計算部１３は、分割木構築部１５と、部品座標計算部１６から成っている。分割木構築部１５は、矩形ボックスの面積と縦横比、各部品の面積と縦横比を用いて、矩形ボックスを区画する分割木を構築する。分割木の構築は、図３（ａ）に示すような、一定縦横比の仮想画面に対して、Ｎ個の部品を、縦横比と面積を維持しながら、図３（ｂ）に示すように配置して、仮想画面の面積を最小化することである。仮想画面を水平方向又は垂直方向に二分に区画することを繰り返して分割して、分割木に対応させる。部品は、隙間に配置することを優先する。部品が隙間に入りきらない場合には、未充填領域に配置する。未充填領域に部品が入りきらない場合には、未充填領域に部品を収納できるまで、縦横比を維持しながら仮想画面を拡大する。複数の部品を見やすく視覚化するには、全ての部品を１画面に詰め込む必要がある。そこで、各部品の縦横比を維持しながら、面積を同率に拡大して、仮想画面上で重ならないように配置する。全ての部品の詰め込み後は、実画面中に表示されるべく、縦横比を維持しながら、仮想画面と部品を同率で縮小することになる。
【００３８】
部品座標計算部１６は、分割木構築部１５で構築された分割木を用いて、分割木のＴＯＰ−ＤＯＷＮ順に沿って、矩形ボックスにおける各部品の置かれる位置座標を計算する。
【００３９】
部品座標出力部１４は、部品座標計算部１６で算出した全ての部品の位置情報を出力するか、ディスプレイ装置の実画面上に表示する。
【００４０】
図４は、部品レイアウト計算部１３におけるレイアウト処理の流れを示すフローチャートである。まず初めに、矩形ボックスパラメータ入力部１１から受け取った矩形ボックスのパラメータ及び部品パラメータ入力部１２から受け取った部品パラメータについて、入力データの正規化を行う（ステップＳ４０１）。入力データの冗長性を少なくして利用しやすくするためである。レイアウト処理で取り扱う入力データには、矩形ボックスサイズ及び各部品サイズがある。矩形ボックスがディスプレイ装置の画面そのものであるような場合には、縦と横のサイズは物理的に決定されるので、一般的に整数にして問題ないが、部品のサイズは常に整数とは限らない。部品レイアウトの位置とサイズは、ディスプレイ装置の画面サイズと部品の相対サイズにより決められるように、部品の絶対サイズとは関係がない。そこで、部品のサイズが整数ではない場合、後の計算を整数で行えるようにするため、部品サイズに同じ倍率を掛けて整数へ変換する。ここでの倍率は、部品サイズを整数で区別できるような倍率が望ましい。例えば、部品サイズを区別するための精度が０．００１であれば、全ての部品サイズに１０００倍を掛ければ、整数で表わされた部品サイズで区別できる。
【００４１】
次いで、分割木と平衡木を初期化する（ステップＳ４０２）。分割木と平衡木の初期値はＮＵＬＬである。仮想画面は、縦横比を固定しながら任意に拡大できるため、分割木構築の初期過程では面積をゼロにしても差し支えない。
【００４２】
次に、面積降順に部品リストを作成する（ステップＳ４０３）。本発明では、累進的な詰め込み方法を採用しており、面積の大きな部品から順に矩形ボックス内に詰め込むためである。
【００４３】
次いで、未配置の部品があるか否かを判定する（ステップＳ４０４）。まだ、未配置の部品が残っている場合には、残り部品から面積の大きい部品を選択する（ステップＳ４０５）。未配置の部品がない場合には、分割木の構築は完了とし、部品座標を計算して（ステップＳ４０６）、レイアウト処理を終了する。
【００４４】
ステップＳ４０５で選択した部品を詰め込むために、平衡木を用いて部品の置かれる隙間を探索する（ステップＳ４０７）。複数の隙間は、平衡木で保持されることにより、面積の降順に探索できる。隙間探索計算量は、ｎ＝隙間数とすると、Ｏ（log ｎ）に抑えられる。
【００４５】
次いで、選択した部品を配置可能な隙間があるか否かを判定する（ステップＳ４０８）。配置可能な隙間がある場合には、最大の隙間への配置を決定（ステップＳ４０９）し、部品の配置後、分割木を更新する（ステップＳ４１０）。分割木の更新後、平衡木を更新するステップＳ４１１）。部品の置かれる隙間の決定と、部品の置かれた後の残った隙間の計算はほぼ同時に行うため、フローチャートにおいて平衡木更新と分割木更新はどちらを先にしても、差し支えない。
【００４６】
一方、配置可能な隙間が無い場合には、仮想画面をリサイズして未充填領域を確保（ステップＳ４１２）し、未充填領域への部品の配置を決定（ステップＳ４１３）する。
【００４７】
（分割木構築例）
以下に、分割木構築例を詳述する。
【００４８】
図５は、面積降順の部品リスト（Ｂ１，Ｂ２，Ｂ３，Ｂ４，Ｂ５, ・・・）と画面（縦横比固定）を用いて、分割木を構築する初期状態を示す図である。初期状態では、面積降順の隙間リストには何も無い（ＮＵＬＬ）。
【００４９】
図６は、部品Ｂ１を画面に詰め込んだ状態を示す図である。画面は縦横比を固定しながら、Ｂ１が納まるまで拡大する。分割木は、Ｂ１ノードのみである。本実施形態において、分割木の根ノードは、境界ボックスである。ここでの境界ボックスは、Ｂ１を含み面積が最小となるような矩形であるため、部品Ｂ１の左右端は画面の横方向に接するので、隙間は生じない。したがって、ここでは、平衡木＝ＮＵＬＬのままである。図６において、部品Ｂ１の上下には、画面内未充填領域が形成されている。
【００５０】
次に、図７は、部品Ｂ２を詰め込んだ状態を示す図である。部品Ｂ２を詰め込む際には、画面面積が小さくなるように詰め込む。図７に示す例では、部品Ｂ１，部品Ｂ２を水平に並べる場合は垂直に並べる場合に比べて画面面積が小さくなる。ここでは、部品Ｂ１，部品Ｂ２を水平に並べる。分割木は、葉ノードペア（Ｂ１，Ｂ２）とそれらの親ノード（水平分岐Ｈ）である。
【００５１】
境界ボックスは、部品Ｂ１，部品Ｂ２を含み面積が最小となるような矩形である。図７に示す例では、境界ボックス内であって、部品Ｂ１の上下に隙間Ｓ１が形成された。隙間Ｓ１は、面積降順の隙間リストに追加され、平衡木が更新されている。部品の上下位置や左右位置は、一方にシフトすることが出来、配置処理に関係しない。そこで、上下の二つの高さを加えた一つの高さと、Ｂ１の幅で代表させて隙間Ｓ１を定義することができる。
【００５２】
次に、図８は、部品Ｂ３を詰め込んだ状態を示す図である。まず、平衡木に保持された複数の隙間を面積降順にチェックする。ここに平衡木に隙間はＳ１しかないが、隙間Ｓ１には、部品Ｂ３を納められない。そこで、詰め込み後の画面面積が小さくなるように、部品Ｂ３を（部品Ｂ１,部品Ｂ２）と垂直に並べ、未充填領域に詰め込んだ。
【００５３】
ここでの境界ボックスは、（部品Ｂ１，部品Ｂ２，部品Ｂ３）を納める最小の矩形である。詰め込みに際し、分割木を更新している。更新後の分割木は、図８の左上に示すように、三つの葉ノード（Ｂ１，Ｂ２，Ｂ３）と二つの分岐ノードで構成される。詰め込み後、部品Ｂ３の左右に隙間Ｓ２が形成されるが、既に隙間リストに存在している隙間Ｓ１よりも面積が大きい。そこで、平衡木である隙間リストが更新され、隙間Ｓ２，隙間Ｓ１の面積降順が同時に保持される。
【００５４】
次に、図９は、部品Ｂ４を詰め込んだ状態を示す図である。平衡木である複数の隙間の中に、面積順で探し、部品Ｂ４を納められる隙間Ｓ２を見つけた。ここでは、部品Ｂ３の右隣に部品Ｂ４を詰め込んでいる。詰め込む部品を納められる隙間について、複数の候補が存在する場合には、詰め込み後のバランスを考慮して、決定するのが好適である。隙間の面積降順に応じて、大きな隙間に優先的に詰めこむことで、最後のレイアウトに大きな隙間がないようにバランスが取れる。部品を詰め込める面積の小さい隙間を優先させることや、それらの複数の隙間をランダムに選ぶこともできる。詰め込む時の隙間優先順番に関わらず、選択した隙間に部品を詰め込みことは本発明の範囲内である。
【００５５】
詰め込みに際し、分割木を更新している。更新後の分割木は、四つの葉ノード（Ｂ１，Ｂ２，Ｂ３，Ｂ４）と三つの分岐ノード（二つのＨノードと一つのＶノード）により構成された。
【００５６】
部品Ｂ４を隙間Ｓ２に詰め込んだ結果、隙間Ｓ２は部品Ｂ４の面積分だけ小さくなり、隙間Ｓ２’になる。さらに、部品Ｂ４の上下に新しい隙間Ｓ３が形成された。
【００５７】
平衡木である隙間リストが更新され、隙間Ｓ１，隙間Ｓ２’，隙間Ｓ３の面積降順も保持される。
【００５８】
図１０は、部品Ｂ５を詰め込んだ状態を示す図である。平衡木である隙間リストを探索し、部品Ｂ５が詰め込める隙間を面積降順に探す。部品Ｂ５は、高さが隙間Ｓ１の高さを超えるため、隙間Ｓ１に納められない。部品Ｂ５が次の隙間Ｓ２’に納められることが探索できると、部品Ｂ５を隙間Ｓ２’に詰め込む。部品Ｂ５を隙間Ｓ２’に詰め込んだ結果、隙間Ｓ２’は部品Ｂ５の面積分だけ小さくなり、隙間Ｓ２’’になる。そして、部品Ｂ５の上下に新しい隙間Ｓ４が形成された。
【００５９】
詰め込みに際し、分割木を更新している。更新後の分割木は、図１０に示すように、五つの葉ノード（Ｂ１〜Ｂ５）と四つの分岐ノードにより構成された。
【００６０】
平衡木である隙間リストが更新され、隙間Ｓ１，隙間Ｓ２’’，隙間Ｓ３，隙間Ｓ４の面積降順も平衡木に保持される。
【００６１】
以上のように、全ての部品について、部品の面積降順で一つずつ画面ボックスへの詰め込みが完了すると、最終の分割木が形成される。
【００６２】
（分割木の更新）
次に、分割木の更新について詳述する。
【００６３】
まず、分割木がＮＵＬＬのときに、最初に配置する部品は根ノードに置く。分割木がＮＵＬＬでないとき、１個の部品を追加する場合、二つのノード（部品の親ノードと部品が配置されるノード）が分割木に追加される。子ノードペアを持つ親ノードのサイズ計算は、図１１に示すようになる。垂直方向に分割する場合、子ノード１の縦横が（ｗ１，ｈ１）、子ノード２の縦横が（ｗ２，ｈ２）であるとき、親ノードのサイズ（ｗ１２，ｈ１２）は、ｗ１２＝ｍａｘ（ｗ１，ｗ２），ｈ１２＝ｈ１＋ｈ２となる。水平方向に分割する場合、子ノード１の縦横が（ｗ１，ｈ１）、子ノード２の縦横が（ｗ２，ｈ２）であるとき、親ノードのサイズ（ｗ１２，ｈ１２）は、ｗ１２＝ｗ１＋ｗ２，ｈ１２＝ｍａｘ（ｈ１，ｈ２）となる。
【００６４】
図１１に示すように、分割木の各ノードに、（１）子ノードペアが垂直（Ｖ）並べか、水平（Ｈ）並べか、（２）ノードに対応する矩形スペースの幅と高さのパラメータが保持される。
【００６５】
（計算複雑度）
次に、分割木構築における計算複雑度について説明する。
【００６６】
ｋ個の部品を二分木に追加した時に形成される隙間の最大数は、ｋ−１である。ｋ番目の隙間を面積降順リストに挿入する際に、二分探索の最大計算量はlog (ｋ-1)となる。
【００６７】
Ｎ個の部品を全て二分木に追加する場合の最大計算量は、
Log１+ log２ + …+ log ｋ + … + log (Ｎ-1) = log (Ｎ-1)! 
≒(Ｎ-１／２) log (Ｎ-1)−Ｎ log e +Ｃ≒Ｎ log Ｎ 
である。ここで、計算式はＮ>>０を条件とする。
【００６８】
（平衡木の探索及び平衡木の更新）
面積降順による隙間列そのままでは、探索時間はＯ(ｎ)である。そこで、探索時間を更に減らすために、隙間リストの実データ構造は、図１２に示すように、平衡木（例えばＡＶＬ木）で保持している。平衡木は、（１）任意の分岐ノードから、左右の子木の深さの差は最大１である、（２）分岐ノードはソートされる、（３）左子ノードの値≧親ノードの値≧  右子ノードの値の関係にある、という特徴をもつ。
【００６９】
そして、平衡木ノードの探索方法は、ソートされたデータ列の二分探索と同様に行える。したがって、平衡木の探索の複雑度は、根からどの葉まで辿ってもほぼ同じ数のノードを経由するため、log (ｎ) (ｎはノード数）で表わされ、ｎ個の隙間の平衡木を操作する計算複雑度はlog (ｎ) となる。
【００７０】
隙間の探索、隙間の削除、隙間の挿入といった平衡木の更新は、平衡木を維持したままで行なわれる。隙間の削除や隙間の挿入の際に、左右の子木の深さの差が２以上になった場合には、平衡性を維持するため、平衡木の再構成が行われる。したがって、計算複雑度は、log (ｎ) (ｎはノード数）に抑えられる。
【００７１】
（仮想画面のリサイズ）
詰め込む部品のサイズ（面積）に比較して、隙間リスト中に適切な隙間が無い場合、仮想画面をリサイズして、未充填領域に部品を詰め込む。図１３により、仮想画面をリサイズして、未充填領域を確保する処理について説明する。
【００７２】
まず、詰め込むべきカレント部品のサイズ（ｗ，ｈ）を把握する（ステップＳ１３０１）。次に、分割木の根ノードサイズを境界ボックスサイズ（Ｗｂ，Ｈｂ）として設定する（ステップＳ１３０２）。次いで、未充填領域のサイズを計算する（ステップＳ１３０３）。それに続いて、計算した未充填領域にカレント部品が配置可能か否かを判定する（ステップＳ１３０４）。配置できない場合には、仮想画面を部品が配置できる大きさまでリサイズする（ステップＳ１３０５）。その後、部品が配置され、分割木の更新処理へ移行する（ステップＳ１３０６）。一方、配置できる場合には、リサイズする必要がないため、直ちにステップＳ１３０６へ移る。
【００７３】
図１４は、未充填領域のサイズ計算を説明する図である。未充填領域は、仮想画面（Ｗｒ，Ｈｒ）と境界ボックス（Ｗｂ，Ｈｂ）の差であり、図１４（ａ）に示すように、境界ボックス（Ｗｂ，Ｈｂ）の上下に未充填領域が形成される場合と、図１４（ｂ）に示すように、境界ボックス（Ｗｂ，Ｈｂ）の左右に未充填領域が形成される場合がある。
【００７４】
実画面の大きさを幅Ｗ０と高さＨ０とすると、Ｗｂ／Ｈｂ＞Ｗ０／Ｈ０の場合、仮想画面（Ｗｒ，Ｈｒ）の大きさは、（Ｗｂ，Ｗｂ＊Ｈ０／Ｗ０）と表わすことができる。よって、未充填領域のサイズは、（Ｗｂ，Ｈｒ−Ｈｂ）となる（図１４（ａ）参照）。一方、Ｗｂ／Ｈｂ＜Ｗ０／Ｈ０の場合、仮想画面（Ｗｒ，Ｈｒ）の大きさは、（Ｈｂ＊Ｗ０／Ｈ０，Ｈｂ）と表わすことができる。よって、未充填領域のサイズは、（Ｗｒ−Ｗｂ，Ｈｂ）となる（図１４（ｂ）参照）。
【００７５】
次に、図１５は、仮想画面のリサイズ方法を説明する図である。いま、カレント部品（ｗ，ｈ）を仮想画面（Ｗｒ，Ｈｒ）と境界ボックス（Ｗｂ、Ｈｂ）との隙間の詰め込もうとするが、不可能である。そこで、実画面の大きさを幅Ｗ０と高さＨ０とし、実画面と同じ縦横比で仮想画面を拡大する。カレント部品と境界ボックスを垂直方向に並べる場合、リサイズ後の仮想画面（Ｗｖ，Ｈｖ）は、Ｗｖ＝Ｈｖ＊Ｗ０／Ｈ０、Ｈｖ＝Ｈｂ＋ｈとなる。カレント部品と境界ボックスを水平方向に並べる場合、リサイズ後の仮想画面（Ｗｈ，Ｈｈ）は、Ｗｈ＝Ｗｂ＋ｗ、Ｈｈ＝Ｗｈ＊Ｈ０／Ｗ０となる。
【００７６】
カレント部品と境界ボックスを水平方向に並べるか、垂直方向に並べるかのいずれを選択するかについては、リサイズ後の仮想画面の面積より、面積が小さい方を選択する。仮想画面はリサイズしても縦横比が同じなので、横或は縦のサイズのみを比べれば面積の順が分かる。すなわち、Ｗｖ＜Ｗｈであれば、リサイズ後の仮想画面として、(Ｗｖ，Ｈｖ)に設定する。Ｗｖ＞Ｗｈであれば、リサイズ後の仮想画面として、(Ｗｈ，Ｈｈ)に設定する。
【００７７】
（部品座標の計算）
次に、部品座標の計算について説明する。上述してきた部品レイアウトのプロセスは、画面の縦横比固定で、仮想画面サイズを任意に拡大しながら分割木を生成した。最終的にレイアウトされた部品を、実際のディスプレイ装置等に表示させるためには、元の実画面サイズに戻す必要がある。簡単な方法としては、仮想画面サイズを元のサイズまで縮小して、全ての部品のサイズと位置（座標）を同じ倍率で縮小する。しかしながら、大量のデータがある場合、大きな座標と小さな座標を同じ倍率で処理すると、誤差の程度が異なり、座標が大きな程、生じる誤差が大きくなる。
【００７８】
そこで、誤差を減らすために、分割木をＴＯＰ-ＤＯＷＮ順に沿って、元の画面サイズから順次、子ノードの座標を計算する。これにより、誤差を分散でき、画面上で目立たないようになる。部品の隣接関係は全て二分木に記録されるので、分割木に沿って、視座標系にある部品座標とサイズを算出する。ここで、視座標系は、実画面の左上を原点として、画面の横をＸ軸、画面の縦をＹ軸とする座標である。
【００７９】
具体的には、（１）各ノードの実画面でのサイズと座標を計算する、（２）部品をリサイズして葉ノード空間の真ん中に置く、とのステップで行う。
【００８０】
各ノードの実画面でのサイズと座標計算は、幅優先走査順（ＢＦＴ順：Breadth First Traversal順）で行う。幅優先走査の計算手法は、根ノードで始まり親ノードから二つの子ノードのサイズと座標を計算する。子ノードは同様のことを繰り返して葉に至るまでの計算手法である。これまで構築された分割木はノード毎に、仮想画面での矩形領域を保持している。これらのノードは、実画面のサイズに応じて、実画面でのノードサイズを計算する；更にノードの相互位置関係（垂直に並べるか、水平に並べるか）を用いて、実画面での位置座標を計算する。葉の実画面での矩形領域には、ｒ倍率（r=仮想画面サイズ/実画面サイズ） に乗じた部品が置かれる。
【００８１】
図１６は、部品の座標の計算を説明する図である。親ノードの実画面でのサイズ（w0’,h0’）と左上角の座標（x0’,y0’）を用いて、垂直に並べた子ノードペアの実画面でのサイズ（w1’,h1’）、（w2’,h2’）と左上角の座標（x1’,y1’）、（x2’,y2’）を計算する。子ノードペアの仮想画面でのサイズ(w1,h1),(w2,h2)は分割木に保持されているので、子ノードの実画面の高さは仮想画面での高さを比例して、親ノードの高さw0’を分割する。h1’ = h0’* h1/(h1 + h2), h2’ = h0’-h1’となる。
【００８２】
子ノードの幅は親ノードの幅と同じであるので、w1’ = w2’ = w0’となる。
【００８３】
更に、子ノードペアの左上の座標を取ると、x1’= x0’, y1= y0’, x2’= x1’, y2’= y1’+h1’となる。子ノードを水平に並べる場合は、計算方法が同じであるので、ここでは省略する。
【００８４】
はじめの親ノード（根ノード）を実画面にあてはめて、 サイズ（w0’,h0’）＝(W0, H0)と左上角の座標を（x0’,y0’）=(0,0)に設定し、上述のように、親ノードから子ノードの計算順を繰り返して、葉まですべてのノードのサイズと座標を計算する。
【００８５】
Ｎ(Ｎ>>０)個の部品を全て二分木に追加する場合の最大計算量は、Ｎ log Ｎ であり、二分木から座標を計算するときの計算複雑度は  Ｏ(Ｎ)であるので、本実施形態における総合した計算複雑度は、Ｏ (Ｎ log Ｎ)となる。また、部品のサイズを整数に正規化しているので、座標計算も整数計算で行える。
【００８６】
本実施形態によれば、複数の部品を配置する際、計算複雑度、空間複雑度を抑制できるので、レイアウトの探索を高速で行うことが出来る。また、レイアウトされた部品の座標計算に際して、整数計算のみで実現するので、誤差を一方向に累積させることがない。
【００８７】
なお、本発明は上記の実施形態のそのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記の実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【符号の説明】
【００８８】
１０…部品レイアウト生成装置、２０…記憶装置、３０…出力装置、４０…演算処理装置、５０…主メモリ、６０…読出し専用メモリ、７０…入力装置、１１…矩形ボックスパラメータ入力部、１２…部品パラメータ入力部、１３…部品レイアウト計算部、１４…部品座標出力部、１５…分割木構築部、１６…部品座標計算部。
【図１】
2011113509.tif 000003
【図２】
2011113509.tif 000004
【図３】
2011113509.tif 000005
【図４】
2011113509.tif 000006
【図５】
2011113509.tif 000007
【図６】
2011113509.tif 000008
【図７】
2011113509.tif 000009
【図８】
2011113509.tif 000010
【図９】
2011113509.tif 000011
【図１０】
2011113509.tif 000012
【図１１】
2011113509.tif 000013
【図１２】
2011113509.tif 000014
【図１３】
2011113509.tif 000015
【図１４】
2011113509.tif 000016
【図１５】
2011113509.tif 000017
【図１６】
2011113509.tif 000018