グラフィック出力における重なりを回避するためにラベルを移動させる方法、システム及びコンピューター読取可能媒体
【課題】１ページに複数のオブジェクトを配置する方法を提供する。
【解決手段】図内に各々フットプリントを有する複数の固定オブジェクトを特定する工程２０２と、図内に各々位置を有する複数の可動オブジェクト（ＭＯ）を特定する工程２０４と、図を表す粗画素配列（ＣＰＡ）を取得する工程２０６と、フットプリントに対応する粗画素を占有状態に設定する工程２０８と、ＭＯを選択する工程２１０と、ＭＯの位置に基づいてＭＯのフレームに対応するＣＰＡ内の粗画素群を特定する工程２１２と、粗画素群のうち少なくとも一の粗画素が占有状態であると判断する工程２１４と、ＭＯの修正位置を生成する工程２２０と、修正位置に基づいてＭＯの修正フレームに対応するＣＰＡ内の修正粗画素群を特定する工程２２２と、ＭＯの修正粗画素群を占有状態に設定する工程２２４と、ＭＯをページ上の修正位置に配置して図をレンダリングする工程２２６を備える方法。
【解決手段】図内に各々フットプリントを有する複数の固定オブジェクトを特定する工程２０２と、図内に各々位置を有する複数の可動オブジェクト（ＭＯ）を特定する工程２０４と、図を表す粗画素配列（ＣＰＡ）を取得する工程２０６と、フットプリントに対応する粗画素を占有状態に設定する工程２０８と、ＭＯを選択する工程２１０と、ＭＯの位置に基づいてＭＯのフレームに対応するＣＰＡ内の粗画素群を特定する工程２１２と、粗画素群のうち少なくとも一の粗画素が占有状態であると判断する工程２１４と、ＭＯの修正位置を生成する工程２２０と、修正位置に基づいてＭＯの修正フレームに対応するＣＰＡ内の修正粗画素群を特定する工程２２２と、ＭＯの修正粗画素群を占有状態に設定する工程２２４と、ＭＯをページ上の修正位置に配置して図をレンダリングする工程２２６を備える方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフィック出力における重なりを回避するためにラベルを移動させる方法、システム及びコンピューター読取可能媒体に関する。
【背景技術】
【０００２】
１ページは、複数のオブジェクトを含む場合がある。これらのオブジェクトには、ページ上の所定の位置に比較的維持されるオブジェクトと、ページ上の多数の位置のうちの何れかの位置に移動させることのできるオブジェクトがある。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
多数のアプリケーションにおいて、１ページは、重なり合う多数のオブジェクトを有する場合がある。これはオブジェクトの読み取りや識別を困難にする。また、オブジェクトが重なり合っていない場合であっても、非常に接近し合ってひとかたまりとなり、明確に解釈できない場合がある。
【課題を解決するための手段】
【０００４】
主として、一側面において、本発明は図をレンダリングする方法に関する。
該方法は、
前記図内に各々フットプリントを有する複数の固定オブジェクトを特定する工程と、
前記図内に各々位置を有し、前記フットプリントと関連付けられた複数の可動オブジェクトを特定する工程と、
コンピュータープロセッサーを用いて、前記図のページスペースを表す粗画素の二次元配列を有する粗画素配列内で、前記フットプリントに対応する粗画素を特定する工程と、
前記コンピュータープロセッサーを用いて、前記フットプリントに対応する前記粗画素を占有状態に設定する工程と、
前記コンピュータープロセッサーを用いて、前記複数の可動オブジェクトのうち第１の位置を有する可動オブジェクトを選択する工程と、
前記コンピュータープロセッサーを用いて、前記第１の位置に基づいて、前記可動オブジェクトの第１のフレームに対応する前記粗画素配列内の第１の粗画素群を特定する工程と、
前記コンピュータープロセッサーを用いて、前記第１の粗画素群のうち少なくとも一の粗画素が前記占有状態であると判断する工程と、
前記コンピュータープロセッサーを用いて、前記第１の粗画素群のうち少なくとも一の粗画素が前記占有状態であると判断された場合に前記可動オブジェクトの第２の位置を生成する工程と、
前記コンピュータープロセッサーを用いて、前記第２の位置に基づいて、前記可動オブジェクトの第２のフレームに対応する前記粗画素配列内の第２の粗画素群を特定する工程と、
前記可動オブジェクトの前記第２の粗画素群を前記占有状態に設定する工程と、
ページ上の前記第２の位置に前記可動オブジェクトを配置して、前記図をレンダリングする工程と、
を備える。
【０００５】
主として、一側面において、本発明は図をレンダリングするシステムに関する。
該システムは、
ハードウェアプロセッサーと、
前記図のページスペースを表す粗画素の二次元配列を有する粗画素配列と、
可動オブジェクトの第１のフレームと第２のフレームを生成するように構成されたフレームモジュールと、
前記ハードウェアプロセッサー上で実行されるレイアウトエンジンと、
を備え、
前記レイアウトエンジンは、
前記図内に各々フットプリントを有する複数の固定オブジェクトを特定し、
前記フットプリントに対応する前記粗画素配列内の粗画素を占有状態に設定し、
前記可動オブジェクトの第１の位置に基づいて、前記第１のフレームに対応する前記粗画素配列内の第１の粗画素群を特定し、
前記第１の粗画素群のうち少なくとも一の粗画素が前記占有状態であると判断し、
前記可動オブジェクトと関連付けられた第２の位置に基づいて、前記可動オブジェクトの前記第２のフレームに対応する前記粗画素配列内の第２の粗画素群を特定し、
ページ上の前記第２の位置に前記可動オブジェクトを配置して、前記図をレンダリングするように構成されている。
【０００６】
主として、一側面において、本発明は図をレンダリングするための指示を記憶する非一時的コンピューター読取可能記憶媒体に関する。
該指示は、
前記図内に各々フットプリントを有する複数の固定オブジェクトを特定するための指示と、
前記図内に位置を有し、前記フットプリントと関連付けられた複数の可動オブジェクトを特定するための指示と、
前記図のページスペースを表す粗画素の二次元配列を有する粗画素配列内で、前記フットプリントに対応する粗画素を特定するための指示と、
前記フットプリントに対応する前記粗画素を占有状態に設定するための指示と、
前記複数の可動オブジェクトのうち第１の位置を有する可動オブジェクトを選択するための指示と、
前記第１の位置に基づいて、前記可動オブジェクトの第１のフレームに対応する前記粗画素配列内の第１の粗画素群を特定するための指示と、
前記第１の粗画素群のうち少なくとも一の粗画素が前記占有状態であると判断するための指示と、
前記第１の粗画素群のうち少なくとも一の粗画素が前記占有状態であると判断された場合に前記可動オブジェクトの第２の位置を生成するための指示と、
前記第２の位置に基づいて、前記可動オブジェクトの第２のフレームに対応する前記粗画素配列内で第２の粗画素群を特定するための指示と、
前記可動オブジェクトの前記第２の粗画素群を前記占有状態に設定するための指示と、
ページ上の前記第２の位置に前記可動オブジェクトを配置して、前記図をレンダリングするための指示と、
を備える。
【０００７】
本発明のその他の側面は、以下の説明及び添付の特許請求の範囲から明らかである。
【図面の簡単な説明】
【０００８】
【図１Ａ】本発明の一以上の実施形態に係るシステムのブロック図を示す。
【図１Ｂ】本発明の一以上の実施形態に係る複数のオブジェクトを有する図を示す。
【図１Ｃ】本発明の一以上の実施形態に係る図及び粗画素配列（ＣＰＡ）を示す。
【図１Ｄ】本発明の一以上の実施形態に係る可動オブジェクト用に生成される複数のフレームを示す。
【図２Ａ】本発明の一以上の実施形態に係るフローチャートを示す。
【図２Ｂ】本発明の一以上の実施形態に係るフローチャートを示す。
【図２Ｃ】本発明の一以上の実施形態に係るフローチャートを示す。
【図３Ａ】本発明の一以上の実施形態に係る例を示す。
【図３Ｂ】本発明の一以上の実施形態に係る例を示す。
【図３Ｃ】本発明の一以上の実施形態に係る例を示す。
【図３Ｄ】本発明の一以上の実施形態に係る例を示す。
【図３Ｅ】本発明の一以上の実施形態に係る例を示す。
【図３Ｆ】本発明の一以上の実施形態に係る例を示す。
【図３Ｇ】本発明の一以上の実施形態に係る例を示す。
【図３Ｈ】本発明の一以上の実施形態に係る例を示す。
【図３Ｉ】本発明の一以上の実施形態に係る例を示す。
【図３Ｊ】本発明の一以上の実施形態に係る例を示す。
【図４】本発明の一以上の実施形態に係るコンピューターシステムを示す。
【発明を実施するための形態】
【０００９】
本発明の具体的な実施形態を、添付の図面を参照して詳細に説明する。複数の図に示される同様の構成要素は、一貫性を保つために同様の参照符号で示す。
【００１０】
以下の本発明に係る実施形態の詳細な説明には、本発明についてより完全な理解を提供するために、数多くの詳細を示す。しかし、当業者には、これらの詳細を用いずとも本発明の実施が可能であることは明らかであろう。他の例においては、不要に複雑な説明となるのを避けるため、周知の特徴に関しては詳細な説明は省略する。
【００１１】
主として、本発明の実施形態は、１ページに複数のオブジェクト（すなわち、固定オブジェクト、可動オブジェクト）を配置するシステム及び方法を提供する。具体的には、複数の固定オブジェクト、そしてそれらに伴う可動オブジェクトを、互いに重なり合わないように１ページ上に配置する。粗画素配列（Ｃｏａｒｓｅ Ｐｉｘｅｌ Ａｒｒａｙ；ＣＰＡ）は粗画素の二次元配列であり、オブジェクトを有する図のページスペースを表す。ページ上の一の位置に配置されるオブジェクトは、ＣＰＡに位置する粗画素群によって表される。この粗画素群は占有状態に設定される。配置される必要のあるオブジェクトは、当該オブジェクトの粗画素群によって表され、初期位置に配置される。このオブジェクトの粗画素群のうち少なくとも一の粗画素が既に占有状態である場合、新たな位置が使用される。この処理は、全てのオブジェクトがページ上に配置されるまで（すなわち、図がレンダリングされるまで）繰り返される。本発明の実施形態において、オブジェクトは、当該オブジェクトのフットプリントの拡大／縮小版に対応するフレームを用いて配置される。
【００１２】
図１は、本発明の一以上の実施形態に係るシステム１００を示す。図１に示されるように、システム１００は、ページレンダリングデバイス（ＰＲＤ）１５０と、ストレージリポジトリ１３０と、クライアントコンピューター１０５とを含む、複数の構成要素を備える。ＰＲＤ１５０は、プリンター、電子読取装置などである。コンピューティングデバイス１０５は、パーソナルコンピューター（ＰＣ）、デスクトップコンピューター、汎用コンピューター、サーバー、電話、公共電話ボックス、ケーブルボックス、携帯情報端末（ＰＤＡ）、電子読取装置、携帯電話、スマートフォンなどである。ストレージリポジトリ１３０は、ハードウェア記憶装置（例えば、ハードドライブ、テープ、メモリー等）の何れかの種類に対応する。コンピューティングデバイス１０５と、ＰＲＤ１５０と、ストレージリポジトリ１３０は、直接的に接続されてもよい（例えば、ユニバーサルシリアルバス（ＵＳＢ）接続など）。あるいは、コンピューティングデバイス１０５と、ＰＲＤ１５０と、ストレージリポジトリ１３０は、有線部分及び／又は無線部分を有するネットワーク１２０を用いて接続されてもよい。
【００１３】
本発明の一以上の実施形態において、ＰＲＤ１５０及び／又は記憶装置１３０はコンピューティングデバイス１０５上に位置する。このような実施形態では、ＰＲＤ１５０は、コンピューティングデバイス１０５上の、図をレンダリングするためのハードウェアとソフトウェアの組み合わせに対応する。本発明の一以上の実施形態において、記憶装置１３０はＰＲＤ１５０上に位置する。
【００１４】
本発明の一以上の実施形態において、コンピューティングデバイス１０５はユーザーアプリケーション１１０を実行する。ユーザーアプリケーション１１０はユーザーによって操作されるソフトウェアアプリケーションであり、図（例えば、図１１５）を取得、入力、生成、表示及び／又は印刷するように構成されている。よって、ユーザーアプリケーション１１０は、ワードプロセッシングアプリケーション、表計算アプリケーション、デスクトップパブリッシングアプリケーション、グラフィックアプリケーション、写真印刷アプリケーション、インターネットブラウザー、地図作成アプリケーション、グラフィカラルプロットアプリケーションなどである。ユーザーアプリケーション１１０は、新たな図を生成及び／又は事前に保存した図を取得する。
【００１５】
本発明の一以上の実施形態において、図１１５は、一以上の固定オブジェクトと一以上の可動オブジェクトを含む。図１１５は、一以上の背景オブジェクトを含んでもよい。背景オブジェクトは、上から重ねて印刷されてもよい図内のアイテムに対応する。背景オブジェクトの例としては、背景画像、多角形フィル、シンボル、線（例えば、表内の縦横拡大縮小線）などがある。固定オブジェクトは、図内に位置を有し、図全体に意味を付与する当該図内のアイテムに対応する。本発明の一以上の実施形態において、固定オブジェクトは上から重ねて印刷されてはならない。固定オブジェクトの例としては、クリップアート、形、散布データ図のマーカー、地図上のシンボルなどがある。一方、可動オブジェクトは、図の全体的な意味を変えずに再配置することが可能な図内のアイテムに対応する。可動オブジェクトは、固定オブジェクトを特定及び／又は説明するために用いられる。例えば、可動オブジェクトは、固定オブジェクトを特定及び／又は説明する文字列（すなわち、ラベル）である。
【００１６】
本発明の一以上の実施形態において、図１１５内の複数の固定オブジェクトと、図１１５内の複数の可動オブジェクトは、ランク付けされる（すなわち、優先順位が付けられる）。すなわち、固定オブジェクトの階層と可動オブジェクトの階層が存在する。記憶装置１３０は、図１１５内の全固定オブジェクトのリスト（すなわち、固定オブジェクト（ＦＯ）リスト１３２）と、図１１５内の全可動オブジェクトのリスト（すなわち、可動オブジェクト（ＭＯ）リスト１３６）を含む。ＦＯ階層１３４は、図１１５内の固定オブジェクトのランクを特定する。同様に、ＭＯ階層１３８は、図１１５内の可動オブジェクトのランクを特定する。
【００１７】
図１Ｂは、本発明の一以上の実施形態に係る図（すなわち、図Ｘ／１９９）を示す。図１Ｂに示されるように、図Ｘ／１９９は、複数の固定オブジェクト（すなわち、固定オブジェクトＡ／１９７、固定オブジェクトＢ／１９３）と、複数の可動オブジェクト（すなわち、可動オブジェクトＸ／１９５、可動オブジェクトＹ／１９３）と、背景オブジェクト１８０を含む。固定オブジェクトＡ／１９７はクリップアート要素であり、可動オブジェクトＸ／１９５は固定オブジェクトＡ／１９７を特定し説明する文字列（すなわち、「ＥＬＥＰＨＡＮＴ」（象））である。固定オブジェクトＢ／１９３はシンボルであり、可動オブジェクトＹ／１９１は固定オブジェクトＢ／１９１を特定し説明する文字列（すなわち、「ＡＵＳＴＩＮ」（オースティン））である。また、同じく図１Ｂに示されるように、固定オブジェクトＢ／１９３と可動オブジェクトＹ／１９１は背景画像１８０上に印刷される。また、可動オブジェクトＸ／１９５は対応する固定オブジェクトＡ／１９７に隣接しており、可動オブジェクトＹ／１９１は対応する固定オブジェクトＢ／１９３に隣接している。
【００１８】
本詳細な説明の恩恵に浴する当業者であれば、可動オブジェクトＸ／１９５と可動オブジェクトＹ／１９１は、それぞれが対応する固定オブジェクトを特定し説明しながら、図Ｘ／１９９の意味を曲解させることなく、再配置される場合があることを理解するであろう。例えば、可動オブジェクトＸ／１９５は、対応する固定オブジェクトＡ／１９７を特定し説明しながら、図Ｘ／１９９の意味を曲解させることなく、当該固定オブジェクトＡ／１９７の近傍に再配置される場合がある。同様に、可動オブジェクトＹ／１９１は、対応する固定オブジェクトＢ／１９５を特定し説明しながら、図Ｘ／１９９の意味を曲解させることなく、当該固定オブジェクトＢ／１９５の近傍に再配置される場合がある。
【００１９】
また、本詳細な説明の恩恵に浴する当業者であれば、図は、固定オブジェクト及び可動オブジェクトをいくつ有してもよいことを理解するであろう。そのため、多数の可動オブジェクトが存在する場合、可動オブジェクトが重なり合う場合がある。このような場合は、図の読み取り及び理解を容易にするため、一以上の可動オブジェクトを初期位置から新たな位置へと再配置する。可動オブジェクトの初期位置は、図内で指定される。
【００２０】
図１Ａに戻り、本発明の一以上の実施形態において、ＰＲＤ１５０は粗画素配列（ＣＰＡ）１５８を含む。ＣＰＡ１５８は、図１１５のページスペースを表す多次元（すなわち、二次元）配列である。ＣＰＡ１５８の有する粗画素数はいくつであってもよい。本発明の一以上の実施形態において、各粗画素は図１１５のｘ／７２ｉｎ２に対応する。ｘは図１１５で使用される最小のフォントサイズである。
【００２１】
本発明の一以上の実施形態において、ＣＰＡ１５８は固定オブジェクト及び可動オブジェクトがどこに描画されたのかを記録又は追跡する。具体的には、描画された固定オブジェクト及び可動オブジェクトのフットプリント（すなわち、面積、周長及び／又はバウンディングボックス）に対応するＣＰＡ１５８内の粗画素は、占有状態に設定される。本発明の一以上の実施形態において、ＣＰＡ１５８はビット配列である。このような実施形態においては、値「０」を有する粗画素は全て空き（すなわち、占有されていない）状態であり、値「１」を有する粗画素は全て占有状態である。本詳細な説明の恩恵に浴する当業者であれば、占有状態と空き（すなわち、占有されていない）状態を示す二つの値には、いかなる値を使用してもよいことを理解するであろう。
【００２２】
図１Ｃは、本発明の一以上の実施形態に係る粗画素配列１９０を示す。ＣＰＡ１９０は図Ｘ／１９９を表す。図１Ｃに示されるように、固定オブジェクト及び可動オブジェクトのフットプリントに対応するＣＰＡ１９０内の粗画素は、占有状態に設定される。例えば、フットプリントＡ／１８７は固定オブジェクトＡ／１９７に対応する。よって、フットプリントＡ／１８７に対応する粗画素は占有状態に設定される。同様に、フットプリントＢ／１８３は固定オブジェクトＢ／１９３に対応する。よって、フットプリントＢ／１８３に対応する粗画素は占有状態に設定される。また、フットプリントＸ／１８５は可動オブジェクトＸ／１９５に対応する。よって、フットプリントＸ／１８５に対応する粗画素は占有状態に設定される。更に、フットプリントＹ／１８１は可動オブジェクトＹ／１９１に対応する。よって、フットプリントＹ／１８１に対応する粗画素は占有状態に設定される。本発明の一以上の実施形態において、ＣＰＡ１９０は背景オブジェクト（例えば、背景オブジェクト１８０）のフットプリントを記録／追跡しない。
【００２３】
図１Ａに戻り、本発明の一以上の実施形態において、ＰＲＤ１５０はフレームモジュール１６０を含む。フレームモジュール１６０は図１１５内の各可動オブジェクトについて、サイズの異なる複数のフレームを算出するように構成されている。また、本発明の一以上の実施形態において、フレームモジュール１６０は、固定オブジェクトが重なり合う場合、重なり合っている固定オブジェクトのうち一以上の固定オブジェクトについて、フレームを算出するように構成されている。各フレームは、実質的に、可動オブジェクト又は固定オブジェクトを囲うコンテナーである。よって、最小フレームはオブジェクトのフットプリントに対応し、最大フレームはフットプリントの拡大／縮小版（すなわち、拡大版）に対応する。フレームは、拡大縮小係数で拡大／縮小されたフットプリントに対応する。例えば、可動オブジェクトがフォントサイズ１０ポイントの文字列である場合、最大フレームはフォントサイズ８０ポイントの当該文字列を囲うバウンディングボックスに対応する。フレームは、オブジェクトをページ上に配置する際に、フットプリントの代わりに用いられる（後述）。
【００２４】
図１Ｄは、本発明の一以上の実施形態に係る、可動オブジェクト用に生成される複数のフレームを示す。図１Ｄに示されるように、複数のＫフレーム（すなわち、フレーム１／１７２、フレーム２／１７４、フレーム３／１７６、・・・、フレームＫ／１７８）は、可動オブジェクトＹ／１９１用に生成されたものである。フレーム１／１７２は最小フレームであり、実質的に、可動オブジェクトＹ／１９１のフットプリントに対応する。一方、フレームＫ／１７８は最大フレームである。
【００２５】
図１Ａに戻り、本発明の一以上の実施形態において、ＰＲＤ１５０はレイアウトエンジン１５２を含む。レイアウトエンジン１５２は、処理するオブジェクト（例えば、ＦＯ、ＭＯ）を選択するように構成されている。処理とは、既にページ上に配置されている他のオブジェクトと重ならないように、当該ページ上にオブジェクト（例えば、ＦＯ、ＭＯ）を配置することである。レイアウトエンジン１５２がオブジェクトを選択する順番は、階層（例えば、ＦＯ階層１３４、ＭＯ階層１３８）に基づく。
【００２６】
また、レイアウトエンジン１５２は、オブジェクト（例えば、ＦＯ、ＭＯ）のフレーム及び／又はフットプリントに対応するＣＰＡ１６０内の粗画素群を特定するように構成されている。更に、レイアウトエンジン１５２は、粗画素群のうち何れかの粗画素が、既に占有状態に設定されているか否か判断するように構成されている。すなわち、本発明の一以上の実施形態において、レイアウトエンジン１５２は、オブジェクト（例えば、ＦＯ、ＭＯ）のフレーム及び／又はフットプリントが、前に描画された一以上のオブジェクト（例えば、ＦＯ、ＭＯ）と重なるか否か判断するように構成されている。
【００２７】
本発明の一以上の実施形態において、レイアウトエンジン１５２は、オブジェクト（例えば、ＦＯ、ＭＯ）について、異なる位置（すなわち、修正された位置又は新たな位置）を選択するように構成されている。この異なる位置は、多数の手段のうちの一つを用いて生成／選択される。その手段は特に制限されないが、アルゴリズム、デフォルトスケジュール（例えば、下、上、左、右、左下、右下、左上、右上）、ランダムロケーションジェネレーター、異なる位置を選択するのに適切なその他の手段などである。
【００２８】
また、レイアウトエンジン１５２は、オブジェクトに対応するＣＰＡ１６０内の粗画素を占有状態に設定するように構成されている。レイアウトエンジン１５２は、オブジェクト（例えば、ＦＯ、ＭＯ）のフレーム及び／又はフットプリントが、他のオブジェクト（例えば、ＦＯ、ＭＯ）と重ならない場合に、当該オブジェクトのフットプリントを占有状態に設定する。更に、レイアウトエンジン１５２は、固定オブジェクト、可動オブジェクト及び背景オブジェクトをページ１７０上に配置して、図１１５をレンダリングするように構成されている。
【００２９】
図２Ａから図２Ｃは、本発明の一以上の実施形態に係るフローチャートを示す。図２Ａから図２Ｃに示される処理は、例えば、図１のシステムによって図をレンダリングする際に用いられる。これらフローチャートには多様なステップが順に示され説明されているが、いくつか又は全てのステップは、異なる順番で実行されてもよく、組み合わせや省略をされてもよい。また、いくつか又は全てのステップは、並行して実行されてもよい。更に、本発明の一以上の実施形態において、後述する一以上のステップは、省略、繰り返し及び／又は異なる順番で実行されてもよい。更に、この方法を実行する際に、図２Ａから図２Ｃでは省略されているステップを追加ステップとして含んでもよい。よって、図２Ａから図２Ｃに示されるステップの具体的な順番は、本発明の範囲を制限するものではない。
【００３０】
本発明の一以上の実施形態において、例えば、図１Ａを参照して上述したコンピューティングデバイスや、図５を参照して後述するコンピューティングデバイスを用いて、後述する一以上のステップを実行する。
【００３１】
図２Ａを参照すると、ステップ２０２において、図内の複数のＦＯ各々のフットプリントを特定する。フットプリントは、図内のＦＯの周長、面積及び／又はバウンディングボックスに対応する。
【００３２】
固定オブジェクトは、ページ上で移動させてもよい。例えば、二つの固定オブジェクトがページ上で重なり合う場合、少なくとも何れかの固定オブジェクトを（例えば、ＭＯの重なり合いを回避する手段と同様の手段で）移動させて、重なり合いを回避する。
【００３３】
ステップ２０４において、図内の複数のＭＯを特定する。本発明の一以上の実施形態において、ＭＯはページ上のＦＯのフットプリントと関連付けられている。例えば、各ＭＯはＦＯを特定及び／又は説明するラベル（すなわち、一のフォントサイズの文字列）である。各ＭＯは図内に初期位置を有する。例えば、ＭＯの初期位置は対応するＦＯに隣接する。
【００３４】
ステップ２０６において、図のページスペースを表すＣＰＡを取得する。本発明の一以上の実施形態において、ＣＰＡは図を表す多次元配列である。また、ＣＰＡの各粗画素は図の一領域に対応する。
【００３５】
ステップ２０８において、フットプリントに対応するＣＰＡ内の粗画素を、占有状態に設定する。本発明の一以上の実施形態において、ＣＰＡはビット配列である。このような実施形態においては、各粗画素は「０」又は「１」に設定される。「１」は占有状態を示すために用いられ、「０」は空き（すなわち、占有されていない）状態を示すために用いられる。
【００３６】
ステップ２０８において、ＦＯの間で重なり合いがある場合、図２Ｂを参照して後述する、ステップ２２８から始まる処理を用いて、ＦＯの間の重なり合いを回避する。
【００３７】
ステップ２１０において、図内の一のＭＯを選択する。本発明の一以上の実施形態において、ＭＯは一手法を用いて選択される。例えば、ＭＯはＭＯ階層に基づいて選択される。ＭＯは他の手法を用いて選択されてもよい。特に制限はされないが、他の手法としては、ＭＯのサイズや位置を用いるものがある。ＭＯの位置は、ページ上のＭＯの初期位置である。ＭＯのフレームを調整する必要がある場合、図２Ｃを参照して後述する、ステップ２４０から始まる処理を用いて、ＭＯのフレームを変更する。
【００３８】
ステップ２１２において、ＭＯのフレームに対応するＣＰＡ内の粗画素群を特定する。粗画素群はＭＯの初期位置に基づく。フレームはＭＯのフットプリントの拡大／縮小版に対応する。
【００３９】
ステップ２１４において、粗画素群のうち少なくとも一の粗画素が占有状態であるか否か判断する。すなわち、ＭＯのフレームが何れかのＦＯ（又はページ上の位置に事前に貼り付けられた他のＭＯ）のフットプリントと重なっているか否か判断する。特定された粗画素群の何れの粗画素も占有状態ではないと判断された場合、ステップ２１６に移行する。粗画素群のうち少なくとも一の粗画素が占有状態であると判断された場合、ステップ２２０に移行する。
【００４０】
ステップ２１６において、粗画素群を占有状態に設定する。すなわち、ＭＯはページ上の初期位置に貼り付けられる。ステップ２１８において、上記複数のＦＯをフットプリントに、上記一のＭＯを初期位置に有する図をレンダリングする。ステップ２１８終了後、本処理を終了する。
【００４１】
ステップ２２０において、上記一のＭＯの修正位置を選択する。ＭＯの修正位置は多数の手段のうちの一つを用いて選択される。例えば、ＭＯの修正位置は、当該ＭＯの初期位置に対して、当該ＭＯが対応するＦＯの反対側となる。ＭＯが関連付けられたＦＯの近隣に利用可能な位置が無い場合、ＭＯの修正位置は関連付けられたＦＯから離れた位置となる。このような場合、修正位置に配置されたＭＯを前述のＦＯと結び付けるために、印を追加する。ＭＯをＦＯと結び付けるために印が追加された場合、この印はＭＯのフットプリントの一部となる。
【００４２】
ステップ２２２において、ＭＯのフレームに対応するＣＰＡ内の修正粗画素群を特定する。修正粗画素群はＭＯの修正位置に基づく。ステップ２２４において、ＭＯの修正粗画素群を占有状態に設定する。すなわち、ＭＯが初期位置に固定されるのは、重なり合いがない場合である。ステップ２２６において、上記複数のＦＯと修正位置に配置された上記一のＭＯを有する図をレンダリングする。ステップ２２６終了後、本処理を終了する。
【００４３】
図２Ｂは、ＦＯ間の重なり合いを解決する方法を説明する。また図２Ｂは、ＦＯをページ上に配列する順番を決定する際に、どのように階層を用いるのかについても説明する。本発明の複数の実施形態は、図２Ｂを参照して説明されるいくつか又は全ての方法を、ＭＯに対しても適用する。図２Ｂのステップ２２８は、例えば、図２Ａのステップ２０８に続くステップである。
【００４４】
図２Ｂを参照すると、ステップ２２８において、第１のＦＯに対応する粗画素を占有状態に設定後、他のＦＯを選択する。本発明の一以上の実施形態において、図１を参照して上述したＦＯ階層を用いて、ＦＯの処理順を選択する。
【００４５】
ステップ２３０において、前記他のＦＯのフレームに対応するＣＰＡ内の粗画素群を特定する。粗画素群は前記他のＦＯの位置に基づく。フレームは、拡大縮小係数に応じて前記他のＦＯのフットプリントを拡大／縮小して算出される。拡大縮小係数は、１よりも小さい（例えば、全てのオブジェクトを重ならずにページ内に収めるために、一以上のオブジェクトのサイズを縮小する必要が場合）、１（すなわち、フレームとフットプリントが同じ）又は１よりも大きい。
【００４６】
ステップ２３２において、粗画素群のうち少なくとも一の粗画素が占有状態に設定されていると判断する。すなわち、前記他のＦＯは、少なくとも一部分、既に初期位置に固定されている第１のＦＯと重なる。よって、第１のＦＯとの重なり合いを回避するために、前記他のＦＯを移動させる必要がある。ステップ２３４において、前記他のＦＯについて修正位置を生成する。前記他のＦＯの修正位置は、ＭＯに対してステップ２２０で説明した手段など多数の手段のうちの一つを用いて生成される。
【００４７】
ステップ２３６において、前記他のＦＯのフレームに対応するＣＰＡ内の修正粗画素群を特定する。修正粗画素群は前記他のＦＯの修正位置に基づく。ステップ２３８において、前記他のＦＯの修正粗画素群を占有状態に設定する。ステップ２３８終了後、本処理は、例えば、図２Ａのステップ２１０に戻る。
【００４８】
図２Ｃは、オブジェクトのフレームを変更する（例えば、フレームを大きくする又は小さくする）方法を説明する。フレームの変更は、ページ上のオブジェクトの重なり合いを低減させる方法として用いられる。例えば、フレームを小さくして、ラベルをページ上の特定の位置に維持する。このような場合、拡大縮小係数を用いてオブジェクトのフットプリントを拡大／縮小して、フレームを算出する。図２Ｃに記載の処理は、ＦＯ及び／又はＭＯのフレームに対して用いられる。図２Ｃのステップ２４０は、例えば、図２Ａのステップ２１０に続くステップである。
【００４９】
図２Ｃを参照すると、ステップ２４０において、ＭＯの初期フレームに対応するＣＰＡ内の初期粗画素群を特定する。ＭＯのフレームに対応する初期粗画素群は、ＭＯの初期位置に基づく。ステップ２４２において、初期粗画素群のうち少なくとも一の粗画素が占有状態に設定されていると判断する。すなわち、ＭＯの初期フレームは、少なくとも一部分、ページ上に既に配置されているオブジェクトと重なる。
【００５０】
ステップ２４４において、修正拡大縮小係数を用いて、ＭＯのフットプリントを拡大／縮小して、異なるフレームを算出する。修正拡大縮小係数は、初期フレームに用いられた拡大縮小係数よりも小さい。本発明の一以上の実施形態においては、修正拡大縮小係数は、初期フレームに用いられた拡大縮小係数よりも大きい。修正拡大縮小係数は、多数の方法のうちの一つを用いて選択される。例えば、所望のフレームサイズ、オブジェクト間の所望のスペース間隔、配置される必要のあるオブジェクトの数及びオブジェクトのフットプリントに基づいて修正拡大縮小係数を決定するアルゴリズムがある。異なるフレームが図２Ａと関連して用いられる場合、当該異なるフレームは、例えば、ステップ２１２のフレームである。
【００５１】
図３Ａから図３Ｊは、本発明の一以上の実施形態に係る例を示す。図３Ａから図３Ｊに示される例は、例えば、システム１００によって、印刷時の重なりを低減させるために用いられる。
【００５２】
本例においては、コロラド州ボルダーの小規模ビール製造所の位置を示す図が存在する。その図は図３Ａに示される。当該図は多数のシンボル（すなわち、正方形）（すなわち、ＦＯ１／４０２、ＦＯ２／４０４、ＦＯ３／４０６、ＦＯ４／４０８、ＦＯ５／４１０、ＦＯ６／４１２、ＦＯ７／４１４、ＦＯ８／４１６、ＦＯ９／４１８、ＦＯ１０／４２０、ＦＯ１１／４２２、ＦＯ１２／４２４、ＦＯ１３／４２６）含む。これらシンボルは固定オブジェクトである。各正方形はコロラド州ボルダーの小規模ビール製造所を示す。また、当該図はラベル（すなわち、ＭＯ１／４３２、ＭＯ２／４３４、ＭＯ３／４３６、ＭＯ４／４３８、ＭＯ５／４４０、ＭＯ６／４４２、ＭＯ７／４４４、ＭＯ８／４４６、ＭＯ９／４４８、ＭＯ１０／４５０、ＭＯ１１／４５２、ＭＯ１２／４５４、ＭＯ１３／４５６）も有する。図３Ａに示されるように、いくつかのオブジェクト（例えば、ＦＯ１２／４２４とＦＯ１３／４２６、ＦＯ６／４１２とＭＯ５／４４０）は重なっている。
【００５３】
ＦＯの処理は、ページ上の最北端（すなわち、ページの上部）に位置するＦＯから始まり、最南端に位置するＦＯまで行われると定める。本例では、最初にＦＯ１／４０２がページ上に配置され、次にＦＯ４／４０８が配置される。そして、最後にＦＯ１３／４２６が配置されるまで当該ページの下部へと進む。
【００５４】
各位置のフットプリント（例えば、正方形）を拡大縮小係数「１」で拡大／縮小してフレームを生成する。すなわち、本例において、各ＦＯのフットプリントとフレームは同じである。また、フレームは正方形の面積で表される。図３Ｂは、図境界４８０と、それぞれの初期位置に位置するＦＯのフレームを示す。
【００５５】
各ＦＯは、互いに重ならないように配置される。図３Ｂに示されるように、ＦＯ１２／４２４とＦＯ１３／４２６を除き、それぞれの初期位置に位置するＦＯの何れも重なっていない。図３Ｃに示されるように、ＦＯ１２／４２４とＦＯ１３／４２６をそれぞれの初期位置から修正位置へ移動させ、ＦＯ１２／４２４の修正位置と初期位置、ＦＯ１３／４２６の修正位置と初期位置を、それぞれ印を用いて結び付けることによって、重なりを回避する。各ＦＯのフットプリントに対応するＣＰＡ内の粗画素は、占有状態に設定される。
【００５６】
ここで、図内のＭＯを配置する。図３Ｄは、互いに重ならないように（上述のようにして）配列されたＦＯと、それぞれの初期位置に位置するＭＯを有する図を示す。ＭＯに関連した重なりが引き続き多数存在する。例えば、ＭＯ５／４４０がＦＯ６／４１２と重なっている。他の例としては、ＭＯ１１／４５２がＦＯ１２／４２４及びＦＯ１３／４２６と重なっている。更に別の例としては、ＭＯ３／４３６とＭＯ２／４３４が重なっており、ＭＯ１２／４５４とＭＯ１３／４５６が重なっている。
【００５７】
本例では、ＭＯの処理は、ページ上の最北端（すなわち、図の上部）のＦＯに関連付けられたＭＯから始まり、図の最南端のＦＯに関連付けられたＭＯまで行われる。本例では、最初にＭＯ１／４３２がページ上に配置され、次にＭＯ４／４３８が配置される。そして、最後にＭＯ１３／４５６が配置されるまで当該ページの下部へと進む。
【００５８】
ＭＯのフットプリントを用いて当該ＭＯのフレームを生成する。図３Ｅは、ページ上のＭＯ（例えば、ＭＯ１／４３２、ＭＯ１３／４５６）のフットプリントを示す。本例において、ＭＯ（例えば、ＭＯ１／４３２、ＭＯ１３／４５６）のフットプリントは、（フットプリントの特定を助ける白抜き文字と共に）黒ボックスで示される。各ＭＯのフットプリント（例えば、長方形）を拡大縮小係数「２」で拡大／縮小して、各ＭＯのフレームを生成する。すなわち、各ＭＯのフレームは、当該ＭＯのフットプリントのサイズの二倍である。図３Ｆは、初期位置にあるＭＯのフレームの例を示す。具体的には、図３Ｆにおいて、フレームＭＯ５−１／４８１は、ＦＯ５／４１０と関連付けられたＭＯ５／４４０（Ｈｅａｖｙ Ｈａｎｄ Ｂｒｅｗｉｎｇ Ｃｏ．）のフレームである。
【００５９】
ＭＯのフレームに対応するＣＰＡ内の粗画素群を特定する。粗画素群のうち少なくとも一の粗画素が占有状態であると判断された場合、フレームを移動させる。この処理は重なりが無くなるまで繰り返される。重なりが無くなると、ＭＯのフットプリントに対応するＣＰＡ内の粗画素が占有状態に設定される（すなわち、ＭＯの位置がページ上で固定される）。図３Ｆから図３Ｉは、ＭＯが重なっている二つのケースを示し、どのようにして重なりが解決されるのかを示す。
【００６０】
図３ＦはＦＯ５／４１０の周りに位置する四つのフレームを示す。各フレームは「Ｈｅａｖｙ Ｈａｎｄ Ｂｒｅｗｉｎｇ Ｃｏ．」と名前の付いたＭＯ５／４４０のフレームである。初期位置に位置するフレームＭＯ５−１／４８１は、当該フレームＭＯ５−１／４８１内の粗画素群の少なくとも一の粗画素が占有状態に設定されているため（すなわち、ＦＯ６／４１２のフットプリントと重なっているため）、使用できない。フレームＭＯ５−１／４８１が使用できないと判断されると、ＭＯ５−２／４８２の処理が試みられる。ここで、フレームＭＯ５−２／４８２内の粗画素群のうち少なくとも一の粗画素は、占有状態に設定されている（すなわち、ＦＯ７／４１４のフットプリント及びＭＯ７／４４４のフレーム（図示なし）と重なっている）。
【００６１】
図３Ｆから引き続き、フレームＭＯ５−２／４８２が使用できないと判断されると、フレームＭＯ５−３／４８３が処理される。ここで、フレームＭＯ５−３／４８３内の粗画素群のうち少なくとも一の粗画素は、占有状態に設定されている（すなわち、ＦＯ７／４１４のフットプリントと重なっている）。そこで、フレームＭＯ５−４／４８４が処理される。ここで、フレームＭＯ５−４／４８４内の粗画素群の粗画素は、何れも占有されていない。ただし、ＭＯ５−４／４８４の一部は図境界４８０の縁を越えて延びている。本発明の一以上の実施形態において、テキストはワードラップされる（すなわち、ＭＯは一ラインのテキストから複数ラインのテキストに変換される）。それにより、ＭＯ５／４４０はフレームＭＯ５−４／４８４内に収まる。
【００６２】
図３ＧはＭＯ５／４４０の処理結果を示す。また、図３Ｇは、ＭＯのフレームは、当該ＭＯが関連付けられたＦＯの真上や真下又は真横ではなく、隣接する位置に配置されてもよいことを示す。具体的には、図３Ｇに示されるＭＯ６／４４２は、当該ＭＯ６／４４２が関連付けられたＦＯ６／４１２の左下に配置される。
【００６３】
図３Ｈは、どのように重なりが解決されるのかについての他の例を示す。ＭＯ１０／４５０とＭＯ１１／４５２は既に配置されている。これらは、それぞれＦＯ１０／４２０、ＦＯ１1／４２２に関連付けられており、ＦＯ１０／４２０とＦＯ１1／４２２はページの上部に位置するためである。ＦＯ１２／４２４はＦＯ１３／４２６よりもページの下部に位置する。一方、ＦＯ１２／４２４からの印はＦＯ１３／４２６からの印よりもページの上部を指し示す。このような場合には、ＭＯ１２／４５４をＭＯ１３／４５６よりも前に処理すると定める。最初にフレームＭＯ１２−１／４９０が処理される。ここで、フレームＭＯ１２−１／４９０内の粗画素群の粗画素は、何れも占有状態に設定されていない（すなわち、何れのＦＯのフットプリント及び／又は何れのＭＯのフレームとも重なっていない）。本例においては、図３Ｈに示される他のフレーム（フレームＭＯ１２−２／４９１、フレームＭＯ１２−３／４９２、フレームＭＯ１２−４／４９３）は何れも処理されないが、説明のために示している。図３Ｈに示される他のフレーム（フレームＭＯ１２−２／４９１、フレームＭＯ１２−３／４９２、フレームＭＯ１２−４／４９３）の何れかが処理される場合、当該フレームの粗画素群のうち少なくとも一の粗画素が占有状態に設定される。図３ＩはＭＯ１２／４５４の処理結果を示す。図３Ｇは、続くＭＯ１３／４５６の処理結果も示す。
【００６４】
図３Ｊは、本発明の実施形態を用いてＦＯ及びＭＯを配列した後にレンダリングした図を示す。
【００６５】
図４は、一以上の実施形態に係るシステム（例えば、図１を参照して説明した、クライアントコンピューター、オブジェクトレイアウトデバイスなど）が実装されたコンピューターシステム５００を示す。図５のコンピューターシステム５００は、用いられているプラットフォームに係らず、実質的に、あらゆるタイプのコンピューターである。例えば、図５に示されるように、コンピューターシステム５００は、集積回路、中央処理装置（ＣＰＵ）又はその他のハードウェアプロセッサーなどの一以上のプロセッサー５０２と、関連するメモリー５０４（例えば、ランダムアクセスメモリー（ＲＡＭ）、キャッシュメモリー、フラッシュメモリーなど）と、記憶装置５０６（例えば、ハードディスク、コンパクトディスクドライブやデジタルビデオディスク（ＤＶＤ）ドライブなどの光学ドライブ、フラッシュメモリースティックなど）と、その他多くの構成要素を含み、今日のコンピューター（図示なし）の有する一般的な機能を備える。コンピューターシステム５００は、キーボード５０８、マウス５１０、マイクロフォン（図示なし）などの入力手段も含んでもよい。また、コンピューターシステム５００は、グラフィックディスプレイ５１２（例えば、液晶ディスプレイ（ＬＣＤ）、発光ダイオード（ＬＥＤ）ディスプレイ、プラズマディスプレイ、ブラウン管（ＣＲＴ）モニター）などの出力手段も含んでもよい。コンピューターシステム５００は、ネットワークインターフェース接続（図示なし）を介して、ネットワーク５１４（例えば、ローカルエリアネットワーク（ＬＡＮ）、インターネットなどの広域ネットワーク（ＷＡＮ）、その他同様のタイプのネットワーク）に接続してもよい。多くの異なるタイプのコンピューターシステムが存在しており、前述の入力手段及び出力手段は、周知の又は今後開発される他の形態を取ってもよい。概括して言えば、コンピューターシステム５００は、少なくとも、本発明の実施形態を実施するために必要な、必要最低限の処理と、入力手段及び／又は出力手段を備える。
【００６６】
また、前述したコンピューターシステム５００の一以上の構成要素は、遠隔に位置し、ネットワークを介して、その他の構成要素と接続してもよい。また、本発明の複数の実施形態は、複数のノードを有する分散システムに実装されてもよく、本発明の各部（例えば、信頼予測エンジン、ソーシャルソース評価モジュール、ソーシャルスコア計算器）は、分散システム内の異なるノードに位置してもよい。本発明の一以上の実施形態において、ノードはコンピューターシステムに対応する。あるいは、ノードは関連する物理メモリーを有するプロセッサーに対応する。または、ノードは共有メモリー及び／又は共有資源を有するプロセッサーに対応する。また、本発明の実施形態を実行するためのソフトウェア指示を、非一時的コンピューター読取可能記憶媒体に記憶させてもよい。非一時的コンピューター読取可能記憶媒体としては、コンパクトディスク（ＣＤ）、ディスケット、テープ、その他の物理的コンピューター読取可能記憶装置がある。
【００６７】
本発明の一以上の実施形態は、１ページ上に一以上のオブジェクトを配列する。具体的には、本発明の実施形態は、オブジェクト同士が重なり合わないように、自動的に、オブジェクトを１ページ上に配列する。また、オブジェクトは、固定オブジェクト又は可動オブジェクトに分類される。固定オブジェクトは、ページ上で（可能ならば）固定された状態を維持する。固定オブジェクトに関連付けられた可動オブジェクトは、固定オブジェクトとの関連性を維持したまま、重なり合い及び／又は群がりを回避するように移動させることができる。
【００６８】
本発明の実施形態は、１ページ上のオブジェクトの重なり合い及び／又は群がりを回避するために、手動で当該ページ上のオブジェクトを移動させる必要がなく、ユーザーの時間を短縮できる。また、本発明の実施形態は、コンピューター処理時間を短縮することもできる。また、（例えば、個々の画素ではなく）ＣＰＡを用いることにより、各オブジェクトを処理し１ページ上に配列させるために使用するメモリー量が低減する。本発明の実施形態は、一の固定オブジェクトに関連付けられた複数の可動オブジェクトを処理することにより、コンピューターリソースを節約することもできる。例えば、オブジェクト又はオブジェクトのフレームの位置を、本発明の実施形態を用いて修正する必要がある場合、影響を受けるのは、ページ上に既に配置されている全てのオブジェクトではなく、可動オブジェクトが関連付けられている固定オブジェクトのみである。すなわち、本発明の実施形態は、一のオブジェクトを移動及び／又は修正する必要がある場合に、既に配置されている全てのオブジェクトに関する値を再度求める必要はない。
【００６９】
限られた数の実施形態を用いて本発明を説明したが、本開示の恩恵に浴する当業者であれば、ここに開示された本発明の範囲から逸脱することなく、他の実施形態を考案できることを理解するであろう。したがって、本発明の範囲は、添付の特許請求の範囲によってのみ制限されるべきである。
【技術分野】
【０００１】
本発明は、グラフィック出力における重なりを回避するためにラベルを移動させる方法、システム及びコンピューター読取可能媒体に関する。
【背景技術】
【０００２】
１ページは、複数のオブジェクトを含む場合がある。これらのオブジェクトには、ページ上の所定の位置に比較的維持されるオブジェクトと、ページ上の多数の位置のうちの何れかの位置に移動させることのできるオブジェクトがある。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
多数のアプリケーションにおいて、１ページは、重なり合う多数のオブジェクトを有する場合がある。これはオブジェクトの読み取りや識別を困難にする。また、オブジェクトが重なり合っていない場合であっても、非常に接近し合ってひとかたまりとなり、明確に解釈できない場合がある。
【課題を解決するための手段】
【０００４】
主として、一側面において、本発明は図をレンダリングする方法に関する。
該方法は、
前記図内に各々フットプリントを有する複数の固定オブジェクトを特定する工程と、
前記図内に各々位置を有し、前記フットプリントと関連付けられた複数の可動オブジェクトを特定する工程と、
コンピュータープロセッサーを用いて、前記図のページスペースを表す粗画素の二次元配列を有する粗画素配列内で、前記フットプリントに対応する粗画素を特定する工程と、
前記コンピュータープロセッサーを用いて、前記フットプリントに対応する前記粗画素を占有状態に設定する工程と、
前記コンピュータープロセッサーを用いて、前記複数の可動オブジェクトのうち第１の位置を有する可動オブジェクトを選択する工程と、
前記コンピュータープロセッサーを用いて、前記第１の位置に基づいて、前記可動オブジェクトの第１のフレームに対応する前記粗画素配列内の第１の粗画素群を特定する工程と、
前記コンピュータープロセッサーを用いて、前記第１の粗画素群のうち少なくとも一の粗画素が前記占有状態であると判断する工程と、
前記コンピュータープロセッサーを用いて、前記第１の粗画素群のうち少なくとも一の粗画素が前記占有状態であると判断された場合に前記可動オブジェクトの第２の位置を生成する工程と、
前記コンピュータープロセッサーを用いて、前記第２の位置に基づいて、前記可動オブジェクトの第２のフレームに対応する前記粗画素配列内の第２の粗画素群を特定する工程と、
前記可動オブジェクトの前記第２の粗画素群を前記占有状態に設定する工程と、
ページ上の前記第２の位置に前記可動オブジェクトを配置して、前記図をレンダリングする工程と、
を備える。
【０００５】
主として、一側面において、本発明は図をレンダリングするシステムに関する。
該システムは、
ハードウェアプロセッサーと、
前記図のページスペースを表す粗画素の二次元配列を有する粗画素配列と、
可動オブジェクトの第１のフレームと第２のフレームを生成するように構成されたフレームモジュールと、
前記ハードウェアプロセッサー上で実行されるレイアウトエンジンと、
を備え、
前記レイアウトエンジンは、
前記図内に各々フットプリントを有する複数の固定オブジェクトを特定し、
前記フットプリントに対応する前記粗画素配列内の粗画素を占有状態に設定し、
前記可動オブジェクトの第１の位置に基づいて、前記第１のフレームに対応する前記粗画素配列内の第１の粗画素群を特定し、
前記第１の粗画素群のうち少なくとも一の粗画素が前記占有状態であると判断し、
前記可動オブジェクトと関連付けられた第２の位置に基づいて、前記可動オブジェクトの前記第２のフレームに対応する前記粗画素配列内の第２の粗画素群を特定し、
ページ上の前記第２の位置に前記可動オブジェクトを配置して、前記図をレンダリングするように構成されている。
【０００６】
主として、一側面において、本発明は図をレンダリングするための指示を記憶する非一時的コンピューター読取可能記憶媒体に関する。
該指示は、
前記図内に各々フットプリントを有する複数の固定オブジェクトを特定するための指示と、
前記図内に位置を有し、前記フットプリントと関連付けられた複数の可動オブジェクトを特定するための指示と、
前記図のページスペースを表す粗画素の二次元配列を有する粗画素配列内で、前記フットプリントに対応する粗画素を特定するための指示と、
前記フットプリントに対応する前記粗画素を占有状態に設定するための指示と、
前記複数の可動オブジェクトのうち第１の位置を有する可動オブジェクトを選択するための指示と、
前記第１の位置に基づいて、前記可動オブジェクトの第１のフレームに対応する前記粗画素配列内の第１の粗画素群を特定するための指示と、
前記第１の粗画素群のうち少なくとも一の粗画素が前記占有状態であると判断するための指示と、
前記第１の粗画素群のうち少なくとも一の粗画素が前記占有状態であると判断された場合に前記可動オブジェクトの第２の位置を生成するための指示と、
前記第２の位置に基づいて、前記可動オブジェクトの第２のフレームに対応する前記粗画素配列内で第２の粗画素群を特定するための指示と、
前記可動オブジェクトの前記第２の粗画素群を前記占有状態に設定するための指示と、
ページ上の前記第２の位置に前記可動オブジェクトを配置して、前記図をレンダリングするための指示と、
を備える。
【０００７】
本発明のその他の側面は、以下の説明及び添付の特許請求の範囲から明らかである。
【図面の簡単な説明】
【０００８】
【図１Ａ】本発明の一以上の実施形態に係るシステムのブロック図を示す。
【図１Ｂ】本発明の一以上の実施形態に係る複数のオブジェクトを有する図を示す。
【図１Ｃ】本発明の一以上の実施形態に係る図及び粗画素配列（ＣＰＡ）を示す。
【図１Ｄ】本発明の一以上の実施形態に係る可動オブジェクト用に生成される複数のフレームを示す。
【図２Ａ】本発明の一以上の実施形態に係るフローチャートを示す。
【図２Ｂ】本発明の一以上の実施形態に係るフローチャートを示す。
【図２Ｃ】本発明の一以上の実施形態に係るフローチャートを示す。
【図３Ａ】本発明の一以上の実施形態に係る例を示す。
【図３Ｂ】本発明の一以上の実施形態に係る例を示す。
【図３Ｃ】本発明の一以上の実施形態に係る例を示す。
【図３Ｄ】本発明の一以上の実施形態に係る例を示す。
【図３Ｅ】本発明の一以上の実施形態に係る例を示す。
【図３Ｆ】本発明の一以上の実施形態に係る例を示す。
【図３Ｇ】本発明の一以上の実施形態に係る例を示す。
【図３Ｈ】本発明の一以上の実施形態に係る例を示す。
【図３Ｉ】本発明の一以上の実施形態に係る例を示す。
【図３Ｊ】本発明の一以上の実施形態に係る例を示す。
【図４】本発明の一以上の実施形態に係るコンピューターシステムを示す。
【発明を実施するための形態】
【０００９】
本発明の具体的な実施形態を、添付の図面を参照して詳細に説明する。複数の図に示される同様の構成要素は、一貫性を保つために同様の参照符号で示す。
【００１０】
以下の本発明に係る実施形態の詳細な説明には、本発明についてより完全な理解を提供するために、数多くの詳細を示す。しかし、当業者には、これらの詳細を用いずとも本発明の実施が可能であることは明らかであろう。他の例においては、不要に複雑な説明となるのを避けるため、周知の特徴に関しては詳細な説明は省略する。
【００１１】
主として、本発明の実施形態は、１ページに複数のオブジェクト（すなわち、固定オブジェクト、可動オブジェクト）を配置するシステム及び方法を提供する。具体的には、複数の固定オブジェクト、そしてそれらに伴う可動オブジェクトを、互いに重なり合わないように１ページ上に配置する。粗画素配列（Ｃｏａｒｓｅ Ｐｉｘｅｌ Ａｒｒａｙ；ＣＰＡ）は粗画素の二次元配列であり、オブジェクトを有する図のページスペースを表す。ページ上の一の位置に配置されるオブジェクトは、ＣＰＡに位置する粗画素群によって表される。この粗画素群は占有状態に設定される。配置される必要のあるオブジェクトは、当該オブジェクトの粗画素群によって表され、初期位置に配置される。このオブジェクトの粗画素群のうち少なくとも一の粗画素が既に占有状態である場合、新たな位置が使用される。この処理は、全てのオブジェクトがページ上に配置されるまで（すなわち、図がレンダリングされるまで）繰り返される。本発明の実施形態において、オブジェクトは、当該オブジェクトのフットプリントの拡大／縮小版に対応するフレームを用いて配置される。
【００１２】
図１は、本発明の一以上の実施形態に係るシステム１００を示す。図１に示されるように、システム１００は、ページレンダリングデバイス（ＰＲＤ）１５０と、ストレージリポジトリ１３０と、クライアントコンピューター１０５とを含む、複数の構成要素を備える。ＰＲＤ１５０は、プリンター、電子読取装置などである。コンピューティングデバイス１０５は、パーソナルコンピューター（ＰＣ）、デスクトップコンピューター、汎用コンピューター、サーバー、電話、公共電話ボックス、ケーブルボックス、携帯情報端末（ＰＤＡ）、電子読取装置、携帯電話、スマートフォンなどである。ストレージリポジトリ１３０は、ハードウェア記憶装置（例えば、ハードドライブ、テープ、メモリー等）の何れかの種類に対応する。コンピューティングデバイス１０５と、ＰＲＤ１５０と、ストレージリポジトリ１３０は、直接的に接続されてもよい（例えば、ユニバーサルシリアルバス（ＵＳＢ）接続など）。あるいは、コンピューティングデバイス１０５と、ＰＲＤ１５０と、ストレージリポジトリ１３０は、有線部分及び／又は無線部分を有するネットワーク１２０を用いて接続されてもよい。
【００１３】
本発明の一以上の実施形態において、ＰＲＤ１５０及び／又は記憶装置１３０はコンピューティングデバイス１０５上に位置する。このような実施形態では、ＰＲＤ１５０は、コンピューティングデバイス１０５上の、図をレンダリングするためのハードウェアとソフトウェアの組み合わせに対応する。本発明の一以上の実施形態において、記憶装置１３０はＰＲＤ１５０上に位置する。
【００１４】
本発明の一以上の実施形態において、コンピューティングデバイス１０５はユーザーアプリケーション１１０を実行する。ユーザーアプリケーション１１０はユーザーによって操作されるソフトウェアアプリケーションであり、図（例えば、図１１５）を取得、入力、生成、表示及び／又は印刷するように構成されている。よって、ユーザーアプリケーション１１０は、ワードプロセッシングアプリケーション、表計算アプリケーション、デスクトップパブリッシングアプリケーション、グラフィックアプリケーション、写真印刷アプリケーション、インターネットブラウザー、地図作成アプリケーション、グラフィカラルプロットアプリケーションなどである。ユーザーアプリケーション１１０は、新たな図を生成及び／又は事前に保存した図を取得する。
【００１５】
本発明の一以上の実施形態において、図１１５は、一以上の固定オブジェクトと一以上の可動オブジェクトを含む。図１１５は、一以上の背景オブジェクトを含んでもよい。背景オブジェクトは、上から重ねて印刷されてもよい図内のアイテムに対応する。背景オブジェクトの例としては、背景画像、多角形フィル、シンボル、線（例えば、表内の縦横拡大縮小線）などがある。固定オブジェクトは、図内に位置を有し、図全体に意味を付与する当該図内のアイテムに対応する。本発明の一以上の実施形態において、固定オブジェクトは上から重ねて印刷されてはならない。固定オブジェクトの例としては、クリップアート、形、散布データ図のマーカー、地図上のシンボルなどがある。一方、可動オブジェクトは、図の全体的な意味を変えずに再配置することが可能な図内のアイテムに対応する。可動オブジェクトは、固定オブジェクトを特定及び／又は説明するために用いられる。例えば、可動オブジェクトは、固定オブジェクトを特定及び／又は説明する文字列（すなわち、ラベル）である。
【００１６】
本発明の一以上の実施形態において、図１１５内の複数の固定オブジェクトと、図１１５内の複数の可動オブジェクトは、ランク付けされる（すなわち、優先順位が付けられる）。すなわち、固定オブジェクトの階層と可動オブジェクトの階層が存在する。記憶装置１３０は、図１１５内の全固定オブジェクトのリスト（すなわち、固定オブジェクト（ＦＯ）リスト１３２）と、図１１５内の全可動オブジェクトのリスト（すなわち、可動オブジェクト（ＭＯ）リスト１３６）を含む。ＦＯ階層１３４は、図１１５内の固定オブジェクトのランクを特定する。同様に、ＭＯ階層１３８は、図１１５内の可動オブジェクトのランクを特定する。
【００１７】
図１Ｂは、本発明の一以上の実施形態に係る図（すなわち、図Ｘ／１９９）を示す。図１Ｂに示されるように、図Ｘ／１９９は、複数の固定オブジェクト（すなわち、固定オブジェクトＡ／１９７、固定オブジェクトＢ／１９３）と、複数の可動オブジェクト（すなわち、可動オブジェクトＸ／１９５、可動オブジェクトＹ／１９３）と、背景オブジェクト１８０を含む。固定オブジェクトＡ／１９７はクリップアート要素であり、可動オブジェクトＸ／１９５は固定オブジェクトＡ／１９７を特定し説明する文字列（すなわち、「ＥＬＥＰＨＡＮＴ」（象））である。固定オブジェクトＢ／１９３はシンボルであり、可動オブジェクトＹ／１９１は固定オブジェクトＢ／１９１を特定し説明する文字列（すなわち、「ＡＵＳＴＩＮ」（オースティン））である。また、同じく図１Ｂに示されるように、固定オブジェクトＢ／１９３と可動オブジェクトＹ／１９１は背景画像１８０上に印刷される。また、可動オブジェクトＸ／１９５は対応する固定オブジェクトＡ／１９７に隣接しており、可動オブジェクトＹ／１９１は対応する固定オブジェクトＢ／１９３に隣接している。
【００１８】
本詳細な説明の恩恵に浴する当業者であれば、可動オブジェクトＸ／１９５と可動オブジェクトＹ／１９１は、それぞれが対応する固定オブジェクトを特定し説明しながら、図Ｘ／１９９の意味を曲解させることなく、再配置される場合があることを理解するであろう。例えば、可動オブジェクトＸ／１９５は、対応する固定オブジェクトＡ／１９７を特定し説明しながら、図Ｘ／１９９の意味を曲解させることなく、当該固定オブジェクトＡ／１９７の近傍に再配置される場合がある。同様に、可動オブジェクトＹ／１９１は、対応する固定オブジェクトＢ／１９５を特定し説明しながら、図Ｘ／１９９の意味を曲解させることなく、当該固定オブジェクトＢ／１９５の近傍に再配置される場合がある。
【００１９】
また、本詳細な説明の恩恵に浴する当業者であれば、図は、固定オブジェクト及び可動オブジェクトをいくつ有してもよいことを理解するであろう。そのため、多数の可動オブジェクトが存在する場合、可動オブジェクトが重なり合う場合がある。このような場合は、図の読み取り及び理解を容易にするため、一以上の可動オブジェクトを初期位置から新たな位置へと再配置する。可動オブジェクトの初期位置は、図内で指定される。
【００２０】
図１Ａに戻り、本発明の一以上の実施形態において、ＰＲＤ１５０は粗画素配列（ＣＰＡ）１５８を含む。ＣＰＡ１５８は、図１１５のページスペースを表す多次元（すなわち、二次元）配列である。ＣＰＡ１５８の有する粗画素数はいくつであってもよい。本発明の一以上の実施形態において、各粗画素は図１１５のｘ／７２ｉｎ２に対応する。ｘは図１１５で使用される最小のフォントサイズである。
【００２１】
本発明の一以上の実施形態において、ＣＰＡ１５８は固定オブジェクト及び可動オブジェクトがどこに描画されたのかを記録又は追跡する。具体的には、描画された固定オブジェクト及び可動オブジェクトのフットプリント（すなわち、面積、周長及び／又はバウンディングボックス）に対応するＣＰＡ１５８内の粗画素は、占有状態に設定される。本発明の一以上の実施形態において、ＣＰＡ１５８はビット配列である。このような実施形態においては、値「０」を有する粗画素は全て空き（すなわち、占有されていない）状態であり、値「１」を有する粗画素は全て占有状態である。本詳細な説明の恩恵に浴する当業者であれば、占有状態と空き（すなわち、占有されていない）状態を示す二つの値には、いかなる値を使用してもよいことを理解するであろう。
【００２２】
図１Ｃは、本発明の一以上の実施形態に係る粗画素配列１９０を示す。ＣＰＡ１９０は図Ｘ／１９９を表す。図１Ｃに示されるように、固定オブジェクト及び可動オブジェクトのフットプリントに対応するＣＰＡ１９０内の粗画素は、占有状態に設定される。例えば、フットプリントＡ／１８７は固定オブジェクトＡ／１９７に対応する。よって、フットプリントＡ／１８７に対応する粗画素は占有状態に設定される。同様に、フットプリントＢ／１８３は固定オブジェクトＢ／１９３に対応する。よって、フットプリントＢ／１８３に対応する粗画素は占有状態に設定される。また、フットプリントＸ／１８５は可動オブジェクトＸ／１９５に対応する。よって、フットプリントＸ／１８５に対応する粗画素は占有状態に設定される。更に、フットプリントＹ／１８１は可動オブジェクトＹ／１９１に対応する。よって、フットプリントＹ／１８１に対応する粗画素は占有状態に設定される。本発明の一以上の実施形態において、ＣＰＡ１９０は背景オブジェクト（例えば、背景オブジェクト１８０）のフットプリントを記録／追跡しない。
【００２３】
図１Ａに戻り、本発明の一以上の実施形態において、ＰＲＤ１５０はフレームモジュール１６０を含む。フレームモジュール１６０は図１１５内の各可動オブジェクトについて、サイズの異なる複数のフレームを算出するように構成されている。また、本発明の一以上の実施形態において、フレームモジュール１６０は、固定オブジェクトが重なり合う場合、重なり合っている固定オブジェクトのうち一以上の固定オブジェクトについて、フレームを算出するように構成されている。各フレームは、実質的に、可動オブジェクト又は固定オブジェクトを囲うコンテナーである。よって、最小フレームはオブジェクトのフットプリントに対応し、最大フレームはフットプリントの拡大／縮小版（すなわち、拡大版）に対応する。フレームは、拡大縮小係数で拡大／縮小されたフットプリントに対応する。例えば、可動オブジェクトがフォントサイズ１０ポイントの文字列である場合、最大フレームはフォントサイズ８０ポイントの当該文字列を囲うバウンディングボックスに対応する。フレームは、オブジェクトをページ上に配置する際に、フットプリントの代わりに用いられる（後述）。
【００２４】
図１Ｄは、本発明の一以上の実施形態に係る、可動オブジェクト用に生成される複数のフレームを示す。図１Ｄに示されるように、複数のＫフレーム（すなわち、フレーム１／１７２、フレーム２／１７４、フレーム３／１７６、・・・、フレームＫ／１７８）は、可動オブジェクトＹ／１９１用に生成されたものである。フレーム１／１７２は最小フレームであり、実質的に、可動オブジェクトＹ／１９１のフットプリントに対応する。一方、フレームＫ／１７８は最大フレームである。
【００２５】
図１Ａに戻り、本発明の一以上の実施形態において、ＰＲＤ１５０はレイアウトエンジン１５２を含む。レイアウトエンジン１５２は、処理するオブジェクト（例えば、ＦＯ、ＭＯ）を選択するように構成されている。処理とは、既にページ上に配置されている他のオブジェクトと重ならないように、当該ページ上にオブジェクト（例えば、ＦＯ、ＭＯ）を配置することである。レイアウトエンジン１５２がオブジェクトを選択する順番は、階層（例えば、ＦＯ階層１３４、ＭＯ階層１３８）に基づく。
【００２６】
また、レイアウトエンジン１５２は、オブジェクト（例えば、ＦＯ、ＭＯ）のフレーム及び／又はフットプリントに対応するＣＰＡ１６０内の粗画素群を特定するように構成されている。更に、レイアウトエンジン１５２は、粗画素群のうち何れかの粗画素が、既に占有状態に設定されているか否か判断するように構成されている。すなわち、本発明の一以上の実施形態において、レイアウトエンジン１５２は、オブジェクト（例えば、ＦＯ、ＭＯ）のフレーム及び／又はフットプリントが、前に描画された一以上のオブジェクト（例えば、ＦＯ、ＭＯ）と重なるか否か判断するように構成されている。
【００２７】
本発明の一以上の実施形態において、レイアウトエンジン１５２は、オブジェクト（例えば、ＦＯ、ＭＯ）について、異なる位置（すなわち、修正された位置又は新たな位置）を選択するように構成されている。この異なる位置は、多数の手段のうちの一つを用いて生成／選択される。その手段は特に制限されないが、アルゴリズム、デフォルトスケジュール（例えば、下、上、左、右、左下、右下、左上、右上）、ランダムロケーションジェネレーター、異なる位置を選択するのに適切なその他の手段などである。
【００２８】
また、レイアウトエンジン１５２は、オブジェクトに対応するＣＰＡ１６０内の粗画素を占有状態に設定するように構成されている。レイアウトエンジン１５２は、オブジェクト（例えば、ＦＯ、ＭＯ）のフレーム及び／又はフットプリントが、他のオブジェクト（例えば、ＦＯ、ＭＯ）と重ならない場合に、当該オブジェクトのフットプリントを占有状態に設定する。更に、レイアウトエンジン１５２は、固定オブジェクト、可動オブジェクト及び背景オブジェクトをページ１７０上に配置して、図１１５をレンダリングするように構成されている。
【００２９】
図２Ａから図２Ｃは、本発明の一以上の実施形態に係るフローチャートを示す。図２Ａから図２Ｃに示される処理は、例えば、図１のシステムによって図をレンダリングする際に用いられる。これらフローチャートには多様なステップが順に示され説明されているが、いくつか又は全てのステップは、異なる順番で実行されてもよく、組み合わせや省略をされてもよい。また、いくつか又は全てのステップは、並行して実行されてもよい。更に、本発明の一以上の実施形態において、後述する一以上のステップは、省略、繰り返し及び／又は異なる順番で実行されてもよい。更に、この方法を実行する際に、図２Ａから図２Ｃでは省略されているステップを追加ステップとして含んでもよい。よって、図２Ａから図２Ｃに示されるステップの具体的な順番は、本発明の範囲を制限するものではない。
【００３０】
本発明の一以上の実施形態において、例えば、図１Ａを参照して上述したコンピューティングデバイスや、図５を参照して後述するコンピューティングデバイスを用いて、後述する一以上のステップを実行する。
【００３１】
図２Ａを参照すると、ステップ２０２において、図内の複数のＦＯ各々のフットプリントを特定する。フットプリントは、図内のＦＯの周長、面積及び／又はバウンディングボックスに対応する。
【００３２】
固定オブジェクトは、ページ上で移動させてもよい。例えば、二つの固定オブジェクトがページ上で重なり合う場合、少なくとも何れかの固定オブジェクトを（例えば、ＭＯの重なり合いを回避する手段と同様の手段で）移動させて、重なり合いを回避する。
【００３３】
ステップ２０４において、図内の複数のＭＯを特定する。本発明の一以上の実施形態において、ＭＯはページ上のＦＯのフットプリントと関連付けられている。例えば、各ＭＯはＦＯを特定及び／又は説明するラベル（すなわち、一のフォントサイズの文字列）である。各ＭＯは図内に初期位置を有する。例えば、ＭＯの初期位置は対応するＦＯに隣接する。
【００３４】
ステップ２０６において、図のページスペースを表すＣＰＡを取得する。本発明の一以上の実施形態において、ＣＰＡは図を表す多次元配列である。また、ＣＰＡの各粗画素は図の一領域に対応する。
【００３５】
ステップ２０８において、フットプリントに対応するＣＰＡ内の粗画素を、占有状態に設定する。本発明の一以上の実施形態において、ＣＰＡはビット配列である。このような実施形態においては、各粗画素は「０」又は「１」に設定される。「１」は占有状態を示すために用いられ、「０」は空き（すなわち、占有されていない）状態を示すために用いられる。
【００３６】
ステップ２０８において、ＦＯの間で重なり合いがある場合、図２Ｂを参照して後述する、ステップ２２８から始まる処理を用いて、ＦＯの間の重なり合いを回避する。
【００３７】
ステップ２１０において、図内の一のＭＯを選択する。本発明の一以上の実施形態において、ＭＯは一手法を用いて選択される。例えば、ＭＯはＭＯ階層に基づいて選択される。ＭＯは他の手法を用いて選択されてもよい。特に制限はされないが、他の手法としては、ＭＯのサイズや位置を用いるものがある。ＭＯの位置は、ページ上のＭＯの初期位置である。ＭＯのフレームを調整する必要がある場合、図２Ｃを参照して後述する、ステップ２４０から始まる処理を用いて、ＭＯのフレームを変更する。
【００３８】
ステップ２１２において、ＭＯのフレームに対応するＣＰＡ内の粗画素群を特定する。粗画素群はＭＯの初期位置に基づく。フレームはＭＯのフットプリントの拡大／縮小版に対応する。
【００３９】
ステップ２１４において、粗画素群のうち少なくとも一の粗画素が占有状態であるか否か判断する。すなわち、ＭＯのフレームが何れかのＦＯ（又はページ上の位置に事前に貼り付けられた他のＭＯ）のフットプリントと重なっているか否か判断する。特定された粗画素群の何れの粗画素も占有状態ではないと判断された場合、ステップ２１６に移行する。粗画素群のうち少なくとも一の粗画素が占有状態であると判断された場合、ステップ２２０に移行する。
【００４０】
ステップ２１６において、粗画素群を占有状態に設定する。すなわち、ＭＯはページ上の初期位置に貼り付けられる。ステップ２１８において、上記複数のＦＯをフットプリントに、上記一のＭＯを初期位置に有する図をレンダリングする。ステップ２１８終了後、本処理を終了する。
【００４１】
ステップ２２０において、上記一のＭＯの修正位置を選択する。ＭＯの修正位置は多数の手段のうちの一つを用いて選択される。例えば、ＭＯの修正位置は、当該ＭＯの初期位置に対して、当該ＭＯが対応するＦＯの反対側となる。ＭＯが関連付けられたＦＯの近隣に利用可能な位置が無い場合、ＭＯの修正位置は関連付けられたＦＯから離れた位置となる。このような場合、修正位置に配置されたＭＯを前述のＦＯと結び付けるために、印を追加する。ＭＯをＦＯと結び付けるために印が追加された場合、この印はＭＯのフットプリントの一部となる。
【００４２】
ステップ２２２において、ＭＯのフレームに対応するＣＰＡ内の修正粗画素群を特定する。修正粗画素群はＭＯの修正位置に基づく。ステップ２２４において、ＭＯの修正粗画素群を占有状態に設定する。すなわち、ＭＯが初期位置に固定されるのは、重なり合いがない場合である。ステップ２２６において、上記複数のＦＯと修正位置に配置された上記一のＭＯを有する図をレンダリングする。ステップ２２６終了後、本処理を終了する。
【００４３】
図２Ｂは、ＦＯ間の重なり合いを解決する方法を説明する。また図２Ｂは、ＦＯをページ上に配列する順番を決定する際に、どのように階層を用いるのかについても説明する。本発明の複数の実施形態は、図２Ｂを参照して説明されるいくつか又は全ての方法を、ＭＯに対しても適用する。図２Ｂのステップ２２８は、例えば、図２Ａのステップ２０８に続くステップである。
【００４４】
図２Ｂを参照すると、ステップ２２８において、第１のＦＯに対応する粗画素を占有状態に設定後、他のＦＯを選択する。本発明の一以上の実施形態において、図１を参照して上述したＦＯ階層を用いて、ＦＯの処理順を選択する。
【００４５】
ステップ２３０において、前記他のＦＯのフレームに対応するＣＰＡ内の粗画素群を特定する。粗画素群は前記他のＦＯの位置に基づく。フレームは、拡大縮小係数に応じて前記他のＦＯのフットプリントを拡大／縮小して算出される。拡大縮小係数は、１よりも小さい（例えば、全てのオブジェクトを重ならずにページ内に収めるために、一以上のオブジェクトのサイズを縮小する必要が場合）、１（すなわち、フレームとフットプリントが同じ）又は１よりも大きい。
【００４６】
ステップ２３２において、粗画素群のうち少なくとも一の粗画素が占有状態に設定されていると判断する。すなわち、前記他のＦＯは、少なくとも一部分、既に初期位置に固定されている第１のＦＯと重なる。よって、第１のＦＯとの重なり合いを回避するために、前記他のＦＯを移動させる必要がある。ステップ２３４において、前記他のＦＯについて修正位置を生成する。前記他のＦＯの修正位置は、ＭＯに対してステップ２２０で説明した手段など多数の手段のうちの一つを用いて生成される。
【００４７】
ステップ２３６において、前記他のＦＯのフレームに対応するＣＰＡ内の修正粗画素群を特定する。修正粗画素群は前記他のＦＯの修正位置に基づく。ステップ２３８において、前記他のＦＯの修正粗画素群を占有状態に設定する。ステップ２３８終了後、本処理は、例えば、図２Ａのステップ２１０に戻る。
【００４８】
図２Ｃは、オブジェクトのフレームを変更する（例えば、フレームを大きくする又は小さくする）方法を説明する。フレームの変更は、ページ上のオブジェクトの重なり合いを低減させる方法として用いられる。例えば、フレームを小さくして、ラベルをページ上の特定の位置に維持する。このような場合、拡大縮小係数を用いてオブジェクトのフットプリントを拡大／縮小して、フレームを算出する。図２Ｃに記載の処理は、ＦＯ及び／又はＭＯのフレームに対して用いられる。図２Ｃのステップ２４０は、例えば、図２Ａのステップ２１０に続くステップである。
【００４９】
図２Ｃを参照すると、ステップ２４０において、ＭＯの初期フレームに対応するＣＰＡ内の初期粗画素群を特定する。ＭＯのフレームに対応する初期粗画素群は、ＭＯの初期位置に基づく。ステップ２４２において、初期粗画素群のうち少なくとも一の粗画素が占有状態に設定されていると判断する。すなわち、ＭＯの初期フレームは、少なくとも一部分、ページ上に既に配置されているオブジェクトと重なる。
【００５０】
ステップ２４４において、修正拡大縮小係数を用いて、ＭＯのフットプリントを拡大／縮小して、異なるフレームを算出する。修正拡大縮小係数は、初期フレームに用いられた拡大縮小係数よりも小さい。本発明の一以上の実施形態においては、修正拡大縮小係数は、初期フレームに用いられた拡大縮小係数よりも大きい。修正拡大縮小係数は、多数の方法のうちの一つを用いて選択される。例えば、所望のフレームサイズ、オブジェクト間の所望のスペース間隔、配置される必要のあるオブジェクトの数及びオブジェクトのフットプリントに基づいて修正拡大縮小係数を決定するアルゴリズムがある。異なるフレームが図２Ａと関連して用いられる場合、当該異なるフレームは、例えば、ステップ２１２のフレームである。
【００５１】
図３Ａから図３Ｊは、本発明の一以上の実施形態に係る例を示す。図３Ａから図３Ｊに示される例は、例えば、システム１００によって、印刷時の重なりを低減させるために用いられる。
【００５２】
本例においては、コロラド州ボルダーの小規模ビール製造所の位置を示す図が存在する。その図は図３Ａに示される。当該図は多数のシンボル（すなわち、正方形）（すなわち、ＦＯ１／４０２、ＦＯ２／４０４、ＦＯ３／４０６、ＦＯ４／４０８、ＦＯ５／４１０、ＦＯ６／４１２、ＦＯ７／４１４、ＦＯ８／４１６、ＦＯ９／４１８、ＦＯ１０／４２０、ＦＯ１１／４２２、ＦＯ１２／４２４、ＦＯ１３／４２６）含む。これらシンボルは固定オブジェクトである。各正方形はコロラド州ボルダーの小規模ビール製造所を示す。また、当該図はラベル（すなわち、ＭＯ１／４３２、ＭＯ２／４３４、ＭＯ３／４３６、ＭＯ４／４３８、ＭＯ５／４４０、ＭＯ６／４４２、ＭＯ７／４４４、ＭＯ８／４４６、ＭＯ９／４４８、ＭＯ１０／４５０、ＭＯ１１／４５２、ＭＯ１２／４５４、ＭＯ１３／４５６）も有する。図３Ａに示されるように、いくつかのオブジェクト（例えば、ＦＯ１２／４２４とＦＯ１３／４２６、ＦＯ６／４１２とＭＯ５／４４０）は重なっている。
【００５３】
ＦＯの処理は、ページ上の最北端（すなわち、ページの上部）に位置するＦＯから始まり、最南端に位置するＦＯまで行われると定める。本例では、最初にＦＯ１／４０２がページ上に配置され、次にＦＯ４／４０８が配置される。そして、最後にＦＯ１３／４２６が配置されるまで当該ページの下部へと進む。
【００５４】
各位置のフットプリント（例えば、正方形）を拡大縮小係数「１」で拡大／縮小してフレームを生成する。すなわち、本例において、各ＦＯのフットプリントとフレームは同じである。また、フレームは正方形の面積で表される。図３Ｂは、図境界４８０と、それぞれの初期位置に位置するＦＯのフレームを示す。
【００５５】
各ＦＯは、互いに重ならないように配置される。図３Ｂに示されるように、ＦＯ１２／４２４とＦＯ１３／４２６を除き、それぞれの初期位置に位置するＦＯの何れも重なっていない。図３Ｃに示されるように、ＦＯ１２／４２４とＦＯ１３／４２６をそれぞれの初期位置から修正位置へ移動させ、ＦＯ１２／４２４の修正位置と初期位置、ＦＯ１３／４２６の修正位置と初期位置を、それぞれ印を用いて結び付けることによって、重なりを回避する。各ＦＯのフットプリントに対応するＣＰＡ内の粗画素は、占有状態に設定される。
【００５６】
ここで、図内のＭＯを配置する。図３Ｄは、互いに重ならないように（上述のようにして）配列されたＦＯと、それぞれの初期位置に位置するＭＯを有する図を示す。ＭＯに関連した重なりが引き続き多数存在する。例えば、ＭＯ５／４４０がＦＯ６／４１２と重なっている。他の例としては、ＭＯ１１／４５２がＦＯ１２／４２４及びＦＯ１３／４２６と重なっている。更に別の例としては、ＭＯ３／４３６とＭＯ２／４３４が重なっており、ＭＯ１２／４５４とＭＯ１３／４５６が重なっている。
【００５７】
本例では、ＭＯの処理は、ページ上の最北端（すなわち、図の上部）のＦＯに関連付けられたＭＯから始まり、図の最南端のＦＯに関連付けられたＭＯまで行われる。本例では、最初にＭＯ１／４３２がページ上に配置され、次にＭＯ４／４３８が配置される。そして、最後にＭＯ１３／４５６が配置されるまで当該ページの下部へと進む。
【００５８】
ＭＯのフットプリントを用いて当該ＭＯのフレームを生成する。図３Ｅは、ページ上のＭＯ（例えば、ＭＯ１／４３２、ＭＯ１３／４５６）のフットプリントを示す。本例において、ＭＯ（例えば、ＭＯ１／４３２、ＭＯ１３／４５６）のフットプリントは、（フットプリントの特定を助ける白抜き文字と共に）黒ボックスで示される。各ＭＯのフットプリント（例えば、長方形）を拡大縮小係数「２」で拡大／縮小して、各ＭＯのフレームを生成する。すなわち、各ＭＯのフレームは、当該ＭＯのフットプリントのサイズの二倍である。図３Ｆは、初期位置にあるＭＯのフレームの例を示す。具体的には、図３Ｆにおいて、フレームＭＯ５−１／４８１は、ＦＯ５／４１０と関連付けられたＭＯ５／４４０（Ｈｅａｖｙ Ｈａｎｄ Ｂｒｅｗｉｎｇ Ｃｏ．）のフレームである。
【００５９】
ＭＯのフレームに対応するＣＰＡ内の粗画素群を特定する。粗画素群のうち少なくとも一の粗画素が占有状態であると判断された場合、フレームを移動させる。この処理は重なりが無くなるまで繰り返される。重なりが無くなると、ＭＯのフットプリントに対応するＣＰＡ内の粗画素が占有状態に設定される（すなわち、ＭＯの位置がページ上で固定される）。図３Ｆから図３Ｉは、ＭＯが重なっている二つのケースを示し、どのようにして重なりが解決されるのかを示す。
【００６０】
図３ＦはＦＯ５／４１０の周りに位置する四つのフレームを示す。各フレームは「Ｈｅａｖｙ Ｈａｎｄ Ｂｒｅｗｉｎｇ Ｃｏ．」と名前の付いたＭＯ５／４４０のフレームである。初期位置に位置するフレームＭＯ５−１／４８１は、当該フレームＭＯ５−１／４８１内の粗画素群の少なくとも一の粗画素が占有状態に設定されているため（すなわち、ＦＯ６／４１２のフットプリントと重なっているため）、使用できない。フレームＭＯ５−１／４８１が使用できないと判断されると、ＭＯ５−２／４８２の処理が試みられる。ここで、フレームＭＯ５−２／４８２内の粗画素群のうち少なくとも一の粗画素は、占有状態に設定されている（すなわち、ＦＯ７／４１４のフットプリント及びＭＯ７／４４４のフレーム（図示なし）と重なっている）。
【００６１】
図３Ｆから引き続き、フレームＭＯ５−２／４８２が使用できないと判断されると、フレームＭＯ５−３／４８３が処理される。ここで、フレームＭＯ５−３／４８３内の粗画素群のうち少なくとも一の粗画素は、占有状態に設定されている（すなわち、ＦＯ７／４１４のフットプリントと重なっている）。そこで、フレームＭＯ５−４／４８４が処理される。ここで、フレームＭＯ５−４／４８４内の粗画素群の粗画素は、何れも占有されていない。ただし、ＭＯ５−４／４８４の一部は図境界４８０の縁を越えて延びている。本発明の一以上の実施形態において、テキストはワードラップされる（すなわち、ＭＯは一ラインのテキストから複数ラインのテキストに変換される）。それにより、ＭＯ５／４４０はフレームＭＯ５−４／４８４内に収まる。
【００６２】
図３ＧはＭＯ５／４４０の処理結果を示す。また、図３Ｇは、ＭＯのフレームは、当該ＭＯが関連付けられたＦＯの真上や真下又は真横ではなく、隣接する位置に配置されてもよいことを示す。具体的には、図３Ｇに示されるＭＯ６／４４２は、当該ＭＯ６／４４２が関連付けられたＦＯ６／４１２の左下に配置される。
【００６３】
図３Ｈは、どのように重なりが解決されるのかについての他の例を示す。ＭＯ１０／４５０とＭＯ１１／４５２は既に配置されている。これらは、それぞれＦＯ１０／４２０、ＦＯ１1／４２２に関連付けられており、ＦＯ１０／４２０とＦＯ１1／４２２はページの上部に位置するためである。ＦＯ１２／４２４はＦＯ１３／４２６よりもページの下部に位置する。一方、ＦＯ１２／４２４からの印はＦＯ１３／４２６からの印よりもページの上部を指し示す。このような場合には、ＭＯ１２／４５４をＭＯ１３／４５６よりも前に処理すると定める。最初にフレームＭＯ１２−１／４９０が処理される。ここで、フレームＭＯ１２−１／４９０内の粗画素群の粗画素は、何れも占有状態に設定されていない（すなわち、何れのＦＯのフットプリント及び／又は何れのＭＯのフレームとも重なっていない）。本例においては、図３Ｈに示される他のフレーム（フレームＭＯ１２−２／４９１、フレームＭＯ１２−３／４９２、フレームＭＯ１２−４／４９３）は何れも処理されないが、説明のために示している。図３Ｈに示される他のフレーム（フレームＭＯ１２−２／４９１、フレームＭＯ１２−３／４９２、フレームＭＯ１２−４／４９３）の何れかが処理される場合、当該フレームの粗画素群のうち少なくとも一の粗画素が占有状態に設定される。図３ＩはＭＯ１２／４５４の処理結果を示す。図３Ｇは、続くＭＯ１３／４５６の処理結果も示す。
【００６４】
図３Ｊは、本発明の実施形態を用いてＦＯ及びＭＯを配列した後にレンダリングした図を示す。
【００６５】
図４は、一以上の実施形態に係るシステム（例えば、図１を参照して説明した、クライアントコンピューター、オブジェクトレイアウトデバイスなど）が実装されたコンピューターシステム５００を示す。図５のコンピューターシステム５００は、用いられているプラットフォームに係らず、実質的に、あらゆるタイプのコンピューターである。例えば、図５に示されるように、コンピューターシステム５００は、集積回路、中央処理装置（ＣＰＵ）又はその他のハードウェアプロセッサーなどの一以上のプロセッサー５０２と、関連するメモリー５０４（例えば、ランダムアクセスメモリー（ＲＡＭ）、キャッシュメモリー、フラッシュメモリーなど）と、記憶装置５０６（例えば、ハードディスク、コンパクトディスクドライブやデジタルビデオディスク（ＤＶＤ）ドライブなどの光学ドライブ、フラッシュメモリースティックなど）と、その他多くの構成要素を含み、今日のコンピューター（図示なし）の有する一般的な機能を備える。コンピューターシステム５００は、キーボード５０８、マウス５１０、マイクロフォン（図示なし）などの入力手段も含んでもよい。また、コンピューターシステム５００は、グラフィックディスプレイ５１２（例えば、液晶ディスプレイ（ＬＣＤ）、発光ダイオード（ＬＥＤ）ディスプレイ、プラズマディスプレイ、ブラウン管（ＣＲＴ）モニター）などの出力手段も含んでもよい。コンピューターシステム５００は、ネットワークインターフェース接続（図示なし）を介して、ネットワーク５１４（例えば、ローカルエリアネットワーク（ＬＡＮ）、インターネットなどの広域ネットワーク（ＷＡＮ）、その他同様のタイプのネットワーク）に接続してもよい。多くの異なるタイプのコンピューターシステムが存在しており、前述の入力手段及び出力手段は、周知の又は今後開発される他の形態を取ってもよい。概括して言えば、コンピューターシステム５００は、少なくとも、本発明の実施形態を実施するために必要な、必要最低限の処理と、入力手段及び／又は出力手段を備える。
【００６６】
また、前述したコンピューターシステム５００の一以上の構成要素は、遠隔に位置し、ネットワークを介して、その他の構成要素と接続してもよい。また、本発明の複数の実施形態は、複数のノードを有する分散システムに実装されてもよく、本発明の各部（例えば、信頼予測エンジン、ソーシャルソース評価モジュール、ソーシャルスコア計算器）は、分散システム内の異なるノードに位置してもよい。本発明の一以上の実施形態において、ノードはコンピューターシステムに対応する。あるいは、ノードは関連する物理メモリーを有するプロセッサーに対応する。または、ノードは共有メモリー及び／又は共有資源を有するプロセッサーに対応する。また、本発明の実施形態を実行するためのソフトウェア指示を、非一時的コンピューター読取可能記憶媒体に記憶させてもよい。非一時的コンピューター読取可能記憶媒体としては、コンパクトディスク（ＣＤ）、ディスケット、テープ、その他の物理的コンピューター読取可能記憶装置がある。
【００６７】
本発明の一以上の実施形態は、１ページ上に一以上のオブジェクトを配列する。具体的には、本発明の実施形態は、オブジェクト同士が重なり合わないように、自動的に、オブジェクトを１ページ上に配列する。また、オブジェクトは、固定オブジェクト又は可動オブジェクトに分類される。固定オブジェクトは、ページ上で（可能ならば）固定された状態を維持する。固定オブジェクトに関連付けられた可動オブジェクトは、固定オブジェクトとの関連性を維持したまま、重なり合い及び／又は群がりを回避するように移動させることができる。
【００６８】
本発明の実施形態は、１ページ上のオブジェクトの重なり合い及び／又は群がりを回避するために、手動で当該ページ上のオブジェクトを移動させる必要がなく、ユーザーの時間を短縮できる。また、本発明の実施形態は、コンピューター処理時間を短縮することもできる。また、（例えば、個々の画素ではなく）ＣＰＡを用いることにより、各オブジェクトを処理し１ページ上に配列させるために使用するメモリー量が低減する。本発明の実施形態は、一の固定オブジェクトに関連付けられた複数の可動オブジェクトを処理することにより、コンピューターリソースを節約することもできる。例えば、オブジェクト又はオブジェクトのフレームの位置を、本発明の実施形態を用いて修正する必要がある場合、影響を受けるのは、ページ上に既に配置されている全てのオブジェクトではなく、可動オブジェクトが関連付けられている固定オブジェクトのみである。すなわち、本発明の実施形態は、一のオブジェクトを移動及び／又は修正する必要がある場合に、既に配置されている全てのオブジェクトに関する値を再度求める必要はない。
【００６９】
限られた数の実施形態を用いて本発明を説明したが、本開示の恩恵に浴する当業者であれば、ここに開示された本発明の範囲から逸脱することなく、他の実施形態を考案できることを理解するであろう。したがって、本発明の範囲は、添付の特許請求の範囲によってのみ制限されるべきである。
【特許請求の範囲】
【請求項１】
図をレンダリングする方法であって、
前記図内に各々フットプリントを有する複数の固定オブジェクトを特定する工程と、
前記図内に各々位置を有し、前記フットプリントと関連付けられた複数の可動オブジェクトを特定する工程と、
コンピュータープロセッサーを用いて、前記図のページスペースを表す粗画素の二次元配列を有する粗画素配列内で、前記フットプリントに対応する粗画素を特定する工程と、
前記コンピュータープロセッサーを用いて、前記フットプリントに対応する前記粗画素を占有状態に設定する工程と、
前記コンピュータープロセッサーを用いて、前記複数の可動オブジェクトのうち第１の位置を有する可動オブジェクトを選択する工程と、
前記コンピュータープロセッサーを用いて、前記第１の位置に基づいて、前記可動オブジェクトの第１のフレームに対応する前記粗画素配列内の第１の粗画素群を特定する工程と、
前記コンピュータープロセッサーを用いて、前記第１の粗画素群のうち少なくとも一の粗画素が前記占有状態であると判断する工程と、
前記コンピュータープロセッサーを用いて、前記第１の粗画素群のうち少なくとも一の粗画素が前記占有状態であると判断された場合に前記可動オブジェクトの第２の位置を生成する工程と、
前記コンピュータープロセッサーを用いて、前記第２の位置に基づいて、前記可動オブジェクトの第２のフレームに対応する前記粗画素配列内の第２の粗画素群を特定する工程と、
前記可動オブジェクトの前記第２の粗画素群を前記占有状態に設定する工程と、
ページ上の前記第２の位置に前記可動オブジェクトを配置して、前記図をレンダリングする工程と、
を備える方法。
【請求項２】
前記可動オブジェクトは、フォントサイズを有するテキストを備えるラベルであり、フットプリントを有し、
前記可動オブジェクトは、前記複数の固定オブジェクトのうちの第１の固定オブジェクトと関連付けられていることを特徴とする請求項１に記載の方法。
【請求項３】
前記第１の固定オブジェクトはクリップアートであることを特徴とする請求項２に記載の方法。
【請求項４】
第１の係数で前記可動オブジェクトのフットプリントを拡大／縮小して前記第１のフレームを算出する工程と、
を更に備えることを特徴とする請求項２に記載の方法。
【請求項５】
前記第１の係数は第２の係数よりも大きく、当該第２の係数で前記可動オブジェクトのフットプリントを拡大／縮小して第３のフレームを算出する工程と、
前記可動オブジェクトを選択後、前記第１の位置に基づいて、前記可動オブジェクトの前記第３のフレームに対応する前記粗画素配列内の第３の粗画素群を特定する工程と、
前記第３の粗画素群のうち少なくとも一の粗画素が前記占有状態に設定されていると判断する工程と、
を更に備える請求項４に記載の方法。
【請求項６】
前記可動オブジェクトの前記第１の位置と前記第２の位置は、前記複数の固定オブジェクトのうちの第１の固定オブジェクトに隣接していることを特徴とする請求項１に記載の方法。
【請求項７】
前記複数の固定オブジェクトのうち第３の位置を有する第２の固定オブジェクトを選択する工程と、
前記第３の位置に基づいて、前記第２の固定オブジェクトのフレームに対応する前記粗画素配列内の第３の粗画素群を特定する工程と、
前記第３の粗画素群のうち少なくとも一の粗画素が前記占有状態に設定されていると判断する工程と、
前記第４の粗画素群のうち少なくとも一の粗画素が前記占有状態に設定されていると判断された場合に前記第２の固定オブジェクトの第４の位置を生成する工程と、
前記第４の位置に基づいて、前記第２の固定オブジェクトの前記フレームに対応する前記粗画素配列内の第５の粗画素群を特定する工程と、
前記可動オブジェクトの前記第５の粗画素群を前記占有状態に設定する工程と、
を更に備え、
前記第２の固定オブジェクトは、固定オブジェクト階層に基づいて、前記第１の固定オブジェクトの後に選択されることを特徴とする請求項１に記載の方法。
【請求項８】
前記ページは前記第２の固定オブジェクトを前記第３の位置に結び付ける印を備えることを特徴とする請求項７に記載の方法。
【請求項９】
図をレンダリングするシステムであって、
ハードウェアプロセッサーと、
前記図のページスペースを表す粗画素の二次元配列を有する粗画素配列と、
可動オブジェクトの第１のフレームと第２のフレームを生成するように構成されたフレームモジュールと、
前記ハードウェアプロセッサー上で実行されるレイアウトエンジンと、
を備え、
前記レイアウトエンジンは、
前記図内に各々フットプリントを有する複数の固定オブジェクトを特定し、
前記フットプリントに対応する前記粗画素配列内の粗画素を占有状態に設定し、
前記可動オブジェクトの第１の位置に基づいて、前記第１のフレームに対応する前記粗画素配列内の第１の粗画素群を特定し、
前記第１の粗画素群のうち少なくとも一の粗画素が前記占有状態であると判断し、
前記可動オブジェクトと関連付けられた第２の位置に基づいて、前記可動オブジェクトの前記第２のフレームに対応する前記粗画素配列内の第２の粗画素群を特定し、
ページ上の前記第２の位置に前記可動オブジェクトを配置して、前記図をレンダリングするように構成されていることを特徴とするシステム。
【請求項１０】
前記レイアウトエンジンは、更に、
前記複数の固定オブジェクトのうち第３の位置を有する固定オブジェクトを選択し、
前記第３の位置に基づいて、前記固定オブジェクトのフレームに対応する前記粗画素配列内の第３の粗画素群を特定し、
前記第３の粗画素群のうち少なくとも一の粗画素が前記占有状態に設定されていると判断し、
前記第３の粗画素群のうち少なくとも一の粗画素が前記占有状態に設定されていると判断された場合に前記固定オブジェクトの第４の位置を生成し、
前記第４の位置に基づいて、前記固定オブジェクトの前記フレームに対応する前記粗画素配列内の第４の粗画素群を特定し、
前記第４の粗画素群を前記占有状態に設定するように構成されていることを特徴とする請求項９に記載のシステム。
【請求項１１】
前記固定オブジェクトはクリップアートであることを特徴とする請求項１０に記載のシステム。
【請求項１２】
前記固定オブジェクトは散布図におけるマーカーであることを特徴とする請求項１０に記載のシステム。
【請求項１３】
前記可動オブジェクトは、フォントサイズを有する文字を備えるテキストであり、プリントを有し、
前記可動オブジェクトは、前記複数の固定オブジェクトのうちの第１の固定オブジェクトと関連付けられていることを特徴とする請求項９に記載のシステム。
【請求項１４】
固定オブジェクト階層を記憶する固定オブジェクトリストと、
可動オブジェクト階層を記憶する可動オブジェクトリストと、
を更に備える請求項９に記載のシステム。
【請求項１５】
図をレンダリングするための指示を記憶する非一時的コンピューター読取可能記憶媒体であって、該指示は
前記図内に各々フットプリントを有する複数の固定オブジェクトを特定するための指示と、
前記図内に位置を有し、前記フットプリントと関連付けられた複数の可動オブジェクトを特定するための指示と、
前記図のページスペースを表す粗画素の二次元配列を有する粗画素配列内で、前記フットプリントに対応する粗画素を特定するための指示と、
前記フットプリントに対応する前記粗画素を占有状態に設定するための指示と、
前記複数の可動オブジェクトのうち第１の位置を有する可動オブジェクトを選択するための指示と、
前記第１の位置に基づいて、前記可動オブジェクトの第１のフレームに対応する前記粗画素配列内の第１の粗画素群を特定するための指示と、
前記第１の粗画素群のうち少なくとも一の粗画素が前記占有状態であると判断するための指示と、
前記第１の粗画素群のうち少なくとも一の粗画素が前記占有状態であると判断された場合に前記可動オブジェクトの第２の位置を生成するための指示と、
前記第２の位置に基づいて、前記可動オブジェクトの第２のフレームに対応する前記粗画素配列内で第２の粗画素群を特定するための指示と、
前記可動オブジェクトの前記第２の粗画素群を前記占有状態に設定するための指示と、
ページ上の前記第２の位置に前記可動オブジェクトを配置して、前記図をレンダリングするための指示と、
を備える非一時的コンピューター読取可能記憶媒体。
【請求項１６】
前記可動オブジェクトは、フォントサイズを有する文字を備えるラベルであり、フットプリントを有し、
前記可動オブジェクトは、前記複数の固定オブジェクトのうちの第１の固定オブジェクトと関連付けられていることを特徴とする請求項１６に記載の非一時的コンピューター読取可能記憶媒体。
【請求項１７】
第１の係数で前記可動オブジェクトのフットプリントを拡大／縮小して前記第１のフレームを算出するための指示と、
を更に備える請求項１６に記載の非一時的コンピューター読取可能記憶媒体。
【請求項１８】
前記第１の係数は第２の係数よりも大きく、当該第２の係数で前記可動オブジェクトのフットプリントを拡大／縮小して第３のフレームを算出するための指示と、
前記可動オブジェクトを選択後、前記第１の位置に基づいて、前記可動オブジェクトの前記第３のフレームに対応する前記粗画素配列内の第３の粗画素群を特定するための指示と、
前記第３の粗画素群のうち少なくとも一の粗画素が前記占有状態に設定されていると判断するための指示と、
を更に備える請求項１７に記載の非一時的コンピューター読取可能記憶媒体。
【請求項１９】
前記複数の固定オブジェクトのうち第３の位置を有する第２の固定オブジェクトを選択するための指示と、
前記第３の位置に基づいて、前記第２の固定オブジェクトのフレームに対応する前記粗画素配列内の第３の粗画素群を特定するための指示と、
前記第３の粗画素群のうち少なくとも一の粗画素が前記占有状態に設定されていると判断するための指示と、
前記第４の粗画素群のうち少なくとも一の粗画素が前記占有状態に設定されていると判断された場合に前記第２の固定オブジェクトの第４の位置を生成するための指示と、
前記第４の位置に基づいて、前記第２の固定オブジェクトの前記フレームに対応する前記粗画素配列内の第５の粗画素群を特定するための指示と、
前記可動オブジェクトの前記第５の粗画素群を前記占有状態に設定するための指示と、
を更に備え、
前記第２の固定オブジェクトは、固定オブジェクト階層に基づいて、前記第１の固定オブジェクトの後に選択されることを特徴とする請求項１５に記載の非一時的コンピューター読取可能記憶媒体。
【請求項２０】
前記ページは前記第２の固定オブジェクトを前記第３の位置に結び付ける印を備えることを特徴とする請求項１９に記載の非一時的コンピューター読取可能記憶媒体。
【請求項１】
図をレンダリングする方法であって、
前記図内に各々フットプリントを有する複数の固定オブジェクトを特定する工程と、
前記図内に各々位置を有し、前記フットプリントと関連付けられた複数の可動オブジェクトを特定する工程と、
コンピュータープロセッサーを用いて、前記図のページスペースを表す粗画素の二次元配列を有する粗画素配列内で、前記フットプリントに対応する粗画素を特定する工程と、
前記コンピュータープロセッサーを用いて、前記フットプリントに対応する前記粗画素を占有状態に設定する工程と、
前記コンピュータープロセッサーを用いて、前記複数の可動オブジェクトのうち第１の位置を有する可動オブジェクトを選択する工程と、
前記コンピュータープロセッサーを用いて、前記第１の位置に基づいて、前記可動オブジェクトの第１のフレームに対応する前記粗画素配列内の第１の粗画素群を特定する工程と、
前記コンピュータープロセッサーを用いて、前記第１の粗画素群のうち少なくとも一の粗画素が前記占有状態であると判断する工程と、
前記コンピュータープロセッサーを用いて、前記第１の粗画素群のうち少なくとも一の粗画素が前記占有状態であると判断された場合に前記可動オブジェクトの第２の位置を生成する工程と、
前記コンピュータープロセッサーを用いて、前記第２の位置に基づいて、前記可動オブジェクトの第２のフレームに対応する前記粗画素配列内の第２の粗画素群を特定する工程と、
前記可動オブジェクトの前記第２の粗画素群を前記占有状態に設定する工程と、
ページ上の前記第２の位置に前記可動オブジェクトを配置して、前記図をレンダリングする工程と、
を備える方法。
【請求項２】
前記可動オブジェクトは、フォントサイズを有するテキストを備えるラベルであり、フットプリントを有し、
前記可動オブジェクトは、前記複数の固定オブジェクトのうちの第１の固定オブジェクトと関連付けられていることを特徴とする請求項１に記載の方法。
【請求項３】
前記第１の固定オブジェクトはクリップアートであることを特徴とする請求項２に記載の方法。
【請求項４】
第１の係数で前記可動オブジェクトのフットプリントを拡大／縮小して前記第１のフレームを算出する工程と、
を更に備えることを特徴とする請求項２に記載の方法。
【請求項５】
前記第１の係数は第２の係数よりも大きく、当該第２の係数で前記可動オブジェクトのフットプリントを拡大／縮小して第３のフレームを算出する工程と、
前記可動オブジェクトを選択後、前記第１の位置に基づいて、前記可動オブジェクトの前記第３のフレームに対応する前記粗画素配列内の第３の粗画素群を特定する工程と、
前記第３の粗画素群のうち少なくとも一の粗画素が前記占有状態に設定されていると判断する工程と、
を更に備える請求項４に記載の方法。
【請求項６】
前記可動オブジェクトの前記第１の位置と前記第２の位置は、前記複数の固定オブジェクトのうちの第１の固定オブジェクトに隣接していることを特徴とする請求項１に記載の方法。
【請求項７】
前記複数の固定オブジェクトのうち第３の位置を有する第２の固定オブジェクトを選択する工程と、
前記第３の位置に基づいて、前記第２の固定オブジェクトのフレームに対応する前記粗画素配列内の第３の粗画素群を特定する工程と、
前記第３の粗画素群のうち少なくとも一の粗画素が前記占有状態に設定されていると判断する工程と、
前記第４の粗画素群のうち少なくとも一の粗画素が前記占有状態に設定されていると判断された場合に前記第２の固定オブジェクトの第４の位置を生成する工程と、
前記第４の位置に基づいて、前記第２の固定オブジェクトの前記フレームに対応する前記粗画素配列内の第５の粗画素群を特定する工程と、
前記可動オブジェクトの前記第５の粗画素群を前記占有状態に設定する工程と、
を更に備え、
前記第２の固定オブジェクトは、固定オブジェクト階層に基づいて、前記第１の固定オブジェクトの後に選択されることを特徴とする請求項１に記載の方法。
【請求項８】
前記ページは前記第２の固定オブジェクトを前記第３の位置に結び付ける印を備えることを特徴とする請求項７に記載の方法。
【請求項９】
図をレンダリングするシステムであって、
ハードウェアプロセッサーと、
前記図のページスペースを表す粗画素の二次元配列を有する粗画素配列と、
可動オブジェクトの第１のフレームと第２のフレームを生成するように構成されたフレームモジュールと、
前記ハードウェアプロセッサー上で実行されるレイアウトエンジンと、
を備え、
前記レイアウトエンジンは、
前記図内に各々フットプリントを有する複数の固定オブジェクトを特定し、
前記フットプリントに対応する前記粗画素配列内の粗画素を占有状態に設定し、
前記可動オブジェクトの第１の位置に基づいて、前記第１のフレームに対応する前記粗画素配列内の第１の粗画素群を特定し、
前記第１の粗画素群のうち少なくとも一の粗画素が前記占有状態であると判断し、
前記可動オブジェクトと関連付けられた第２の位置に基づいて、前記可動オブジェクトの前記第２のフレームに対応する前記粗画素配列内の第２の粗画素群を特定し、
ページ上の前記第２の位置に前記可動オブジェクトを配置して、前記図をレンダリングするように構成されていることを特徴とするシステム。
【請求項１０】
前記レイアウトエンジンは、更に、
前記複数の固定オブジェクトのうち第３の位置を有する固定オブジェクトを選択し、
前記第３の位置に基づいて、前記固定オブジェクトのフレームに対応する前記粗画素配列内の第３の粗画素群を特定し、
前記第３の粗画素群のうち少なくとも一の粗画素が前記占有状態に設定されていると判断し、
前記第３の粗画素群のうち少なくとも一の粗画素が前記占有状態に設定されていると判断された場合に前記固定オブジェクトの第４の位置を生成し、
前記第４の位置に基づいて、前記固定オブジェクトの前記フレームに対応する前記粗画素配列内の第４の粗画素群を特定し、
前記第４の粗画素群を前記占有状態に設定するように構成されていることを特徴とする請求項９に記載のシステム。
【請求項１１】
前記固定オブジェクトはクリップアートであることを特徴とする請求項１０に記載のシステム。
【請求項１２】
前記固定オブジェクトは散布図におけるマーカーであることを特徴とする請求項１０に記載のシステム。
【請求項１３】
前記可動オブジェクトは、フォントサイズを有する文字を備えるテキストであり、プリントを有し、
前記可動オブジェクトは、前記複数の固定オブジェクトのうちの第１の固定オブジェクトと関連付けられていることを特徴とする請求項９に記載のシステム。
【請求項１４】
固定オブジェクト階層を記憶する固定オブジェクトリストと、
可動オブジェクト階層を記憶する可動オブジェクトリストと、
を更に備える請求項９に記載のシステム。
【請求項１５】
図をレンダリングするための指示を記憶する非一時的コンピューター読取可能記憶媒体であって、該指示は
前記図内に各々フットプリントを有する複数の固定オブジェクトを特定するための指示と、
前記図内に位置を有し、前記フットプリントと関連付けられた複数の可動オブジェクトを特定するための指示と、
前記図のページスペースを表す粗画素の二次元配列を有する粗画素配列内で、前記フットプリントに対応する粗画素を特定するための指示と、
前記フットプリントに対応する前記粗画素を占有状態に設定するための指示と、
前記複数の可動オブジェクトのうち第１の位置を有する可動オブジェクトを選択するための指示と、
前記第１の位置に基づいて、前記可動オブジェクトの第１のフレームに対応する前記粗画素配列内の第１の粗画素群を特定するための指示と、
前記第１の粗画素群のうち少なくとも一の粗画素が前記占有状態であると判断するための指示と、
前記第１の粗画素群のうち少なくとも一の粗画素が前記占有状態であると判断された場合に前記可動オブジェクトの第２の位置を生成するための指示と、
前記第２の位置に基づいて、前記可動オブジェクトの第２のフレームに対応する前記粗画素配列内で第２の粗画素群を特定するための指示と、
前記可動オブジェクトの前記第２の粗画素群を前記占有状態に設定するための指示と、
ページ上の前記第２の位置に前記可動オブジェクトを配置して、前記図をレンダリングするための指示と、
を備える非一時的コンピューター読取可能記憶媒体。
【請求項１６】
前記可動オブジェクトは、フォントサイズを有する文字を備えるラベルであり、フットプリントを有し、
前記可動オブジェクトは、前記複数の固定オブジェクトのうちの第１の固定オブジェクトと関連付けられていることを特徴とする請求項１６に記載の非一時的コンピューター読取可能記憶媒体。
【請求項１７】
第１の係数で前記可動オブジェクトのフットプリントを拡大／縮小して前記第１のフレームを算出するための指示と、
を更に備える請求項１６に記載の非一時的コンピューター読取可能記憶媒体。
【請求項１８】
前記第１の係数は第２の係数よりも大きく、当該第２の係数で前記可動オブジェクトのフットプリントを拡大／縮小して第３のフレームを算出するための指示と、
前記可動オブジェクトを選択後、前記第１の位置に基づいて、前記可動オブジェクトの前記第３のフレームに対応する前記粗画素配列内の第３の粗画素群を特定するための指示と、
前記第３の粗画素群のうち少なくとも一の粗画素が前記占有状態に設定されていると判断するための指示と、
を更に備える請求項１７に記載の非一時的コンピューター読取可能記憶媒体。
【請求項１９】
前記複数の固定オブジェクトのうち第３の位置を有する第２の固定オブジェクトを選択するための指示と、
前記第３の位置に基づいて、前記第２の固定オブジェクトのフレームに対応する前記粗画素配列内の第３の粗画素群を特定するための指示と、
前記第３の粗画素群のうち少なくとも一の粗画素が前記占有状態に設定されていると判断するための指示と、
前記第４の粗画素群のうち少なくとも一の粗画素が前記占有状態に設定されていると判断された場合に前記第２の固定オブジェクトの第４の位置を生成するための指示と、
前記第４の位置に基づいて、前記第２の固定オブジェクトの前記フレームに対応する前記粗画素配列内の第５の粗画素群を特定するための指示と、
前記可動オブジェクトの前記第５の粗画素群を前記占有状態に設定するための指示と、
を更に備え、
前記第２の固定オブジェクトは、固定オブジェクト階層に基づいて、前記第１の固定オブジェクトの後に選択されることを特徴とする請求項１５に記載の非一時的コンピューター読取可能記憶媒体。
【請求項２０】
前記ページは前記第２の固定オブジェクトを前記第３の位置に結び付ける印を備えることを特徴とする請求項１９に記載の非一時的コンピューター読取可能記憶媒体。
【図１Ａ】
【図１Ｂ】
【図１Ｃ】
【図１Ｄ】
【図２Ａ】
【図２Ｂ】
【図２Ｃ】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図３Ｄ】
【図３Ｅ】
【図３Ｆ】
【図３Ｇ】
【図３Ｈ】
【図３Ｉ】
【図３Ｊ】
【図４】
【図１Ｂ】
【図１Ｃ】
【図１Ｄ】
【図２Ａ】
【図２Ｂ】
【図２Ｃ】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図３Ｄ】
【図３Ｅ】
【図３Ｆ】
【図３Ｇ】
【図３Ｈ】
【図３Ｉ】
【図３Ｊ】
【図４】
【公開番号】特開２０１２−１９０４５６（Ｐ２０１２−１９０４５６Ａ）
【公開日】平成２４年１０月４日（２０１２．１０．４）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１２−４８６７５（Ｐ２０１２−４８６７５）
【出願日】平成２４年３月６日（２０１２．３．６）
【出願人】（５０７０３１９１８）コニカ ミノルタ ラボラトリー ユー．エス．エー．，インコーポレイテッド (157)
【Ｆターム（参考）】
【公開日】平成２４年１０月４日（２０１２．１０．４）
【国際特許分類】
【出願番号】特願２０１２−４８６７５（Ｐ２０１２−４８６７５）
【出願日】平成２４年３月６日（２０１２．３．６）
【出願人】（５０７０３１９１８）コニカ ミノルタ ラボラトリー ユー．エス．エー．，インコーポレイテッド (157)
【Ｆターム（参考）】
[ Back to top ]