図形要素配置装置及びプログラム
【課題】より多くの図形要素を互いに重ならないよう配置できる図形要素配置装置を提供する。
【解決手段】制御部11が、所定の条件の下で、過去に配置された他の図形要素と干渉せずに、対象となる図形要素の配置領域を探索し、対象となる図形要素が、他の図形要素と干渉せずに配置できない場合に、過去に配置された他の図形要素の再配置を試行する図形要素配置装置である。
【解決手段】制御部11が、所定の条件の下で、過去に配置された他の図形要素と干渉せずに、対象となる図形要素の配置領域を探索し、対象となる図形要素が、他の図形要素と干渉せずに配置できない場合に、過去に配置された他の図形要素の再配置を試行する図形要素配置装置である。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、複数の図形要素を、互いに重ならないように配置する図形要素配置装置及びプログラムに関する。
【背景技術】
【0002】
近年では、種々の画像がコンピュータを用いて生成されている。例えば地図などの画像もその一つである。この地図などの画像では、道路を表す線分や、建造物の形状を表す線分、地名や建物名その他の文字など、多数の図形要素が互いに重なり合わないよう配置される。
【0003】
従来、こうした図形要素の配置には主として手作業が要求されていた。また、道路や建造物などを表す線分を描き入れた後、例えば道路上の交差点を表す文字列(長さL)を配置するために、交差点の中心点を基準として、その左右方向に所定長の仮想線分を伸ばし、当該仮想線分上で、他の線分に交わらない長さLの部分があれば、当該部分を文字列の配置位置候補とする技術がある(特許文献1)。
【特許文献1】特開平8−167039号公報
【発明の開示】
【発明が解決しようとする課題】
【0004】
しかしながら、上記従来の図形要素の配置方法では、配置される文字列が多くなってくると、既に配置された文字列のために、新たな文字列の配置位置が制限され、文字列の配置位置の探索が困難になることがあった。
【0005】
本発明は上記実情に鑑みて為されたもので、より多くの図形要素を互いに重ならないよう配置できる図形要素配置装置を提供することを、その目的の一つとする。
【課題を解決するための手段】
【0006】
上記従来例の問題点を解決するための本発明は、複数の図形要素を配置する図形要素配置装置であって、所定の条件の下で、過去に配置された他の図形要素と干渉せずに、対象となる図形要素の配置領域を探索し、前記対象となる図形要素が、他の図形要素と干渉せずに配置できた場合に、その配置位置を決定する配置領域探索手段と、前記対象となる図形要素が、他の図形要素と干渉せずに配置できない場合に、前記過去に配置された他の図形要素の再配置を試行する再配置試行手段と、を含むこととしたものである。
【0007】
ここで、前記配置領域探索手段は、所定の条件の下で、対象となる図形要素の配置領域を探索し、前記探索によって見出された配置領域が他の図形要素と干渉するか否かを判断し、前記探索によって見出された配置領域が他の図形要素と干渉しない場合は、当該見出した配置領域に対象となる図形要素を配置し、前記判断により干渉すると判断される場合に、前記見出された配置領域の近傍に他の図形要素に干渉せずに前記対象となる図形要素を配置可能な配置領域があれば、当該配置領域に対象となる図形要素を配置することとしてもよい。
【0008】
さらに、前記再配置試行手段は、前記判断により干渉すると判断される場合に、前記見出された配置領域の近傍に他の図形要素に干渉せずに前記対象となる図形要素を配置可能な配置領域がない場合に、前記過去に配置された他の図形要素の再配置を試行することとしてもよい。
【0009】
さらに前記所定の条件は、指定された座標の点から予め定められた角度方向に仮想的に描画された線分に配置領域が重なり合う条件であってもよい。
【0010】
また、本発明の一態様は、コンピュータに、複数の図形要素を配置させるプログラムであって、所定の条件の下で、過去に配置された他の図形要素と干渉せずに、対象となる図形要素の配置領域を探索し、前記対象となる図形要素が、他の図形要素と干渉せずに配置できた場合に、その配置位置を決定する配置領域探索手段と、前記対象となる図形要素が、他の図形要素と干渉せずに配置できない場合に、前記過去に配置された他の図形要素の再配置を試行する再配置試行手段と、として、コンピュータを機能させることとしたものである。
【発明の効果】
【0011】
本発明によると、図形要素を互いに重ならないよう配置できる。
【発明を実施するための最良の形態】
【0012】
本発明の実施の形態について図面を参照しながら説明する。本発明の実施の形態に係る図形要素配置装置は、図1に示すように、制御部11と、記憶部12と、操作部13と、出力部14とを含んで構成されている。
【0013】
ここに制御部11は、例えばCPUなどのプログラム制御デバイスであり、記憶部12に格納されたプログラムに従って処理を行う。本実施の形態では、この制御部11は、地図などのように、複数の図形要素を、互いに重なり合わないように配置する処理を実行する。例えば制御部11は、予め定めた条件の下で、過去に配置された他の図形要素と干渉せずに、対象となる図形要素の配置領域を探索する処理と、この対象となる図形要素が、他の図形要素と干渉せずに配置できない場合に、過去に配置された他の図形要素の再配置を試行する処理(再配置試行処理)とを実行する。この制御部11の動作例については、後に詳しく述べる。
【0014】
記憶部12は、制御部11が実行するプログラムを保持するコンピュータ可読な記録媒体として動作する。また、この記憶部12は、制御部11のワークメモリとしても動作している。操作部13は、例えばマウスやキーボードなどであり、利用者の指示操作を受け入れて、当該指示操作の内容を制御部11に出力する。
【0015】
出力部14は、例えば液晶ディスプレイなどの表示デバイスを含む。この出力部14は、図形要素を配置した画像の少なくとも一部を表示出力する。また、この出力部14は、図形要素を配置して得られた画像の情報を出力する。
【0016】
ここで制御部11によって実行される処理の詳しい内容について述べる。本実施の形態の制御部11は、基本的には、図形要素である線分や文字列などを描画する処理を行う。この処理では、記憶部12に、描画の対象となる図形要素を特定する情報が蓄積される。この情報は、出力部14に対して情報が表示出力される際などに供される。
【0017】
例えば、この記憶部12には、各図形要素について、図形要素ごとに固有の識別子と、図形要素の種別と、図形要素を描画するのに必要となる座標情報と、色の情報などとが関連づけて記録されている。図形要素が線分である場合は、その描画に必要となる座標情報として、線分の端点を表す座標情報が記録される。また、図形要素が文字列である場合は、図2に例示するように、その描画に必要となる文字列を包含する図形要素(以下、代理図形と呼ぶ)の頂点の座標情報と、代理図形内部に描画されるべき文字列を表す情報などが記録される。
【0018】
また制御部11は、記憶部12に、その後の移動を抑制する移動抑制リストを格納する。この移動抑制リストには、移動を抑制する対象となる図形要素の識別子が列挙して保持される。
【0019】
さらに制御部11は、図形要素である線分で囲まれた「面」、線分、及び図形要素を配置した画像上の一点を基準として、文字列を配置する処理を行う。以下、この処理について説明する。
【0020】
すなわち、本実施の形態の制御部11が実行するプログラムは、機能的には図3に示すように、補助線設定部21と、空間探索部22と、調整部23と、配置位置決定部24と、描画部25と、再配置試行部26とを含んで構成される。
【0021】
補助線設定部21は、配置の基準として、面や、線分、点などの指定と、描画するべき文字列の情報とを受け入れる。補助線設定部21は、受け入れた文字列を包含する代理図形のサイズを算出する。一般に文字列は矩形状に配列されるので、ここでの代理図形は矩形状であるとすればよい。代理図形を矩形とする場合、そのサイズは幅L及び高さHで規定できる。ここで幅は一行あたりの文字列の配置幅、高さは行方向の長さ(一行の文字列配列に垂直な方向の長さ)を表す。
【0022】
補助線設定部21は、面が指定された場合は、図4に例示するように、面内に仮想の平行線(補助線)を複数設定する。そして補助線設定部21は、複数設定した補助線と、面を構成する線分(境界線)など、他の図形要素との交点を求め交点間の距離(交差区間長)を演算する。さらに補助線設定部21は、交差区間長が最大となっている補助線(仮候補補助線)を特定する。
【0023】
補助線設定部21は、交差区間長が最大となる仮候補補助線について、当該交差区間長が、描画するべき文字列に対応する代理図形(以下、注目代理図形と呼ぶ)の幅Lを越えているか否かを調べる。このとき、交差区間長が文字列の注目代理図形の幅Lを越えていなければ、補助線設定部21は配置不能と判断して処理を中断してもよい。
【0024】
また、交差区間長が注目代理図形の幅Lを越えていれば、補助線設定部21は当該仮候補補助線を候補補助線とする。補助線設定部21は、その候補補助線と、交点間の位置(交差区間)とを特定する情報(線分の端点の座標情報と交差区間の端点の座標情報と、など)を空間探索部22に出力する。
【0025】
空間探索部22は、注目代理図形を、その幅方向の辺が、候補補助線の交差区間に平行になるよう配し、当該配したときの注目代理図形の外周が、他の図形要素に重なり合っている(干渉している)か否かを調べる。なお、注目代理図形を配する場合に、候補補助線と注目代理図形とが交差しないよう配してもよいし、候補補助線と注目代理図形とを交差させるよう配してもよい。
【0026】
ここで、候補補助線に沿って配した注目代理図形の外周が、他の図形要素に重なり合わない場合は、そのときの注目代理図形の配置位置を特定する情報(例えば代理図形が矩形であれば、対角線上の二点の座標情報)を配置位置決定部24に出力する。
【0027】
そして配置位置決定部24は、固有の図形要素の識別子を発行して、この発行した識別子と、配置の対象となった文字列と、それに対応する代理図形の配置位置を特定する情報とを関連づけて、図5に示したように、記憶部12に格納する。また、配置位置決定部24は、配置した文字列に対応する図形要素の識別子を、移動抑制リストに追加して格納する。
【0028】
一方、空間探索部22の処理において、候補補助線に沿って配した注目代理図形の外周が、他の図形要素(環境線や他の代理図形など)に重なり合う場合は、空間探索部22は、調整部23に注目代理図形の位置を調整させる。ここで調整部23は、注目代理図形を候補補助線に沿って平行移動し、他の図形要素に干渉せずに配置できる位置があるか否かを調べる(注目代理図形配置調整処理)。この処理は例えば次のようになる。一例として図6(a)に示すように、注目代理図形B1に干渉する他の図形要素B2があり、また注目代理図形に対して現在は干渉していないが、その近傍に配された環境線の図形要素Eがあるとする。このとき、調整部23は、注目代理図形B1の候補補助線Xに平行な二辺(辺PS,QR)を延長し、現在干渉のない環境線の図形要素Eに交差する点をα,βとして、各辺に対応する延長線部分の長さ、Sαと、Rβとを求める。
【0029】
なお、図6(b)に示すように、注目代理図形B1が環境線Fに干渉している場合もある。このときには、注目代理図形B1に現在干渉のない環境線Eに、注目代理図形B1の候補補助線Xに平行な二辺(辺PS,QR)を延長した線分が交差する点をα,βとして、各辺に対応する延長線部分の長さ、Sαと、Rβとを求める。
【0030】
さらに、図6(c)に示すように、注目代理図形B1の候補補助線Xに平行な二辺(辺PS,QR)を延長した線分の少なくとも一方が環境線に交差しない場合もある。このときには延長線上にαまたはβを仮想的に、SαまたはRβが予め定めた値となる位置に配置して、SαとRβとを定める。図6(c)では、辺PSの延長線は点αで、現在干渉のない環境線Eに交わるが、辺QRの延長線が環境線に交わらない例を示している。そこでこの例では、Rから予め定めた長さlmaxの位置に点βを仮想的に設定している。
【0031】
なお、環境線Eに延長線が交わる場合であっても、交差点αまでの距離Sα(またはRβ)がこのlmaxを越える場合は、点α(または点β)を仮想的に、Sα=lmax(またはRβ=lmax)となる位置に設定してもよい。
【0032】
また、調整部23は、現在干渉している他の図形要素B2との干渉を解消するために移動するべき方向と距離とを演算する。図6の例では、辺PSとその延長線が、他の図形要素B2との間で、点L及び点Mにて交差している。そこで、PからSへの方向へ移動する場合、距離PLだけ移動すれば、注目代理図形B1と図形要素B2との干渉が回避できる。また、SからPへの方向へ移動する場合、距離SMだけ移動すれば注目代理図形B1と図形要素B2との干渉が回避できる。
【0033】
調整部23は、PからSの方向に延長された各辺からの延長線分がさらに他の図形要素と交差する点までの距離Sα,Rβを参照し、そのうち短いもの(図6ではSα<Rβのように図示しているので、この場合Sα)を取り出す。そして、当該取り出した値が、干渉を回避するために移動するべき距離よりも大きいか否かを調べる(図6の例では、Sα>PLか否かを調べる)。
【0034】
ここで取り出した値が、干渉を回避するために移動するべき距離よりも大きいならば、調整部23は、注目代理図形を、距離D(Sα>D>PL)だけ移動して、他の図形要素との干渉を回避し、回避後の注目代理図形の配置位置を特定する情報を配置位置決定部24に出力して、注目代理図形配置調整処理を終了する。
【0035】
一方で、上記取り出した値が、干渉を回避するために移動するべき距離以下の場合は、調整部23はその旨を、空間探索部22に出力する。そして空間探索部22は、干渉が回避できないとして、現在の候補補助線を除く、他の補助線から改めて仮候補補助線を選択する。つまり、この場合は、交差区間長の長い順に候補補助線を選択しつつ、注目代理図形を配して、他の図形要素に重なり合わないかを調べる。なお、他の図形要素に干渉せずに注目代理図形を配置できる候補補助線が見出せない場合(当初設定したすべての補助線に沿って文字列等が配置できない場合)は、最初の候補補助線(最も長い交差区間長を有する候補補助線)に沿って注目代理図形を仮に配置し、再配置試行処理を開始する。すなわち空間探索部22は、まず、干渉している他の図形要素が、移動可能なものであるか否かを判断する。ここで移動可能なものとは、文字列の代理図形などであり、図形要素ごとに指定されてもよいし、図形要素の種別ごとに判断されてもよい。
【0036】
干渉している他の図形要素が移動可能なものである場合、空間探索部22は、固有の図形要素の識別子を発行して、この発行した識別子と、配置の対象となった文字列と、対応する注目代理図形の配置位置を特定する情報とを関連づけて、記憶部12に格納する(図5)。また、仮に配置した文字列に対応する図形要素の識別子を、移動抑制リストに追加して格納する。そして、配置の対象となった文字列の代理図形に重なり合う他の図形要素の識別子を、再配置試行部26に出力する。
【0037】
干渉している他の図形要素が、環境線など移動不能なものである場合、空間探索部22は、エラーを報知するなどして、処理を中断する。
【0038】
描画部25は、配置位置決定部24が記憶部12に格納した情報を参照して、配置の対象となった文字列を、それぞれ対応する情報で特定される代理図形の配置位置(領域)内に描画する。この描画部25による描画結果は、例えば出力部14によるディスプレイ等への出力に供される。
【0039】
再配置試行部26は、空間探索部22の処理により、文字列の配置位置が見出せない場合に、それまでに配置した文字列等、他の図形要素の配置位置を移動して、配置位置が得られるか否かを試行する。
【0040】
すなわち本実施の形態では、一度配置位置が見出されると、その文字列などの図形要素は、移動抑制の対象として設定される。しかしながら、その後の図形要素(対象図形要素と呼ぶ)が配置できない場合は、過去に配置位置が決定され、移動抑制の対象となった図形要素であっても、再度、その配置位置を調整する処理が行われ、対象図形要素の配置が可能となるか否かが試行されるのである。
【0041】
次に、この再配置試行部26の具体的な処理例について説明する。再配置試行部26は、再配置試行処理の対象となる図形要素(既配置の図形要素であって、環境線など移動不能なものを除く:以下、再配置対象図形要素と呼ぶ)の識別子の入力を受け入れる。そして入力を受け入れた識別子を、移動抑制リストから除去する。
【0042】
再配置試行部26は、図7に示すように、再配置対象図形要素を包含する代理図形を設定(例えば再配置対象図形要素に外接する外接矩形そのもの、または外接矩形を外側へ所定量だけ拡大して得る)し(S1)、代理図形の各辺をその両側へ所定量だけ延長する(S2)。また、各辺を延長して得た線分が他の図形要素に交差する場合は、その交差の点から外への延長部分を除去する(S3)。
【0043】
次に再配置試行部26は、各辺において、他の図形要素(例えば他の代理図形の線分)が交差する位置を点(以下、交差点という)として特定する(S4)。図7においては、再配置対象図形要素は、他の代理図形と、点A,Bで交差することを示している。また、図8に例示するように、再配置対象図形要素内に、他の図形要素を構成する線分の端点(当該他の図形要素が多角形であれば、その頂点)が含まれている場合、処理S4では、当該頂点から、当該他の図形要素との交差がある辺へ下した垂線の足(図8のC,D)をも交差点として特定する。
【0044】
他の図形要素との交差がある辺の両端の頂点から、各頂点より最も遠い位置にある交差点でも長さを求める(S5)。図7においては、頂点P,Qから交差点Aまでの距離、PA及びQAと、頂点Q,Rから交差点Bまでの距離、QB及びRBとを求める。また、図8においては、図8(b)に示すように、PC,QA,QB,RDをそれぞれ求めることになる。
【0045】
この処理S5で求めた長さが、移動量の候補となる。すなわち、再配置試行部26は、図7を例として説明すると、
【0046】
(1)辺PQに沿って、PからAの方向へ長さPAだけ移動した場合、
(2)辺PQに沿って、QからAの方向へ長さQAだけ移動した場合、
(3)辺QRに沿って、QからBの方向へ長さQBだけ移動した場合、
(4)辺QRに沿って、RからBの方向へ長さRBだけ移動した場合
【0047】
のそれぞれについて、再配置対象図形要素を移動したとき、他の図形要素との重なり合いが回避できるか否かを調べる。ここでは、(2)辺PQに沿って、QからAの方向へ長さQAだけ移動した場合、または(3)辺QRに沿って、QからBの方向へ長さQBだけ移動した場合のときに他の図形要素との交差を回避できることとなり、再配置試行部26は、例えば移動距離が最も短い選択肢として、(2)辺PQに沿って、QからAの方向へ長さQAだけ移動することとして、再配置対象図形要素の識別子と、上記移動後の配置位置を表す情報とを配置位置決定部24に出力し、また、再配置対象図形要素の識別子を移動抑制リストに追加して処理を終了する。
【0048】
このように、既に配置済みとなっている図形要素を移動することで、より多くの図形要素を配置する機会を増大できる。
【0049】
また、再配置試行部26は、どの選択肢においても他の図形要素との重なり合いが回避できない場合は、移動距離が最も短い選択肢の位置に、再配置対象図形要素を仮に移動して、再配置対象図形要素の識別子を移動抑制リストに追加する。そして、その移動先で重なり合っている他の図形要素の識別子を用いて、さらに再配置試行処理を実行する。つまり、再配置処理によっても、回避できない干渉(重なり合いなど)が発生すると判断される場合に、既に配置されている他の図形要素の再配置を試行する。
【0050】
また、図8においては、
(1)辺PQに沿って、PからAの方向へ長さPCだけ移動した場合、
(2)辺PQに沿って、QからAの方向へ長さQAだけ移動した場合、
(3)辺QRに沿って、QからBの方向へ長さQBだけ移動した場合、
(4)辺QRに沿って、RからBの方向へ長さRDだけ移動した場合
【0051】
のそれぞれについて、再配置対象図形要素を移動したとき、他の図形要素との重なり合いが回避できるか否かを調べることになる。
【0052】
[点を基準とした文字列の配置]
なお、ここまでの説明では、図形要素の配置の基準として面が指定された場合の処理について説明したが、これに限られない。例えば配置の基準として、点が指定された場合、次のように処理が行われる。
【0053】
まず補助線設定部21は、図9に例示するように、基準として指定された点(O)を端点として放射状に仮想の線分を複数設定する。なお、図9に示す例では、予め定められた角度ごと(図9では45度ごと)に、補助線を設定する例を述べているが、これに限られるものではない。
【0054】
補助線設定部21は、複数設定した補助線と、基準となる点または他の図形要素との交点を求め、基準点と交点または交点間の距離(交差区間長)を演算する。ここで交点が複数あるときには、互いに隣接する交点間の複数の距離を算出しておく。
【0055】
補助線設定部21は、設定した各補助線ごとに、最も長い交差区間長となっている交差区間(最長交差区間)と、その最長交差区間を挟む交点とを特定する。そして補助線設定部21は、予め定めた優先順位の順に補助線を選択する。補助線設定部21は、選択した補助線において、特定した最長交差区間の交差区間長が、配置の対象となる文字列に対応する代理図形(注目代理図形)の幅Lを越えているか否かを調べる。
【0056】
ここで、注目代理図形の幅Lを越えていれば、当該選択している補助線を候補補助線とする。補助線設定部21は、その候補補助線と、最長交差区間とを特定する情報(線分の端点の座標情報と交差区間の端点の座標情報と、など)を空間探索部22に出力する。
【0057】
なお、空間探索部22が、当該交差区間に代理図形を配置不能であった旨の情報を出力すると、補助線設定部21は、優先順位に従って次の補助線を選択し、選択した補助線において、特定した最長交差区間の交差区間長が、注目代理図形の幅Lを越えているか否かを調べる処理から繰り返して行う。
【0058】
ここで優先順位に従って次の補助線がない場合(すべての補助線において見出した最長交差区間内に代理図形を配置不能であったとき)は、補助線設定部21は優先順位が最上位となっている補助線を再度、候補補助線として、その候補補助線と、最長交差区間とを特定する情報と、次の補助線がないことを表す情報とを空間探索部22に出力する。
【0059】
ここに優先順位は、例えば図9に例示するように、指定された点の右方を順位「1」、左方を順位「2」…とするなど、見やすさを基準に予め定めておけばよい。図9では、優先順位を丸で囲んだ数字で表している。また図9では注目代理図形の配置例を、補助線に交差する破線の矩形で表している。
【0060】
空間探索部22は、注目代理図形を、その幅方向の辺が、候補補助線の交差区間に平行になるように配し、当該配したときの注目代理図形の外周が、他の図形要素に重なり合うか否かを調べる。ここで注目代理図形の外周が、他の図形要素に重なり合う場合は、調整部23が、上述したような注目代理図形配置調整処理を実行する。そして注目代理図形配置調整処理により、注目代理図形が配置できた場合は、そのときの注目代理図形の配置位置を特定する情報を配置位置決定部24に出力する。
【0061】
一方、注目代理図形配置調整処理によっても注目代理図形が配置できなかった場合は、空間探索部22が、交差区間に代理図形を配置不能であった旨の情報を出力する。
【0062】
なお、補助線設定部21が、次の補助線がないことを表す情報を出力している場合は、当該情報とともに出力された、候補補助線(最も優先順位の高い補助線)の最長の交差区間に沿って、注目代理図形を仮に配置し、再配置試行処理を開始する。このとき、空間探索部22は、固有の図形要素の識別子を発行して、この発行した識別子と、配置の対象となった文字列と、それに対応する注目代理図形の仮の配置位置を特定する情報とを関連づけて、記憶部12に格納する。また、注目代理図形の識別子を、移動抑制リストに追加して格納する。そして注目代理図形に重なり合う他の図形要素の識別子を、再配置試行部26に出力する。
【0063】
一方、空間探索部22は、現在の候補補助線上に配した注目代理図形の外周が、他の図形要素に重なり合わない場合は、そのときの注目代理図形の配置位置を特定する情報を配置位置決定部24に出力する。
【0064】
このように点を基準として配置位置を決定する場合、図10に例示するように、既配置の図形要素P1,P2の隙間を縫って文字列(を囲む代理図形X)を配置できる可能性が向上する。
【0065】
なお、線分を基準とする場合は、例えば当該線分の中点を端点として、線分に平行な方向から所定角度ごと、または任意角度に放射状に補助線を設定し、上述の、点を基準とする場合と同様の処理を行えばよい。
【0066】
次に、本実施の形態の装置の動作例について図11を参照しつつ説明する。本実施の形態の図形要素配置装置は、配置の対象となる文字列などが入力され、その配置の基準となる面や、点、線分などの指定を受けて、図11に示す処理を開始する。
【0067】
そして、まず基準として指定された点、線分、面などに基づいて、少なくとも一つの補助線を設定する(S11)。そして補助線上で他の図形要素との交差点を見出し、交差点間の距離(交差区間長)を算出して、配置の対象となる図形要素を配置可能な交差区間があるか否かを調べる(S12)。ここで、配置可能な交差区間がなければ(Noならば)、配置ができなかったことを報知して(S13)、処理を終了する。
【0068】
一方処理S12において、配置の対象となる図形要素を配置可能な交差区間があれば(Yesならば)、配置の対象となる図形要素を当該交差区間に沿って配置し、他の図形要素との間で干渉なく配置が可能であるか否かを調べる(S14)。ここで、配置が可能であれば(Yesならば)、その配置位置を配置の対象となった図形要素(文字列であればその文字列を含む)とともに記録して(S15)、処理を終了する。
【0069】
さらに処理S14において、他の図形要素との間で干渉なしに配置ができなかったときには、補助線に沿って対象となる図形要素を移動して(その例が、上述の注目代理図形配置調整処理:S16)、干渉を回避して配置できるか否かを調べる(S17)。ここで配置ができたならば(Yesならば)、処理S15に移行する。
【0070】
また、処理S17において配置ができなければ(Noならば)、再配置の処理を開始して、干渉している他の図形要素が移動可能であるときには、他の図形要素の配置位置を調整して(S18)、再配置できたか否かを調べる(S19)。ここで配置ができたならば(Yesならば)、処理S15に移行する(A)。
【0071】
一方、処理S19において再配置できなかった場合や、干渉している他の図形要素が移動不能なものであれば、この図11の処理を開始する前の配置(当該配置位置については予め記憶部12内に複写を作成しておき、ここでは作成した複写に基づいて元へ戻せばよい)に戻し(S20)、配置ができなかったことを報知して(S21)、処理を終了する。
【0072】
本実施の形態によると、対象となる図形要素や既に配置されている図形要素の配置位置の調整が行われるので、より多くの図形要素を、干渉を避けつつ配置できる。
【0073】
なお、ここまでの説明で、注目代理図形配置調整処理は、対象となる図形を補助線に平行に移動するものとしたが、図7等で示した再配置試行の処理と同様に、補助線と垂直な方向へも、移動することで干渉が回避可能であるか否かを判断してもよい。
【図面の簡単な説明】
【0074】
【図1】本発明の実施の形態に係る図形要素配置装置の例を表す構成ブロック図である。
【図2】本発明の実施の形態に係る図形要素配置装置が規定する代理図形の例を表す説明図である。
【図3】本発明の実施の形態に係る図形要素配置装置の例を表す機能ブロック図である。
【図4】本発明の実施の形態に係る図形要素配置装置において設定される補助線の例を表す説明図である。
【図5】本発明の実施の形態に係る図形要素配置装置が保持する図形要素の情報例を表す説明図である。
【図6】本発明の実施の形態に係る図形要素配置装置における配置位置の調整処理例を表す説明図である。
【図7】本発明の実施の形態に係る図形要素配置装置における再配置試行の処理例を表す説明図である。
【図8】本発明の実施の形態に係る図形要素配置装置における再配置試行の処理の別の例を表す説明図である。
【図9】本発明の実施の形態に係る図形要素配置装置において点を基準として代理図形を配する例を表す説明図である。
【図10】本発明の実施の形態に係る図形要素配置装置において点を基準として代理図形を配するときの効果の例を表す説明図である。
【図11】本発明の実施の形態に係る図形要素配置装置での処理例を表すフローチャート図である。
【符号の説明】
【0075】
11 制御部、12 記憶部、13 操作部、14 出力部、21 補助線設定部、22 空間探索部、23 調整部、24 配置位置決定部、25 描画部、26 再配置試行部。
【技術分野】
【0001】
本発明は、複数の図形要素を、互いに重ならないように配置する図形要素配置装置及びプログラムに関する。
【背景技術】
【0002】
近年では、種々の画像がコンピュータを用いて生成されている。例えば地図などの画像もその一つである。この地図などの画像では、道路を表す線分や、建造物の形状を表す線分、地名や建物名その他の文字など、多数の図形要素が互いに重なり合わないよう配置される。
【0003】
従来、こうした図形要素の配置には主として手作業が要求されていた。また、道路や建造物などを表す線分を描き入れた後、例えば道路上の交差点を表す文字列(長さL)を配置するために、交差点の中心点を基準として、その左右方向に所定長の仮想線分を伸ばし、当該仮想線分上で、他の線分に交わらない長さLの部分があれば、当該部分を文字列の配置位置候補とする技術がある(特許文献1)。
【特許文献1】特開平8−167039号公報
【発明の開示】
【発明が解決しようとする課題】
【0004】
しかしながら、上記従来の図形要素の配置方法では、配置される文字列が多くなってくると、既に配置された文字列のために、新たな文字列の配置位置が制限され、文字列の配置位置の探索が困難になることがあった。
【0005】
本発明は上記実情に鑑みて為されたもので、より多くの図形要素を互いに重ならないよう配置できる図形要素配置装置を提供することを、その目的の一つとする。
【課題を解決するための手段】
【0006】
上記従来例の問題点を解決するための本発明は、複数の図形要素を配置する図形要素配置装置であって、所定の条件の下で、過去に配置された他の図形要素と干渉せずに、対象となる図形要素の配置領域を探索し、前記対象となる図形要素が、他の図形要素と干渉せずに配置できた場合に、その配置位置を決定する配置領域探索手段と、前記対象となる図形要素が、他の図形要素と干渉せずに配置できない場合に、前記過去に配置された他の図形要素の再配置を試行する再配置試行手段と、を含むこととしたものである。
【0007】
ここで、前記配置領域探索手段は、所定の条件の下で、対象となる図形要素の配置領域を探索し、前記探索によって見出された配置領域が他の図形要素と干渉するか否かを判断し、前記探索によって見出された配置領域が他の図形要素と干渉しない場合は、当該見出した配置領域に対象となる図形要素を配置し、前記判断により干渉すると判断される場合に、前記見出された配置領域の近傍に他の図形要素に干渉せずに前記対象となる図形要素を配置可能な配置領域があれば、当該配置領域に対象となる図形要素を配置することとしてもよい。
【0008】
さらに、前記再配置試行手段は、前記判断により干渉すると判断される場合に、前記見出された配置領域の近傍に他の図形要素に干渉せずに前記対象となる図形要素を配置可能な配置領域がない場合に、前記過去に配置された他の図形要素の再配置を試行することとしてもよい。
【0009】
さらに前記所定の条件は、指定された座標の点から予め定められた角度方向に仮想的に描画された線分に配置領域が重なり合う条件であってもよい。
【0010】
また、本発明の一態様は、コンピュータに、複数の図形要素を配置させるプログラムであって、所定の条件の下で、過去に配置された他の図形要素と干渉せずに、対象となる図形要素の配置領域を探索し、前記対象となる図形要素が、他の図形要素と干渉せずに配置できた場合に、その配置位置を決定する配置領域探索手段と、前記対象となる図形要素が、他の図形要素と干渉せずに配置できない場合に、前記過去に配置された他の図形要素の再配置を試行する再配置試行手段と、として、コンピュータを機能させることとしたものである。
【発明の効果】
【0011】
本発明によると、図形要素を互いに重ならないよう配置できる。
【発明を実施するための最良の形態】
【0012】
本発明の実施の形態について図面を参照しながら説明する。本発明の実施の形態に係る図形要素配置装置は、図1に示すように、制御部11と、記憶部12と、操作部13と、出力部14とを含んで構成されている。
【0013】
ここに制御部11は、例えばCPUなどのプログラム制御デバイスであり、記憶部12に格納されたプログラムに従って処理を行う。本実施の形態では、この制御部11は、地図などのように、複数の図形要素を、互いに重なり合わないように配置する処理を実行する。例えば制御部11は、予め定めた条件の下で、過去に配置された他の図形要素と干渉せずに、対象となる図形要素の配置領域を探索する処理と、この対象となる図形要素が、他の図形要素と干渉せずに配置できない場合に、過去に配置された他の図形要素の再配置を試行する処理(再配置試行処理)とを実行する。この制御部11の動作例については、後に詳しく述べる。
【0014】
記憶部12は、制御部11が実行するプログラムを保持するコンピュータ可読な記録媒体として動作する。また、この記憶部12は、制御部11のワークメモリとしても動作している。操作部13は、例えばマウスやキーボードなどであり、利用者の指示操作を受け入れて、当該指示操作の内容を制御部11に出力する。
【0015】
出力部14は、例えば液晶ディスプレイなどの表示デバイスを含む。この出力部14は、図形要素を配置した画像の少なくとも一部を表示出力する。また、この出力部14は、図形要素を配置して得られた画像の情報を出力する。
【0016】
ここで制御部11によって実行される処理の詳しい内容について述べる。本実施の形態の制御部11は、基本的には、図形要素である線分や文字列などを描画する処理を行う。この処理では、記憶部12に、描画の対象となる図形要素を特定する情報が蓄積される。この情報は、出力部14に対して情報が表示出力される際などに供される。
【0017】
例えば、この記憶部12には、各図形要素について、図形要素ごとに固有の識別子と、図形要素の種別と、図形要素を描画するのに必要となる座標情報と、色の情報などとが関連づけて記録されている。図形要素が線分である場合は、その描画に必要となる座標情報として、線分の端点を表す座標情報が記録される。また、図形要素が文字列である場合は、図2に例示するように、その描画に必要となる文字列を包含する図形要素(以下、代理図形と呼ぶ)の頂点の座標情報と、代理図形内部に描画されるべき文字列を表す情報などが記録される。
【0018】
また制御部11は、記憶部12に、その後の移動を抑制する移動抑制リストを格納する。この移動抑制リストには、移動を抑制する対象となる図形要素の識別子が列挙して保持される。
【0019】
さらに制御部11は、図形要素である線分で囲まれた「面」、線分、及び図形要素を配置した画像上の一点を基準として、文字列を配置する処理を行う。以下、この処理について説明する。
【0020】
すなわち、本実施の形態の制御部11が実行するプログラムは、機能的には図3に示すように、補助線設定部21と、空間探索部22と、調整部23と、配置位置決定部24と、描画部25と、再配置試行部26とを含んで構成される。
【0021】
補助線設定部21は、配置の基準として、面や、線分、点などの指定と、描画するべき文字列の情報とを受け入れる。補助線設定部21は、受け入れた文字列を包含する代理図形のサイズを算出する。一般に文字列は矩形状に配列されるので、ここでの代理図形は矩形状であるとすればよい。代理図形を矩形とする場合、そのサイズは幅L及び高さHで規定できる。ここで幅は一行あたりの文字列の配置幅、高さは行方向の長さ(一行の文字列配列に垂直な方向の長さ)を表す。
【0022】
補助線設定部21は、面が指定された場合は、図4に例示するように、面内に仮想の平行線(補助線)を複数設定する。そして補助線設定部21は、複数設定した補助線と、面を構成する線分(境界線)など、他の図形要素との交点を求め交点間の距離(交差区間長)を演算する。さらに補助線設定部21は、交差区間長が最大となっている補助線(仮候補補助線)を特定する。
【0023】
補助線設定部21は、交差区間長が最大となる仮候補補助線について、当該交差区間長が、描画するべき文字列に対応する代理図形(以下、注目代理図形と呼ぶ)の幅Lを越えているか否かを調べる。このとき、交差区間長が文字列の注目代理図形の幅Lを越えていなければ、補助線設定部21は配置不能と判断して処理を中断してもよい。
【0024】
また、交差区間長が注目代理図形の幅Lを越えていれば、補助線設定部21は当該仮候補補助線を候補補助線とする。補助線設定部21は、その候補補助線と、交点間の位置(交差区間)とを特定する情報(線分の端点の座標情報と交差区間の端点の座標情報と、など)を空間探索部22に出力する。
【0025】
空間探索部22は、注目代理図形を、その幅方向の辺が、候補補助線の交差区間に平行になるよう配し、当該配したときの注目代理図形の外周が、他の図形要素に重なり合っている(干渉している)か否かを調べる。なお、注目代理図形を配する場合に、候補補助線と注目代理図形とが交差しないよう配してもよいし、候補補助線と注目代理図形とを交差させるよう配してもよい。
【0026】
ここで、候補補助線に沿って配した注目代理図形の外周が、他の図形要素に重なり合わない場合は、そのときの注目代理図形の配置位置を特定する情報(例えば代理図形が矩形であれば、対角線上の二点の座標情報)を配置位置決定部24に出力する。
【0027】
そして配置位置決定部24は、固有の図形要素の識別子を発行して、この発行した識別子と、配置の対象となった文字列と、それに対応する代理図形の配置位置を特定する情報とを関連づけて、図5に示したように、記憶部12に格納する。また、配置位置決定部24は、配置した文字列に対応する図形要素の識別子を、移動抑制リストに追加して格納する。
【0028】
一方、空間探索部22の処理において、候補補助線に沿って配した注目代理図形の外周が、他の図形要素(環境線や他の代理図形など)に重なり合う場合は、空間探索部22は、調整部23に注目代理図形の位置を調整させる。ここで調整部23は、注目代理図形を候補補助線に沿って平行移動し、他の図形要素に干渉せずに配置できる位置があるか否かを調べる(注目代理図形配置調整処理)。この処理は例えば次のようになる。一例として図6(a)に示すように、注目代理図形B1に干渉する他の図形要素B2があり、また注目代理図形に対して現在は干渉していないが、その近傍に配された環境線の図形要素Eがあるとする。このとき、調整部23は、注目代理図形B1の候補補助線Xに平行な二辺(辺PS,QR)を延長し、現在干渉のない環境線の図形要素Eに交差する点をα,βとして、各辺に対応する延長線部分の長さ、Sαと、Rβとを求める。
【0029】
なお、図6(b)に示すように、注目代理図形B1が環境線Fに干渉している場合もある。このときには、注目代理図形B1に現在干渉のない環境線Eに、注目代理図形B1の候補補助線Xに平行な二辺(辺PS,QR)を延長した線分が交差する点をα,βとして、各辺に対応する延長線部分の長さ、Sαと、Rβとを求める。
【0030】
さらに、図6(c)に示すように、注目代理図形B1の候補補助線Xに平行な二辺(辺PS,QR)を延長した線分の少なくとも一方が環境線に交差しない場合もある。このときには延長線上にαまたはβを仮想的に、SαまたはRβが予め定めた値となる位置に配置して、SαとRβとを定める。図6(c)では、辺PSの延長線は点αで、現在干渉のない環境線Eに交わるが、辺QRの延長線が環境線に交わらない例を示している。そこでこの例では、Rから予め定めた長さlmaxの位置に点βを仮想的に設定している。
【0031】
なお、環境線Eに延長線が交わる場合であっても、交差点αまでの距離Sα(またはRβ)がこのlmaxを越える場合は、点α(または点β)を仮想的に、Sα=lmax(またはRβ=lmax)となる位置に設定してもよい。
【0032】
また、調整部23は、現在干渉している他の図形要素B2との干渉を解消するために移動するべき方向と距離とを演算する。図6の例では、辺PSとその延長線が、他の図形要素B2との間で、点L及び点Mにて交差している。そこで、PからSへの方向へ移動する場合、距離PLだけ移動すれば、注目代理図形B1と図形要素B2との干渉が回避できる。また、SからPへの方向へ移動する場合、距離SMだけ移動すれば注目代理図形B1と図形要素B2との干渉が回避できる。
【0033】
調整部23は、PからSの方向に延長された各辺からの延長線分がさらに他の図形要素と交差する点までの距離Sα,Rβを参照し、そのうち短いもの(図6ではSα<Rβのように図示しているので、この場合Sα)を取り出す。そして、当該取り出した値が、干渉を回避するために移動するべき距離よりも大きいか否かを調べる(図6の例では、Sα>PLか否かを調べる)。
【0034】
ここで取り出した値が、干渉を回避するために移動するべき距離よりも大きいならば、調整部23は、注目代理図形を、距離D(Sα>D>PL)だけ移動して、他の図形要素との干渉を回避し、回避後の注目代理図形の配置位置を特定する情報を配置位置決定部24に出力して、注目代理図形配置調整処理を終了する。
【0035】
一方で、上記取り出した値が、干渉を回避するために移動するべき距離以下の場合は、調整部23はその旨を、空間探索部22に出力する。そして空間探索部22は、干渉が回避できないとして、現在の候補補助線を除く、他の補助線から改めて仮候補補助線を選択する。つまり、この場合は、交差区間長の長い順に候補補助線を選択しつつ、注目代理図形を配して、他の図形要素に重なり合わないかを調べる。なお、他の図形要素に干渉せずに注目代理図形を配置できる候補補助線が見出せない場合(当初設定したすべての補助線に沿って文字列等が配置できない場合)は、最初の候補補助線(最も長い交差区間長を有する候補補助線)に沿って注目代理図形を仮に配置し、再配置試行処理を開始する。すなわち空間探索部22は、まず、干渉している他の図形要素が、移動可能なものであるか否かを判断する。ここで移動可能なものとは、文字列の代理図形などであり、図形要素ごとに指定されてもよいし、図形要素の種別ごとに判断されてもよい。
【0036】
干渉している他の図形要素が移動可能なものである場合、空間探索部22は、固有の図形要素の識別子を発行して、この発行した識別子と、配置の対象となった文字列と、対応する注目代理図形の配置位置を特定する情報とを関連づけて、記憶部12に格納する(図5)。また、仮に配置した文字列に対応する図形要素の識別子を、移動抑制リストに追加して格納する。そして、配置の対象となった文字列の代理図形に重なり合う他の図形要素の識別子を、再配置試行部26に出力する。
【0037】
干渉している他の図形要素が、環境線など移動不能なものである場合、空間探索部22は、エラーを報知するなどして、処理を中断する。
【0038】
描画部25は、配置位置決定部24が記憶部12に格納した情報を参照して、配置の対象となった文字列を、それぞれ対応する情報で特定される代理図形の配置位置(領域)内に描画する。この描画部25による描画結果は、例えば出力部14によるディスプレイ等への出力に供される。
【0039】
再配置試行部26は、空間探索部22の処理により、文字列の配置位置が見出せない場合に、それまでに配置した文字列等、他の図形要素の配置位置を移動して、配置位置が得られるか否かを試行する。
【0040】
すなわち本実施の形態では、一度配置位置が見出されると、その文字列などの図形要素は、移動抑制の対象として設定される。しかしながら、その後の図形要素(対象図形要素と呼ぶ)が配置できない場合は、過去に配置位置が決定され、移動抑制の対象となった図形要素であっても、再度、その配置位置を調整する処理が行われ、対象図形要素の配置が可能となるか否かが試行されるのである。
【0041】
次に、この再配置試行部26の具体的な処理例について説明する。再配置試行部26は、再配置試行処理の対象となる図形要素(既配置の図形要素であって、環境線など移動不能なものを除く:以下、再配置対象図形要素と呼ぶ)の識別子の入力を受け入れる。そして入力を受け入れた識別子を、移動抑制リストから除去する。
【0042】
再配置試行部26は、図7に示すように、再配置対象図形要素を包含する代理図形を設定(例えば再配置対象図形要素に外接する外接矩形そのもの、または外接矩形を外側へ所定量だけ拡大して得る)し(S1)、代理図形の各辺をその両側へ所定量だけ延長する(S2)。また、各辺を延長して得た線分が他の図形要素に交差する場合は、その交差の点から外への延長部分を除去する(S3)。
【0043】
次に再配置試行部26は、各辺において、他の図形要素(例えば他の代理図形の線分)が交差する位置を点(以下、交差点という)として特定する(S4)。図7においては、再配置対象図形要素は、他の代理図形と、点A,Bで交差することを示している。また、図8に例示するように、再配置対象図形要素内に、他の図形要素を構成する線分の端点(当該他の図形要素が多角形であれば、その頂点)が含まれている場合、処理S4では、当該頂点から、当該他の図形要素との交差がある辺へ下した垂線の足(図8のC,D)をも交差点として特定する。
【0044】
他の図形要素との交差がある辺の両端の頂点から、各頂点より最も遠い位置にある交差点でも長さを求める(S5)。図7においては、頂点P,Qから交差点Aまでの距離、PA及びQAと、頂点Q,Rから交差点Bまでの距離、QB及びRBとを求める。また、図8においては、図8(b)に示すように、PC,QA,QB,RDをそれぞれ求めることになる。
【0045】
この処理S5で求めた長さが、移動量の候補となる。すなわち、再配置試行部26は、図7を例として説明すると、
【0046】
(1)辺PQに沿って、PからAの方向へ長さPAだけ移動した場合、
(2)辺PQに沿って、QからAの方向へ長さQAだけ移動した場合、
(3)辺QRに沿って、QからBの方向へ長さQBだけ移動した場合、
(4)辺QRに沿って、RからBの方向へ長さRBだけ移動した場合
【0047】
のそれぞれについて、再配置対象図形要素を移動したとき、他の図形要素との重なり合いが回避できるか否かを調べる。ここでは、(2)辺PQに沿って、QからAの方向へ長さQAだけ移動した場合、または(3)辺QRに沿って、QからBの方向へ長さQBだけ移動した場合のときに他の図形要素との交差を回避できることとなり、再配置試行部26は、例えば移動距離が最も短い選択肢として、(2)辺PQに沿って、QからAの方向へ長さQAだけ移動することとして、再配置対象図形要素の識別子と、上記移動後の配置位置を表す情報とを配置位置決定部24に出力し、また、再配置対象図形要素の識別子を移動抑制リストに追加して処理を終了する。
【0048】
このように、既に配置済みとなっている図形要素を移動することで、より多くの図形要素を配置する機会を増大できる。
【0049】
また、再配置試行部26は、どの選択肢においても他の図形要素との重なり合いが回避できない場合は、移動距離が最も短い選択肢の位置に、再配置対象図形要素を仮に移動して、再配置対象図形要素の識別子を移動抑制リストに追加する。そして、その移動先で重なり合っている他の図形要素の識別子を用いて、さらに再配置試行処理を実行する。つまり、再配置処理によっても、回避できない干渉(重なり合いなど)が発生すると判断される場合に、既に配置されている他の図形要素の再配置を試行する。
【0050】
また、図8においては、
(1)辺PQに沿って、PからAの方向へ長さPCだけ移動した場合、
(2)辺PQに沿って、QからAの方向へ長さQAだけ移動した場合、
(3)辺QRに沿って、QからBの方向へ長さQBだけ移動した場合、
(4)辺QRに沿って、RからBの方向へ長さRDだけ移動した場合
【0051】
のそれぞれについて、再配置対象図形要素を移動したとき、他の図形要素との重なり合いが回避できるか否かを調べることになる。
【0052】
[点を基準とした文字列の配置]
なお、ここまでの説明では、図形要素の配置の基準として面が指定された場合の処理について説明したが、これに限られない。例えば配置の基準として、点が指定された場合、次のように処理が行われる。
【0053】
まず補助線設定部21は、図9に例示するように、基準として指定された点(O)を端点として放射状に仮想の線分を複数設定する。なお、図9に示す例では、予め定められた角度ごと(図9では45度ごと)に、補助線を設定する例を述べているが、これに限られるものではない。
【0054】
補助線設定部21は、複数設定した補助線と、基準となる点または他の図形要素との交点を求め、基準点と交点または交点間の距離(交差区間長)を演算する。ここで交点が複数あるときには、互いに隣接する交点間の複数の距離を算出しておく。
【0055】
補助線設定部21は、設定した各補助線ごとに、最も長い交差区間長となっている交差区間(最長交差区間)と、その最長交差区間を挟む交点とを特定する。そして補助線設定部21は、予め定めた優先順位の順に補助線を選択する。補助線設定部21は、選択した補助線において、特定した最長交差区間の交差区間長が、配置の対象となる文字列に対応する代理図形(注目代理図形)の幅Lを越えているか否かを調べる。
【0056】
ここで、注目代理図形の幅Lを越えていれば、当該選択している補助線を候補補助線とする。補助線設定部21は、その候補補助線と、最長交差区間とを特定する情報(線分の端点の座標情報と交差区間の端点の座標情報と、など)を空間探索部22に出力する。
【0057】
なお、空間探索部22が、当該交差区間に代理図形を配置不能であった旨の情報を出力すると、補助線設定部21は、優先順位に従って次の補助線を選択し、選択した補助線において、特定した最長交差区間の交差区間長が、注目代理図形の幅Lを越えているか否かを調べる処理から繰り返して行う。
【0058】
ここで優先順位に従って次の補助線がない場合(すべての補助線において見出した最長交差区間内に代理図形を配置不能であったとき)は、補助線設定部21は優先順位が最上位となっている補助線を再度、候補補助線として、その候補補助線と、最長交差区間とを特定する情報と、次の補助線がないことを表す情報とを空間探索部22に出力する。
【0059】
ここに優先順位は、例えば図9に例示するように、指定された点の右方を順位「1」、左方を順位「2」…とするなど、見やすさを基準に予め定めておけばよい。図9では、優先順位を丸で囲んだ数字で表している。また図9では注目代理図形の配置例を、補助線に交差する破線の矩形で表している。
【0060】
空間探索部22は、注目代理図形を、その幅方向の辺が、候補補助線の交差区間に平行になるように配し、当該配したときの注目代理図形の外周が、他の図形要素に重なり合うか否かを調べる。ここで注目代理図形の外周が、他の図形要素に重なり合う場合は、調整部23が、上述したような注目代理図形配置調整処理を実行する。そして注目代理図形配置調整処理により、注目代理図形が配置できた場合は、そのときの注目代理図形の配置位置を特定する情報を配置位置決定部24に出力する。
【0061】
一方、注目代理図形配置調整処理によっても注目代理図形が配置できなかった場合は、空間探索部22が、交差区間に代理図形を配置不能であった旨の情報を出力する。
【0062】
なお、補助線設定部21が、次の補助線がないことを表す情報を出力している場合は、当該情報とともに出力された、候補補助線(最も優先順位の高い補助線)の最長の交差区間に沿って、注目代理図形を仮に配置し、再配置試行処理を開始する。このとき、空間探索部22は、固有の図形要素の識別子を発行して、この発行した識別子と、配置の対象となった文字列と、それに対応する注目代理図形の仮の配置位置を特定する情報とを関連づけて、記憶部12に格納する。また、注目代理図形の識別子を、移動抑制リストに追加して格納する。そして注目代理図形に重なり合う他の図形要素の識別子を、再配置試行部26に出力する。
【0063】
一方、空間探索部22は、現在の候補補助線上に配した注目代理図形の外周が、他の図形要素に重なり合わない場合は、そのときの注目代理図形の配置位置を特定する情報を配置位置決定部24に出力する。
【0064】
このように点を基準として配置位置を決定する場合、図10に例示するように、既配置の図形要素P1,P2の隙間を縫って文字列(を囲む代理図形X)を配置できる可能性が向上する。
【0065】
なお、線分を基準とする場合は、例えば当該線分の中点を端点として、線分に平行な方向から所定角度ごと、または任意角度に放射状に補助線を設定し、上述の、点を基準とする場合と同様の処理を行えばよい。
【0066】
次に、本実施の形態の装置の動作例について図11を参照しつつ説明する。本実施の形態の図形要素配置装置は、配置の対象となる文字列などが入力され、その配置の基準となる面や、点、線分などの指定を受けて、図11に示す処理を開始する。
【0067】
そして、まず基準として指定された点、線分、面などに基づいて、少なくとも一つの補助線を設定する(S11)。そして補助線上で他の図形要素との交差点を見出し、交差点間の距離(交差区間長)を算出して、配置の対象となる図形要素を配置可能な交差区間があるか否かを調べる(S12)。ここで、配置可能な交差区間がなければ(Noならば)、配置ができなかったことを報知して(S13)、処理を終了する。
【0068】
一方処理S12において、配置の対象となる図形要素を配置可能な交差区間があれば(Yesならば)、配置の対象となる図形要素を当該交差区間に沿って配置し、他の図形要素との間で干渉なく配置が可能であるか否かを調べる(S14)。ここで、配置が可能であれば(Yesならば)、その配置位置を配置の対象となった図形要素(文字列であればその文字列を含む)とともに記録して(S15)、処理を終了する。
【0069】
さらに処理S14において、他の図形要素との間で干渉なしに配置ができなかったときには、補助線に沿って対象となる図形要素を移動して(その例が、上述の注目代理図形配置調整処理:S16)、干渉を回避して配置できるか否かを調べる(S17)。ここで配置ができたならば(Yesならば)、処理S15に移行する。
【0070】
また、処理S17において配置ができなければ(Noならば)、再配置の処理を開始して、干渉している他の図形要素が移動可能であるときには、他の図形要素の配置位置を調整して(S18)、再配置できたか否かを調べる(S19)。ここで配置ができたならば(Yesならば)、処理S15に移行する(A)。
【0071】
一方、処理S19において再配置できなかった場合や、干渉している他の図形要素が移動不能なものであれば、この図11の処理を開始する前の配置(当該配置位置については予め記憶部12内に複写を作成しておき、ここでは作成した複写に基づいて元へ戻せばよい)に戻し(S20)、配置ができなかったことを報知して(S21)、処理を終了する。
【0072】
本実施の形態によると、対象となる図形要素や既に配置されている図形要素の配置位置の調整が行われるので、より多くの図形要素を、干渉を避けつつ配置できる。
【0073】
なお、ここまでの説明で、注目代理図形配置調整処理は、対象となる図形を補助線に平行に移動するものとしたが、図7等で示した再配置試行の処理と同様に、補助線と垂直な方向へも、移動することで干渉が回避可能であるか否かを判断してもよい。
【図面の簡単な説明】
【0074】
【図1】本発明の実施の形態に係る図形要素配置装置の例を表す構成ブロック図である。
【図2】本発明の実施の形態に係る図形要素配置装置が規定する代理図形の例を表す説明図である。
【図3】本発明の実施の形態に係る図形要素配置装置の例を表す機能ブロック図である。
【図4】本発明の実施の形態に係る図形要素配置装置において設定される補助線の例を表す説明図である。
【図5】本発明の実施の形態に係る図形要素配置装置が保持する図形要素の情報例を表す説明図である。
【図6】本発明の実施の形態に係る図形要素配置装置における配置位置の調整処理例を表す説明図である。
【図7】本発明の実施の形態に係る図形要素配置装置における再配置試行の処理例を表す説明図である。
【図8】本発明の実施の形態に係る図形要素配置装置における再配置試行の処理の別の例を表す説明図である。
【図9】本発明の実施の形態に係る図形要素配置装置において点を基準として代理図形を配する例を表す説明図である。
【図10】本発明の実施の形態に係る図形要素配置装置において点を基準として代理図形を配するときの効果の例を表す説明図である。
【図11】本発明の実施の形態に係る図形要素配置装置での処理例を表すフローチャート図である。
【符号の説明】
【0075】
11 制御部、12 記憶部、13 操作部、14 出力部、21 補助線設定部、22 空間探索部、23 調整部、24 配置位置決定部、25 描画部、26 再配置試行部。
【特許請求の範囲】
【請求項1】
複数の図形要素を配置する図形要素配置装置であって、
所定の条件の下で、過去に配置された他の図形要素と干渉せずに、対象となる図形要素の配置領域を探索し、前記対象となる図形要素が、他の図形要素と干渉せずに配置できた場合に、その配置位置を決定する配置領域探索手段と、
前記対象となる図形要素が、他の図形要素と干渉せずに配置できない場合に、前記過去に配置された他の図形要素の再配置を試行する再配置試行手段と、
を含むことを特徴とする図形要素配置装置。
【請求項2】
請求項1記載の図形要素配置装置であって、
前記配置領域探索手段は、
所定の条件の下で、対象となる図形要素の配置領域を探索し、
前記探索によって見出された配置領域が他の図形要素と干渉するか否かを判断し、
前記探索によって見出された配置領域が他の図形要素と干渉しない場合は、当該見出した配置領域に対象となる図形要素を配置し、
前記判断により干渉すると判断される場合に、前記見出された配置領域の近傍に他の図形要素に干渉せずに前記対象となる図形要素を配置可能な配置領域があれば、当該配置領域に対象となる図形要素を配置することを特徴とする図形要素配置装置。
【請求項3】
請求項2記載の図形要素配置装置であって、
前記再配置試行手段は、
前記判断により干渉すると判断される場合に、前記見出された配置領域の近傍に他の図形要素に干渉せずに前記対象となる図形要素を配置可能な配置領域がない場合に、前記過去に配置された他の図形要素の再配置を試行することを特徴とする図形要素配置装置。
【請求項4】
請求項1から3のいずれか一項に記載の図形要素配置装置であって、
前記所定の条件は、指定された座標の点から予め定められた角度方向に仮想的に描画された線分に配置領域が重なり合う条件であることを特徴とする図形要素配置装置。
【請求項5】
コンピュータに、複数の図形要素を配置させるプログラムであって、
所定の条件の下で、過去に配置された他の図形要素と干渉せずに、対象となる図形要素の配置領域を探索し、前記対象となる図形要素が、他の図形要素と干渉せずに配置できた場合に、その配置位置を決定する配置領域探索手段と、
前記対象となる図形要素が、他の図形要素と干渉せずに配置できない場合に、前記過去に配置された他の図形要素の再配置を試行する再配置試行手段と、
として、コンピュータを機能させることを特徴とするプログラム。
【請求項1】
複数の図形要素を配置する図形要素配置装置であって、
所定の条件の下で、過去に配置された他の図形要素と干渉せずに、対象となる図形要素の配置領域を探索し、前記対象となる図形要素が、他の図形要素と干渉せずに配置できた場合に、その配置位置を決定する配置領域探索手段と、
前記対象となる図形要素が、他の図形要素と干渉せずに配置できない場合に、前記過去に配置された他の図形要素の再配置を試行する再配置試行手段と、
を含むことを特徴とする図形要素配置装置。
【請求項2】
請求項1記載の図形要素配置装置であって、
前記配置領域探索手段は、
所定の条件の下で、対象となる図形要素の配置領域を探索し、
前記探索によって見出された配置領域が他の図形要素と干渉するか否かを判断し、
前記探索によって見出された配置領域が他の図形要素と干渉しない場合は、当該見出した配置領域に対象となる図形要素を配置し、
前記判断により干渉すると判断される場合に、前記見出された配置領域の近傍に他の図形要素に干渉せずに前記対象となる図形要素を配置可能な配置領域があれば、当該配置領域に対象となる図形要素を配置することを特徴とする図形要素配置装置。
【請求項3】
請求項2記載の図形要素配置装置であって、
前記再配置試行手段は、
前記判断により干渉すると判断される場合に、前記見出された配置領域の近傍に他の図形要素に干渉せずに前記対象となる図形要素を配置可能な配置領域がない場合に、前記過去に配置された他の図形要素の再配置を試行することを特徴とする図形要素配置装置。
【請求項4】
請求項1から3のいずれか一項に記載の図形要素配置装置であって、
前記所定の条件は、指定された座標の点から予め定められた角度方向に仮想的に描画された線分に配置領域が重なり合う条件であることを特徴とする図形要素配置装置。
【請求項5】
コンピュータに、複数の図形要素を配置させるプログラムであって、
所定の条件の下で、過去に配置された他の図形要素と干渉せずに、対象となる図形要素の配置領域を探索し、前記対象となる図形要素が、他の図形要素と干渉せずに配置できた場合に、その配置位置を決定する配置領域探索手段と、
前記対象となる図形要素が、他の図形要素と干渉せずに配置できない場合に、前記過去に配置された他の図形要素の再配置を試行する再配置試行手段と、
として、コンピュータを機能させることを特徴とするプログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【公開番号】特開2009−157574(P2009−157574A)
【公開日】平成21年7月16日(2009.7.16)
【国際特許分類】
【出願番号】特願2007−334075(P2007−334075)
【出願日】平成19年12月26日(2007.12.26)
【出願人】(000135771)株式会社パスコ (102)
【Fターム(参考)】
【公開日】平成21年7月16日(2009.7.16)
【国際特許分類】
【出願日】平成19年12月26日(2007.12.26)
【出願人】(000135771)株式会社パスコ (102)
【Fターム(参考)】
[ Back to top ]