(57)【特許請求の範囲】
【請求項１】
複数の図形要素を配置する図形要素配置装置であって、
前記図形要素には、移動可能な図形要素と、移動不能な図形要素とが含まれ、
所定の条件の下で、過去に配置された他の図形要素と干渉せずに、対象となる図形要素の配置可能な領域を探索し、前記対象となる図形要素が、他の図形要素と干渉せずに配置できた場合に、その配置位置を決定する配置領域探索手段と、
前記対象となる図形要素が、過去に配置された他の図形要素と干渉せずに配置できない場合には、当該過去に配置された図形要素が移動可能であるか移動不能であるかを判断し、当該過去に配置された他の図形要素が移動可能な図形要素であり、当該過去に配置された図形要素の再配置を試行し、再配置できなかった場合にその旨を報知し、また、前記判断において当該過去に配置された他の図形要素が移動不能な図形要素である場合にその旨を報知する再配置試行手段と、
を含むことを特徴とする図形要素配置装置。
【請求項２】
請求項１記載の図形要素配置装置であって、
前記配置領域探索手段は、
指定された座標の点から予め定められた角度方向に仮想的に描画された線分に配置領域が重なり合わないよう、対象となる図形要素の配置領域を探索し、
前記探索によって見出された配置領域が他の図形要素と干渉するか否かを判断し、
前記探索によって見出された配置領域が他の図形要素と干渉しない場合は、当該見出した配置領域に対象となる図形要素を配置し、
前記判断により干渉すると判断される場合に、前記見出された配置領域の近傍に他の図形要素に干渉せずに前記対象となる図形要素を配置可能な配置領域があれば、当該配置領域に対象となる図形要素を配置することを特徴とする図形要素配置装置。
【請求項３】
請求項２記載の図形要素配置装置であって、
前記再配置試行手段は、
前記判断により干渉すると判断される場合に、前記見出された配置領域の近傍に他の図形要素に干渉せずに前記対象となる図形要素を配置可能な配置領域がない場合であって、前記他の図形要素が移動可能な図形要素である場合に、前記過去に配置された他の図形要素の再配置を試行することを特徴とする図形要素配置装置。
【請求項４】
コンピュータに、複数の図形要素を配置させるプログラムであって、
前記図形要素には、移動可能な図形要素と、移動不能な図形要素とが含まれ、
所定の条件の下で、過去に配置された他の図形要素と干渉せずに、対象となる図形要素の配置可能な領域を探索し、前記対象となる図形要素が、他の図形要素と干渉せずに配置できた場合に、その配置位置を決定する配置領域探索手段と、
前記対象となる図形要素が、過去に配置された他の図形要素と干渉せずに配置できない場合には、当該過去に配置された図形要素が移動可能であるか移動不能であるかを判断し、当該過去に配置された他の図形要素が移動可能な図形要素であり、当該過去に配置された図形要素の再配置を試行し、再配置できなかった場合にその旨を報知し、また、前記判断において当該過去に配置された他の図形要素が移動不能な図形要素である場合にその旨を報知する再配置試行手段と、
として、コンピュータを機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の図形要素を、互いに重ならないように配置する図形要素配置装置及びプログラムに関する。
【背景技術】
【０００２】
近年では、種々の画像がコンピュータを用いて生成されている。例えば地図などの画像もその一つである。この地図などの画像では、道路を表す線分や、建造物の形状を表す線分、地名や建物名その他の文字など、多数の図形要素が互いに重なり合わないよう配置される。
【０００３】
従来、こうした図形要素の配置には主として手作業が要求されていた。また、道路や建造物などを表す線分を描き入れた後、例えば道路上の交差点を表す文字列（長さＬ）を配置するために、交差点の中心点を基準として、その左右方向に所定長の仮想線分を伸ばし、当該仮想線分上で、他の線分に交わらない長さＬの部分があれば、当該部分を文字列の配置位置候補とする技術がある（特許文献１）。
【特許文献１】特開平８−１６７０３９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記従来の図形要素の配置方法では、配置される文字列が多くなってくると、既に配置された文字列のために、新たな文字列の配置位置が制限され、文字列の配置位置の探索が困難になることがあった。
【０００５】
本発明は上記実情に鑑みて為されたもので、より多くの図形要素を互いに重ならないよう配置できる図形要素配置装置を提供することを、その目的の一つとする。
【課題を解決するための手段】
【０００６】
上記従来例の問題点を解決するための本発明は、複数の図形要素を配置する図形要素配置装置であって、所定の条件の下で、過去に配置された他の図形要素と干渉せずに、対象となる図形要素の配置領域を探索し、前記対象となる図形要素が、他の図形要素と干渉せずに配置できた場合に、その配置位置を決定する配置領域探索手段と、前記対象となる図形要素が、他の図形要素と干渉せずに配置できない場合に、前記過去に配置された他の図形要素の再配置を試行する再配置試行手段と、を含むこととしたものである。
【０００７】
ここで、前記配置領域探索手段は、所定の条件の下で、対象となる図形要素の配置領域を探索し、前記探索によって見出された配置領域が他の図形要素と干渉するか否かを判断し、前記探索によって見出された配置領域が他の図形要素と干渉しない場合は、当該見出した配置領域に対象となる図形要素を配置し、前記判断により干渉すると判断される場合に、前記見出された配置領域の近傍に他の図形要素に干渉せずに前記対象となる図形要素を配置可能な配置領域があれば、当該配置領域に対象となる図形要素を配置することとしてもよい。
【０００８】
さらに、前記再配置試行手段は、前記判断により干渉すると判断される場合に、前記見出された配置領域の近傍に他の図形要素に干渉せずに前記対象となる図形要素を配置可能な配置領域がない場合に、前記過去に配置された他の図形要素の再配置を試行することとしてもよい。
【０００９】
さらに前記所定の条件は、指定された座標の点から予め定められた角度方向に仮想的に描画された線分に配置領域が重なり合う条件であってもよい。
【００１０】
また、本発明の一態様は、コンピュータに、複数の図形要素を配置させるプログラムであって、所定の条件の下で、過去に配置された他の図形要素と干渉せずに、対象となる図形要素の配置領域を探索し、前記対象となる図形要素が、他の図形要素と干渉せずに配置できた場合に、その配置位置を決定する配置領域探索手段と、前記対象となる図形要素が、他の図形要素と干渉せずに配置できない場合に、前記過去に配置された他の図形要素の再配置を試行する再配置試行手段と、として、コンピュータを機能させることとしたものである。
【発明の効果】
【００１１】
本発明によると、図形要素を互いに重ならないよう配置できる。
【発明を実施するための最良の形態】
【００１２】
本発明の実施の形態について図面を参照しながら説明する。本発明の実施の形態に係る図形要素配置装置は、図１に示すように、制御部１１と、記憶部１２と、操作部１３と、出力部１４とを含んで構成されている。
【００１３】
ここに制御部１１は、例えばＣＰＵなどのプログラム制御デバイスであり、記憶部１２に格納されたプログラムに従って処理を行う。本実施の形態では、この制御部１１は、地図などのように、複数の図形要素を、互いに重なり合わないように配置する処理を実行する。例えば制御部１１は、予め定めた条件の下で、過去に配置された他の図形要素と干渉せずに、対象となる図形要素の配置領域を探索する処理と、この対象となる図形要素が、他の図形要素と干渉せずに配置できない場合に、過去に配置された他の図形要素の再配置を試行する処理（再配置試行処理）とを実行する。この制御部１１の動作例については、後に詳しく述べる。
【００１４】
記憶部１２は、制御部１１が実行するプログラムを保持するコンピュータ可読な記録媒体として動作する。また、この記憶部１２は、制御部１１のワークメモリとしても動作している。操作部１３は、例えばマウスやキーボードなどであり、利用者の指示操作を受け入れて、当該指示操作の内容を制御部１１に出力する。
【００１５】
出力部１４は、例えば液晶ディスプレイなどの表示デバイスを含む。この出力部１４は、図形要素を配置した画像の少なくとも一部を表示出力する。また、この出力部１４は、図形要素を配置して得られた画像の情報を出力する。
【００１６】
ここで制御部１１によって実行される処理の詳しい内容について述べる。本実施の形態の制御部１１は、基本的には、図形要素である線分や文字列などを描画する処理を行う。この処理では、記憶部１２に、描画の対象となる図形要素を特定する情報が蓄積される。この情報は、出力部１４に対して情報が表示出力される際などに供される。
【００１７】
例えば、この記憶部１２には、各図形要素について、図形要素ごとに固有の識別子と、図形要素の種別と、図形要素を描画するのに必要となる座標情報と、色の情報などとが関連づけて記録されている。図形要素が線分である場合は、その描画に必要となる座標情報として、線分の端点を表す座標情報が記録される。また、図形要素が文字列である場合は、図２に例示するように、その描画に必要となる文字列を包含する図形要素（以下、代理図形と呼ぶ）の頂点の座標情報と、代理図形内部に描画されるべき文字列を表す情報などが記録される。
【００１８】
また制御部１１は、記憶部１２に、その後の移動を抑制する移動抑制リストを格納する。この移動抑制リストには、移動を抑制する対象となる図形要素の識別子が列挙して保持される。
【００１９】
さらに制御部１１は、図形要素である線分で囲まれた「面」、線分、及び図形要素を配置した画像上の一点を基準として、文字列を配置する処理を行う。以下、この処理について説明する。
【００２０】
すなわち、本実施の形態の制御部１１が実行するプログラムは、機能的には図３に示すように、補助線設定部２１と、空間探索部２２と、調整部２３と、配置位置決定部２４と、描画部２５と、再配置試行部２６とを含んで構成される。
【００２１】
補助線設定部２１は、配置の基準として、面や、線分、点などの指定と、描画するべき文字列の情報とを受け入れる。補助線設定部２１は、受け入れた文字列を包含する代理図形のサイズを算出する。一般に文字列は矩形状に配列されるので、ここでの代理図形は矩形状であるとすればよい。代理図形を矩形とする場合、そのサイズは幅Ｌ及び高さＨで規定できる。ここで幅は一行あたりの文字列の配置幅、高さは行方向の長さ（一行の文字列配列に垂直な方向の長さ）を表す。
【００２２】
補助線設定部２１は、面が指定された場合は、図４に例示するように、面内に仮想の平行線（補助線）を複数設定する。そして補助線設定部２１は、複数設定した補助線と、面を構成する線分（境界線）など、他の図形要素との交点を求め交点間の距離（交差区間長）を演算する。さらに補助線設定部２１は、交差区間長が最大となっている補助線（仮候補補助線）を特定する。
【００２３】
補助線設定部２１は、交差区間長が最大となる仮候補補助線について、当該交差区間長が、描画するべき文字列に対応する代理図形（以下、注目代理図形と呼ぶ）の幅Ｌを越えているか否かを調べる。このとき、交差区間長が文字列の注目代理図形の幅Ｌを越えていなければ、補助線設定部２１は配置不能と判断して処理を中断してもよい。
【００２４】
また、交差区間長が注目代理図形の幅Ｌを越えていれば、補助線設定部２１は当該仮候補補助線を候補補助線とする。補助線設定部２１は、その候補補助線と、交点間の位置（交差区間）とを特定する情報（線分の端点の座標情報と交差区間の端点の座標情報と、など）を空間探索部２２に出力する。
【００２５】
空間探索部２２は、注目代理図形を、その幅方向の辺が、候補補助線の交差区間に平行になるよう配し、当該配したときの注目代理図形の外周が、他の図形要素に重なり合っている（干渉している）か否かを調べる。なお、注目代理図形を配する場合に、候補補助線と注目代理図形とが交差しないよう配してもよいし、候補補助線と注目代理図形とを交差させるよう配してもよい。
【００２６】
ここで、候補補助線に沿って配した注目代理図形の外周が、他の図形要素に重なり合わない場合は、そのときの注目代理図形の配置位置を特定する情報（例えば代理図形が矩形であれば、対角線上の二点の座標情報）を配置位置決定部２４に出力する。
【００２７】
そして配置位置決定部２４は、固有の図形要素の識別子を発行して、この発行した識別子と、配置の対象となった文字列と、それに対応する代理図形の配置位置を特定する情報とを関連づけて、図５に示したように、記憶部１２に格納する。また、配置位置決定部２４は、配置した文字列に対応する図形要素の識別子を、移動抑制リストに追加して格納する。
【００２８】
一方、空間探索部２２の処理において、候補補助線に沿って配した注目代理図形の外周が、他の図形要素（環境線や他の代理図形など）に重なり合う場合は、空間探索部２２は、調整部２３に注目代理図形の位置を調整させる。ここで調整部２３は、注目代理図形を候補補助線に沿って平行移動し、他の図形要素に干渉せずに配置できる位置があるか否かを調べる（注目代理図形配置調整処理）。この処理は例えば次のようになる。一例として図６（ａ）に示すように、注目代理図形Ｂ１に干渉する他の図形要素Ｂ２があり、また注目代理図形に対して現在は干渉していないが、その近傍に配された環境線の図形要素Ｅがあるとする。このとき、調整部２３は、注目代理図形Ｂ１の候補補助線Ｘに平行な二辺（辺ＰＳ，ＱＲ）を延長し、現在干渉のない環境線の図形要素Ｅに交差する点をα，βとして、各辺に対応する延長線部分の長さ、Ｓαと、Ｒβとを求める。
【００２９】
なお、図６（ｂ）に示すように、注目代理図形Ｂ１が環境線Ｆに干渉している場合もある。このときには、注目代理図形Ｂ１に現在干渉のない環境線Ｅに、注目代理図形Ｂ１の候補補助線Ｘに平行な二辺（辺ＰＳ，ＱＲ）を延長した線分が交差する点をα，βとして、各辺に対応する延長線部分の長さ、Ｓαと、Ｒβとを求める。
【００３０】
さらに、図６（ｃ）に示すように、注目代理図形Ｂ１の候補補助線Ｘに平行な二辺（辺ＰＳ，ＱＲ）を延長した線分の少なくとも一方が環境線に交差しない場合もある。このときには延長線上にαまたはβを仮想的に、ＳαまたはＲβが予め定めた値となる位置に配置して、ＳαとＲβとを定める。図６（ｃ）では、辺ＰＳの延長線は点αで、現在干渉のない環境線Ｅに交わるが、辺ＱＲの延長線が環境線に交わらない例を示している。そこでこの例では、Ｒから予め定めた長さｌmaxの位置に点βを仮想的に設定している。
【００３１】
なお、環境線Ｅに延長線が交わる場合であっても、交差点αまでの距離Ｓα（またはＲβ）がこのｌmaxを越える場合は、点α（または点β）を仮想的に、Ｓα＝ｌmax（またはＲβ＝ｌmax）となる位置に設定してもよい。
【００３２】
また、調整部２３は、現在干渉している他の図形要素Ｂ２との干渉を解消するために移動するべき方向と距離とを演算する。図６の例では、辺ＰＳとその延長線が、他の図形要素Ｂ２との間で、点Ｌ及び点Ｍにて交差している。そこで、ＰからＳへの方向へ移動する場合、距離ＰＬだけ移動すれば、注目代理図形Ｂ１と図形要素Ｂ２との干渉が回避できる。また、ＳからＰへの方向へ移動する場合、距離ＳＭだけ移動すれば注目代理図形Ｂ１と図形要素Ｂ２との干渉が回避できる。
【００３３】
調整部２３は、ＰからＳの方向に延長された各辺からの延長線分がさらに他の図形要素と交差する点までの距離Ｓα，Ｒβを参照し、そのうち短いもの（図６ではＳα＜Ｒβのように図示しているので、この場合Ｓα）を取り出す。そして、当該取り出した値が、干渉を回避するために移動するべき距離よりも大きいか否かを調べる（図６の例では、Ｓα＞ＰＬか否かを調べる）。
【００３４】
ここで取り出した値が、干渉を回避するために移動するべき距離よりも大きいならば、調整部２３は、注目代理図形を、距離Ｄ（Ｓα＞Ｄ＞ＰＬ）だけ移動して、他の図形要素との干渉を回避し、回避後の注目代理図形の配置位置を特定する情報を配置位置決定部２４に出力して、注目代理図形配置調整処理を終了する。
【００３５】
一方で、上記取り出した値が、干渉を回避するために移動するべき距離以下の場合は、調整部２３はその旨を、空間探索部２２に出力する。そして空間探索部２２は、干渉が回避できないとして、現在の候補補助線を除く、他の補助線から改めて仮候補補助線を選択する。つまり、この場合は、交差区間長の長い順に候補補助線を選択しつつ、注目代理図形を配して、他の図形要素に重なり合わないかを調べる。なお、他の図形要素に干渉せずに注目代理図形を配置できる候補補助線が見出せない場合（当初設定したすべての補助線に沿って文字列等が配置できない場合）は、最初の候補補助線（最も長い交差区間長を有する候補補助線）に沿って注目代理図形を仮に配置し、再配置試行処理を開始する。すなわち空間探索部２２は、まず、干渉している他の図形要素が、移動可能なものであるか否かを判断する。ここで移動可能なものとは、文字列の代理図形などであり、図形要素ごとに指定されてもよいし、図形要素の種別ごとに判断されてもよい。
【００３６】
干渉している他の図形要素が移動可能なものである場合、空間探索部２２は、固有の図形要素の識別子を発行して、この発行した識別子と、配置の対象となった文字列と、対応する注目代理図形の配置位置を特定する情報とを関連づけて、記憶部１２に格納する（図５）。また、仮に配置した文字列に対応する図形要素の識別子を、移動抑制リストに追加して格納する。そして、配置の対象となった文字列の代理図形に重なり合う他の図形要素の識別子を、再配置試行部２６に出力する。
【００３７】
干渉している他の図形要素が、環境線など移動不能なものである場合、空間探索部２２は、エラーを報知するなどして、処理を中断する。
【００３８】
描画部２５は、配置位置決定部２４が記憶部１２に格納した情報を参照して、配置の対象となった文字列を、それぞれ対応する情報で特定される代理図形の配置位置（領域）内に描画する。この描画部２５による描画結果は、例えば出力部１４によるディスプレイ等への出力に供される。
【００３９】
再配置試行部２６は、空間探索部２２の処理により、文字列の配置位置が見出せない場合に、それまでに配置した文字列等、他の図形要素の配置位置を移動して、配置位置が得られるか否かを試行する。
【００４０】
すなわち本実施の形態では、一度配置位置が見出されると、その文字列などの図形要素は、移動抑制の対象として設定される。しかしながら、その後の図形要素（対象図形要素と呼ぶ）が配置できない場合は、過去に配置位置が決定され、移動抑制の対象となった図形要素であっても、再度、その配置位置を調整する処理が行われ、対象図形要素の配置が可能となるか否かが試行されるのである。
【００４１】
次に、この再配置試行部２６の具体的な処理例について説明する。再配置試行部２６は、再配置試行処理の対象となる図形要素（既配置の図形要素であって、環境線など移動不能なものを除く：以下、再配置対象図形要素と呼ぶ）の識別子の入力を受け入れる。そして入力を受け入れた識別子を、移動抑制リストから除去する。
【００４２】
再配置試行部２６は、図７に示すように、再配置対象図形要素を包含する代理図形を設定（例えば再配置対象図形要素に外接する外接矩形そのもの、または外接矩形を外側へ所定量だけ拡大して得る）し（Ｓ１）、代理図形の各辺をその両側へ所定量だけ延長する（Ｓ２）。また、各辺を延長して得た線分が他の図形要素に交差する場合は、その交差の点から外への延長部分を除去する（Ｓ３）。
【００４３】
次に再配置試行部２６は、各辺において、他の図形要素（例えば他の代理図形の線分）が交差する位置を点（以下、交差点という）として特定する（Ｓ４）。図７においては、再配置対象図形要素は、他の代理図形と、点Ａ，Ｂで交差することを示している。また、図８に例示するように、再配置対象図形要素内に、他の図形要素を構成する線分の端点（当該他の図形要素が多角形であれば、その頂点）が含まれている場合、処理Ｓ４では、当該頂点から、当該他の図形要素との交差がある辺へ下した垂線の足（図８のＣ，Ｄ）をも交差点として特定する。
【００４４】
他の図形要素との交差がある辺の両端の頂点から、各頂点より最も遠い位置にある交差点でも長さを求める（Ｓ５）。図７においては、頂点Ｐ，Ｑから交差点Ａまでの距離、ＰＡ及びＱＡと、頂点Ｑ，Ｒから交差点Ｂまでの距離、ＱＢ及びＲＢとを求める。また、図８においては、図８（ｂ）に示すように、ＰＣ，ＱＡ，ＱＢ，ＲＤをそれぞれ求めることになる。
【００４５】
この処理Ｓ５で求めた長さが、移動量の候補となる。すなわち、再配置試行部２６は、図７を例として説明すると、
【００４６】
（１）辺ＰＱに沿って、ＰからＡの方向へ長さＰＡだけ移動した場合、
（２）辺ＰＱに沿って、ＱからＡの方向へ長さＱＡだけ移動した場合、
（３）辺ＱＲに沿って、ＱからＢの方向へ長さＱＢだけ移動した場合、
（４）辺ＱＲに沿って、ＲからＢの方向へ長さＲＢだけ移動した場合
【００４７】
のそれぞれについて、再配置対象図形要素を移動したとき、他の図形要素との重なり合いが回避できるか否かを調べる。ここでは、（２）辺ＰＱに沿って、ＱからＡの方向へ長さＱＡだけ移動した場合、または（３）辺ＱＲに沿って、ＱからＢの方向へ長さＱＢだけ移動した場合のときに他の図形要素との交差を回避できることとなり、再配置試行部２６は、例えば移動距離が最も短い選択肢として、（２）辺ＰＱに沿って、ＱからＡの方向へ長さＱＡだけ移動することとして、再配置対象図形要素の識別子と、上記移動後の配置位置を表す情報とを配置位置決定部２４に出力し、また、再配置対象図形要素の識別子を移動抑制リストに追加して処理を終了する。
【００４８】
このように、既に配置済みとなっている図形要素を移動することで、より多くの図形要素を配置する機会を増大できる。
【００４９】
また、再配置試行部２６は、どの選択肢においても他の図形要素との重なり合いが回避できない場合は、移動距離が最も短い選択肢の位置に、再配置対象図形要素を仮に移動して、再配置対象図形要素の識別子を移動抑制リストに追加する。そして、その移動先で重なり合っている他の図形要素の識別子を用いて、さらに再配置試行処理を実行する。つまり、再配置処理によっても、回避できない干渉（重なり合いなど）が発生すると判断される場合に、既に配置されている他の図形要素の再配置を試行する。
【００５０】
また、図８においては、
（１）辺ＰＱに沿って、ＰからＡの方向へ長さＰＣだけ移動した場合、
（２）辺ＰＱに沿って、ＱからＡの方向へ長さＱＡだけ移動した場合、
（３）辺ＱＲに沿って、ＱからＢの方向へ長さＱＢだけ移動した場合、
（４）辺ＱＲに沿って、ＲからＢの方向へ長さＲＤだけ移動した場合
【００５１】
のそれぞれについて、再配置対象図形要素を移動したとき、他の図形要素との重なり合いが回避できるか否かを調べることになる。
【００５２】
［点を基準とした文字列の配置］
なお、ここまでの説明では、図形要素の配置の基準として面が指定された場合の処理について説明したが、これに限られない。例えば配置の基準として、点が指定された場合、次のように処理が行われる。
【００５３】
まず補助線設定部２１は、図９に例示するように、基準として指定された点（Ｏ）を端点として放射状に仮想の線分を複数設定する。なお、図９に示す例では、予め定められた角度ごと（図９では４５度ごと）に、補助線を設定する例を述べているが、これに限られるものではない。
【００５４】
補助線設定部２１は、複数設定した補助線と、基準となる点または他の図形要素との交点を求め、基準点と交点または交点間の距離（交差区間長）を演算する。ここで交点が複数あるときには、互いに隣接する交点間の複数の距離を算出しておく。
【００５５】
補助線設定部２１は、設定した各補助線ごとに、最も長い交差区間長となっている交差区間（最長交差区間）と、その最長交差区間を挟む交点とを特定する。そして補助線設定部２１は、予め定めた優先順位の順に補助線を選択する。補助線設定部２１は、選択した補助線において、特定した最長交差区間の交差区間長が、配置の対象となる文字列に対応する代理図形（注目代理図形）の幅Ｌを越えているか否かを調べる。
【００５６】
ここで、注目代理図形の幅Ｌを越えていれば、当該選択している補助線を候補補助線とする。補助線設定部２１は、その候補補助線と、最長交差区間とを特定する情報（線分の端点の座標情報と交差区間の端点の座標情報と、など）を空間探索部２２に出力する。
【００５７】
なお、空間探索部２２が、当該交差区間に代理図形を配置不能であった旨の情報を出力すると、補助線設定部２１は、優先順位に従って次の補助線を選択し、選択した補助線において、特定した最長交差区間の交差区間長が、注目代理図形の幅Ｌを越えているか否かを調べる処理から繰り返して行う。
【００５８】
ここで優先順位に従って次の補助線がない場合（すべての補助線において見出した最長交差区間内に代理図形を配置不能であったとき）は、補助線設定部２１は優先順位が最上位となっている補助線を再度、候補補助線として、その候補補助線と、最長交差区間とを特定する情報と、次の補助線がないことを表す情報とを空間探索部２２に出力する。
【００５９】
ここに優先順位は、例えば図９に例示するように、指定された点の右方を順位「１」、左方を順位「２」…とするなど、見やすさを基準に予め定めておけばよい。図９では、優先順位を丸で囲んだ数字で表している。また図９では注目代理図形の配置例を、補助線に交差する破線の矩形で表している。
【００６０】
空間探索部２２は、注目代理図形を、その幅方向の辺が、候補補助線の交差区間に平行になるように配し、当該配したときの注目代理図形の外周が、他の図形要素に重なり合うか否かを調べる。ここで注目代理図形の外周が、他の図形要素に重なり合う場合は、調整部２３が、上述したような注目代理図形配置調整処理を実行する。そして注目代理図形配置調整処理により、注目代理図形が配置できた場合は、そのときの注目代理図形の配置位置を特定する情報を配置位置決定部２４に出力する。
【００６１】
一方、注目代理図形配置調整処理によっても注目代理図形が配置できなかった場合は、空間探索部２２が、交差区間に代理図形を配置不能であった旨の情報を出力する。
【００６２】
なお、補助線設定部２１が、次の補助線がないことを表す情報を出力している場合は、当該情報とともに出力された、候補補助線（最も優先順位の高い補助線）の最長の交差区間に沿って、注目代理図形を仮に配置し、再配置試行処理を開始する。このとき、空間探索部２２は、固有の図形要素の識別子を発行して、この発行した識別子と、配置の対象となった文字列と、それに対応する注目代理図形の仮の配置位置を特定する情報とを関連づけて、記憶部１２に格納する。また、注目代理図形の識別子を、移動抑制リストに追加して格納する。そして注目代理図形に重なり合う他の図形要素の識別子を、再配置試行部２６に出力する。
【００６３】
一方、空間探索部２２は、現在の候補補助線上に配した注目代理図形の外周が、他の図形要素に重なり合わない場合は、そのときの注目代理図形の配置位置を特定する情報を配置位置決定部２４に出力する。
【００６４】
このように点を基準として配置位置を決定する場合、図１０に例示するように、既配置の図形要素Ｐ１，Ｐ２の隙間を縫って文字列（を囲む代理図形Ｘ）を配置できる可能性が向上する。
【００６５】
なお、線分を基準とする場合は、例えば当該線分の中点を端点として、線分に平行な方向から所定角度ごと、または任意角度に放射状に補助線を設定し、上述の、点を基準とする場合と同様の処理を行えばよい。
【００６６】
次に、本実施の形態の装置の動作例について図１１を参照しつつ説明する。本実施の形態の図形要素配置装置は、配置の対象となる文字列などが入力され、その配置の基準となる面や、点、線分などの指定を受けて、図１１に示す処理を開始する。
【００６７】
そして、まず基準として指定された点、線分、面などに基づいて、少なくとも一つの補助線を設定する（Ｓ１１）。そして補助線上で他の図形要素との交差点を見出し、交差点間の距離（交差区間長）を算出して、配置の対象となる図形要素を配置可能な交差区間があるか否かを調べる（Ｓ１２）。ここで、配置可能な交差区間がなければ（Ｎｏならば）、配置ができなかったことを報知して（Ｓ１３）、処理を終了する。
【００６８】
一方処理Ｓ１２において、配置の対象となる図形要素を配置可能な交差区間があれば（Ｙｅｓならば）、配置の対象となる図形要素を当該交差区間に沿って配置し、他の図形要素との間で干渉なく配置が可能であるか否かを調べる（Ｓ１４）。ここで、配置が可能であれば（Ｙｅｓならば）、その配置位置を配置の対象となった図形要素（文字列であればその文字列を含む）とともに記録して（Ｓ１５）、処理を終了する。
【００６９】
さらに処理Ｓ１４において、他の図形要素との間で干渉なしに配置ができなかったときには、補助線に沿って対象となる図形要素を移動して（その例が、上述の注目代理図形配置調整処理：Ｓ１６）、干渉を回避して配置できるか否かを調べる（Ｓ１７）。ここで配置ができたならば（Ｙｅｓならば）、処理Ｓ１５に移行する。
【００７０】
また、処理Ｓ１７において配置ができなければ（Ｎｏならば）、再配置の処理を開始して、干渉している他の図形要素が移動可能であるときには、他の図形要素の配置位置を調整して（Ｓ１８）、再配置できたか否かを調べる（Ｓ１９）。ここで配置ができたならば（Ｙｅｓならば）、処理Ｓ１５に移行する（Ａ）。
【００７１】
一方、処理Ｓ１９において再配置できなかった場合や、干渉している他の図形要素が移動不能なものであれば、この図１１の処理を開始する前の配置（当該配置位置については予め記憶部１２内に複写を作成しておき、ここでは作成した複写に基づいて元へ戻せばよい）に戻し（Ｓ２０）、配置ができなかったことを報知して（Ｓ２１）、処理を終了する。
【００７２】
本実施の形態によると、対象となる図形要素や既に配置されている図形要素の配置位置の調整が行われるので、より多くの図形要素を、干渉を避けつつ配置できる。
【００７３】
なお、ここまでの説明で、注目代理図形配置調整処理は、対象となる図形を補助線に平行に移動するものとしたが、図７等で示した再配置試行の処理と同様に、補助線と垂直な方向へも、移動することで干渉が回避可能であるか否かを判断してもよい。
【図面の簡単な説明】
【００７４】
【図１】本発明の実施の形態に係る図形要素配置装置の例を表す構成ブロック図である。
【図２】本発明の実施の形態に係る図形要素配置装置が規定する代理図形の例を表す説明図である。
【図３】本発明の実施の形態に係る図形要素配置装置の例を表す機能ブロック図である。
【図４】本発明の実施の形態に係る図形要素配置装置において設定される補助線の例を表す説明図である。
【図５】本発明の実施の形態に係る図形要素配置装置が保持する図形要素の情報例を表す説明図である。
【図６】本発明の実施の形態に係る図形要素配置装置における配置位置の調整処理例を表す説明図である。
【図７】本発明の実施の形態に係る図形要素配置装置における再配置試行の処理例を表す説明図である。
【図８】本発明の実施の形態に係る図形要素配置装置における再配置試行の処理の別の例を表す説明図である。
【図９】本発明の実施の形態に係る図形要素配置装置において点を基準として代理図形を配する例を表す説明図である。
【図１０】本発明の実施の形態に係る図形要素配置装置において点を基準として代理図形を配するときの効果の例を表す説明図である。
【図１１】本発明の実施の形態に係る図形要素配置装置での処理例を表すフローチャート図である。
【符号の説明】
【００７５】
１１  制御部、１２  記憶部、１３  操作部、１４  出力部、２１  補助線設定部、２２  空間探索部、２３  調整部、２４  配置位置決定部、２５  描画部、２６  再配置試行部。
【図１】
0005203690.tif 000002
【図２】
0005203690.tif 000003
【図３】
0005203690.tif 000004
【図４】
0005203690.tif 000005
【図５】
0005203690.tif 000006
【図６】
0005203690.tif 000007
【図７】
0005203690.tif 000008
【図８】
0005203690.tif 000009
【図９】
0005203690.tif 000010
【図１０】
0005203690.tif 000011
【図１１】
0005203690.tif 000012