(57)【要約】【課題】線分データを組み合わせて多角形を生成する際の処理時間を短縮することができるようにする。【解決手段】複数の線分データから構成される印刷データを受信する受信部と、前記複数の線分データが任意の形状を塗り潰（つぶ）す構成を備えるか否かを判断する塗り潰し判断部と、前記複数の線分データが任意の形状を塗り潰す構成を備えると判断された場合、前記複数の線分データによって構成される形状を検出する形状検出部と、前記複数の線分データを検出された前記形状の塗り潰しデータとして処理するデータ処理部とを有する。【選択図】図１
2005275638.tif 000002
【特許請求の範囲】
【請求項１】
（ａ）複数の線分データから構成される印刷データを受信する受信部と、
（ｂ）前記複数の線分データが任意の形状を塗り潰す構成を備えるか否かを判断する塗り潰し判断部と、
（ｃ）前記複数の線分データが任意の形状を塗り潰す構成を備えると判断された場合、前記複数の線分データによって構成される形状を検出する形状検出部と、
（ｄ）前記複数の線分データを検出された前記形状の塗り潰しデータとして処理するデータ処理部とを有することを特徴とする画像処理装置。
【請求項２】
電子写真記録装置である請求項１に記載の画像処理装置。
【請求項３】
前記印刷データは、ペンプロッタ用の印刷制御情報から構成される請求項１に記載の画像処理装置。
【請求項４】
前記塗り潰し判断部は、第１線分データと第２線分データとの距離が所定のペン幅より狭い場合、前記第１線分データ及び第２線分データが任意の形状を塗り潰す構成を備えると判断する請求項１に記載の画像処理装置。
【請求項５】
前記形状検出部は、少なくとも第１線分データと第Ｎ線分データとの座標値に基づき前記形状を検出する請求項１に記載の画像処理装置。
【請求項６】
前記データ処理部は、前記形状内を塗り潰すように画像を形成する請求項１に記載の画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置に関するものである。
【背景技術】
【０００２】
従来、ペンプロッタ等のようにペンを用いて図形を描画する画像処理装置においては、文字や図形、又は、直線や曲線を描画する際、それらの形状や大きさを確定することができるような情報を組み合わせて描画形状を生成するようになっている（例えば、特許文献１参照。）。例えば、直線を生成する場合は、直線を構成する端点の位置を示す座標、直線の幅等の情報によって直線を確定するようになっている。また、曲線を生成する場合は、該曲線を線分近似して直線を生成する場合と同じような情報によって曲線を確定したり、ベジエ曲線のように湾曲度合いを表す情報によって曲線を確定したりする。このような情報は、図形を確定するために必要な情報の一例であり、その表し方には複数ある。
【０００３】
図２は従来の多角形を確定する輪郭情報を示す図、図３は従来の多角形を生成する動作の例を示す第１の図、図４は従来の多角形を生成する動作の例を示す第２の図である。
【０００４】
例えば、多角形を生成する場合、図２に示されるように、多角形の輪郭情報として頂点である点Ｐ１（ｐｘ１，ｐｙ１）、点Ｐ２（ｐｘ２，ｐｙ２）、点Ｐ３（ｐｘ３，ｐｙ３）及び点Ｐ４（ｐｘ４，ｐｙ４）の座標を使用することによって多角形が確定される。
【０００５】
また、図３及び４に示されるように、線分情報を組み合わせて最終的に多角形を生成することもできる。図３は、多角形の端から、一筆書きのように線分情報を組み合わせる例であり、図４は多角形の端から同じ向きの線分を複数本組み合わせる例である。このように、線分情報を組み合わせて最終的に多角形を生成する方法は、描画する手段がペンプロッタなどのようにペンを用いて行うものである場合、特に有効である。また、線分情報を組み合わせて最終的に多角形も生成することができるようにすると、図形を確定するために必要な情報の種類が少なくて済み、単一的な処理で画像処理を行うことができるという長所がある。
【特許文献１】特開平８−３００８８５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、前記従来の画像処理装置において多角形を生成する方法は、線分情報を組み合わせて最終的に多角形を生成しようとすると、図形を確定するために必要な情報の種類が少なくて済み、単一的な処理で図形処理を行うことができるという長所があるが、電子写真プリンタで描画を行う場合、生成しようとする面積に対して、処理時間が長くなってしまう。特に、面積の広い多角形を描画しようとするときに、線幅が細い線で線分に沿って塗り潰（つぶ）していこうとすると、処理時間が極めて長くなってしまう。
【０００７】
図５は従来の線に幅を付けて多角形を生成する動作の例を示す図である。
【０００８】
図５（ａ）は、図３に示される多角形の一部を拡大したものであり、前記多角形を塗り潰す場合、多角形の左上端から線分Ｑ１Ｑ２、線分Ｑ２Ｑ３、線分Ｑ３Ｑ４、線分Ｑ４Ｑ５・・・の順で塗り潰すようになっている。そして、前記線分のそれぞれについて幅付け処理を行って多角形を塗り潰すと、図５（ｂ）に示されるようになる。この場合、線分Ｑ１Ｑ２に対して四角形Ｑ１１Ｑ１２Ｑ１３Ｑ１４、線分Ｑ２Ｑ３に対して四角形Ｑ２１Ｑ２２Ｑ２３Ｑ２４、線分Ｑ３Ｑ４に対して四角形Ｑ３１Ｑ３２Ｑ３３Ｑ３４・・・となるように、一本の線分毎に幅付け処理を行って展開する。なお、線幅が上下方向に隣接する線分の間隔よりも広くなるように設定される。
【０００９】
また、線分の端点や接続点を修飾して、丸めたり、尖（とが）らせたり、角を付けたりすることもできる。この場合、前記四角形Ｑ１１Ｑ１２Ｑ１３Ｑ１４、四角形Ｑ２１Ｑ２２Ｑ２３Ｑ２４、四角形Ｑ３１Ｑ３２Ｑ３３Ｑ３４等の外に、図５（ｃ）に示される図ＣやＤのような修飾のための図形を算出して展開するようになっている。このように、多角形を線幅が細い線で線分に沿って塗り潰す場合には、多くの処理を行う必要があるので、処理時間が極めて長くなってしまう。
【００１０】
本発明は、前記従来の問題点を解決して、線分データを組み合わせて多角形を生成する際の処理時間を短縮することができる画像処理装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
そのために、本発明の画像処理装置においては、複数の線分データから構成される印刷データを受信する受信部と、前記複数の線分データが任意の形状を塗り潰す構成を備えるか否かを判断する塗り潰し判断部と、前記複数の線分データが任意の形状を塗り潰す構成を備えると判断された場合、前記複数の線分データによって構成される形状を検出する形状検出部と、前記複数の線分データを検出された前記形状の塗り潰しデータとして処理するデータ処理部とを有する。
【発明の効果】
【００１２】
本発明によれば、画像処理装置においては、線分データを組み合わせて多角形を生成する際の処理時間を短縮することができる。
【発明を実施するための最良の形態】
【００１３】
以下、本発明の実施の形態について図面を参照しながら詳細に説明する。
【００１４】
図１は本発明の第１の実施の形態における図形処理装置の構成を示すブロック図である。
【００１５】
図において、１０は画像処理装置としての図形処理装置であり、例えば、コンピュータ等の情報処理装置に接続されたＣＲＴ、液晶ディスプレイ等の表示装置、ペンプロッタ、電子写真記録装置等の画像形成装置等において、図形の中塗り、塗り潰し、その他の図形処理を行うために使用される装置である。そして、前記図形処理装置１０は、ＣＰＵ、ＭＰＵ等の演算手段、半導体メモリ、磁気ディスク等の記憶手段、通信インターフェイス等を備える一種のコンピュータであるが、独立して構成されたものであってもよいし、情報処理装置、画像形成装置等と一体的に構成されたものであってもよいし、情報処理装置、画像形成装置等の中に構築された複数のシステムの中の一つであってもよい。
【００１６】
本実施の形態において、前記図形処理装置１０は、図に示されるような構成を有する。ここで、１１は入力された複数本の線分データとしての線分情報２３を必要に応じて多角形データとして扱うように加工する線分情報加工部である。該線分情報加工部１１は、入力された線分情報２３の一連の点の位置関係を解析する線分位置解析部１２と、該線分位置解析部１２において解析した点の位置関係によって、入力された複数本の線分をすべて描画した際の描画結果を予想し、それが一つの平行な水平線又は平行な垂直線を含む台形と成り得るかどうかを判断する台形判定部１３と、該台形判定部１３において一つの平行な水平線又は平行な垂直線を含む台形と成り得ると判断された場合は線分情報２３を一つの台形情報に変換する台形データ加工部１４とを有する。
【００１７】
また、２１は前記線分情報加工部１１において入力された複数本の線分情報２３が加工されなかったときに処理を行う線分描画処理部、２２は前記線分情報加工部１１において入力された複数本の線分情報２３が加工されたときに処理を行う多角形描画処理部である。なお、２４は線分の端点、接続点等を修飾するための線分修飾情報である。
【００１８】
そして、前記図形処理装置１０は、機能の観点から、線分情報２３から構成される印刷データを受信する受信部、線分情報２３が任意の形状を塗り潰す構成を備えるか否かを判断する塗り潰し判断部、線分情報２３が任意の形状を塗り潰す構成を備えると判断された場合、線分情報２３によって構成される形状を検出する形状検出部、及び、線分情報２３を検出された形状の塗り潰しデータとして処理するデータ処理部を有する。この場合、前記線分情報加工部１１は、受信部、塗り潰し判断部及び形状検出部に該当し、前記多角形描画処理部２２はデータ処理部に該当する。
【００１９】
次に、前記構成の図形処理装置１０の動作について説明する。なお、図形描画に関し、動作が分かりやすいように、「背景技術」における図２〜４を参照して説明する。
【００２０】
図６は本発明の第１の実施の形態における多角形情報を示す第１の図、図７は本発明の第１の実施の形態における多角形情報を示す第２の図、図８は本発明の第１の実施の形態における多角形情報を示す第３の図、図９は本発明の第１の実施の形態における多角形情報を示す第４の図、図１０は本発明の第１の実施の形態における多角形を確定する輪郭情報を示す第１の図、図１１は本発明の第１の実施の形態における多角形を生成する動作の例を示す第１の図、図１２は本発明の第１の実施の形態における多角形を確定する輪郭情報を示す第２の図、図１３は本発明の第１の実施の形態における多角形を生成する動作の例を示す第２の図、図１４は本発明の第１の実施の形態における図形処理装置の動作を示すフローチャート、図２８は本発明の第１の実施の形態における多角形情報を示す第５の図である。
【００２１】
ここでは、図２に示されるような多角形Ｐ１Ｐ２Ｐ３Ｐ４を描画する場合の動作について説明する。まず、線分情報２３が線分情報加工部１１に入力される。なお、前記線分情報２３は印刷データを構成するものである。この場合、前記線分情報２３は、図３に示されるように、線分の集合が頂点Ｑ１、Ｑ２、Ｑ３・・・Ｑｎ−１、Ｑｎの順で、例えば、図６に示されるような形式で入力される。そして、前記線分情報加工部１１は、まず、入力された線分情報２３のうち、一本目の線分の線分情報２３を取り出す。該一本目の線分の線分情報２３とは、前記線分の両端点の座標情報であり、図３における点Ｑ１（ｑｘ１，ｑｙ１）及び点Ｑ２（ｑｘ２，ｑｙ２）の座標情報である。そして、入力された線分情報２３の数を図６に示される頂点数を参照して判断し、線分情報２３の数によって線分終了であるか否かを判断する。ここで、前記線分情報２３の数が二点のみの場合は、一線分しかなく、多角形ではないので、わざわざ多角形の情報に持ち替える必要はないため、線分終了であると判断する。そして、線分描画処理部２１が、そのまま、線分描画処理を行い、図形処理装置１０は処理を終了する。
【００２２】
また、前記線分情報加工部１１は、線分情報２３の数が二線分以上ある場合、線分終了でないと判断して、図２８に示されるような形式で、多角形情報を作成する。この場合、図２８に示されるように、頂点数４と初めの線分の両端点として点Ｑ１及び点Ｑ２の座標（ｑｘ１，ｑｙ１）及び（ｑｘ２，ｑｙ２）を記憶エリアに格納して、入力線分の頂点数から処理頂点二頂点分を減らし、頂点数を更新する。
【００２３】
続いて、前記線分情報加工部１１は、次の線分の線分情報２３としての両端点である点Ｑ３及びＱ４を取り出す。図３に示されるような線分の線分情報２３が入力されたときは、点Ｑ３と点Ｑ２及び点Ｑ４と点Ｑ１のＸ座標がそれぞれ等しいか否かを判断する。すなわち、本線分（次の線分）と前線分（初めの線分）との両端の位置関係が、矩（く）形の形成が可能なものであるか否かを判断する。ここで、どちらか一方でもＸ座標が異なる場合、矩形とは成り得ないため、線分描画処理部２１が、そのまま、線分描画処理を行い、図形処理装置１０は処理を終了する。
【００２４】
また、前記線分情報加工部１１は、本線分の両端である点Ｑ４と点Ｑ３のＸ座標が、前線分の両端である点Ｑ１と点Ｑ２のＸ座標と同じ場合、矩形の形成が可能であると判断し、本線分と前線分との両端点の距離を算出する。点Ｑ３と点Ｑ２との距離Δｙ３は、次の式（１）によって算出することができる。
距離Δｙ３＝（ｑｙ３−ｑｙ２）  ・・・式（１）
また、点Ｑ４と点Ｑ１との距離Δｙ４は、次の式（２）によって算出することができる。
距離Δｙ４＝（ｑｙ４−ｑｙｌ）  ・・・式（２）
ここで、前記線分情報加工部１１は、距離Δｙ３又は距離Δｙ４のどちらか一方でもペン幅（描画される線一本の幅）より大きくないか否かを判断する。すなわち、本線分と前線分との距離がペン幅以下か否かを判断する。そして、距離Δｙ３又は距離Δｙ４のどちらか一方でもペン幅より大きい場合、すなわち、本線分と前線分との距離がペン幅以下でない場合、多角形描画に変更すると線分描画とは描画結果に相違が出るため、線分描画処理部２１が、そのまま、線分描画処理を行い、図形処理装置１０は処理を終了する。
【００２５】
また、距離Δｙ３及び距離Δｙ４がともにペン幅より小さい場合、すなわち、本線分と前線分との距離がペン幅以下である場合は、線分描画を多角形描画に変更しても描画結果に違いは出ない。そのため、処理時間の短い多角形描画用に、本線分の両端点として点Ｑ３及び点Ｑ４の座標（ｑｘ３，ｑｙ３）及び（ｑｘ４，ｑｙ４）を図８に示されるような形式で記憶エリアに格納する。
【００２６】
次に、前記線分情報加工部１１は、入力線分の頂点数から処理頂点二頂点分を減らし、、頂点数を更新する。そして、未処理の頂点があるか否か、すなわち、すべての線分が終了したか否かを判断する。ここで、未処理の頂点がある場合には、すべての線分が終了していないので、再び、次の線分の両端点を取り出す。この場合、次の線分の両端点である点Ｑ５及びＱ６を取り出す。そして、点Ｑ５と点Ｑ４及び点Ｑ６と点Ｑ３のＸ座標を判断し、線分Ｑ３Ｑ４のときと同様の処理を行い、図形として頂点座標を格納する場合は図９に示されるような形式で、点Ｑ５及び点Ｑ６の座標（ｑＸ５，ｑｙ５）及び（ｑｘ６，ｑｙ６）を記憶エリアに格納する。以降、すべての頂点について、処理し終わるまで前述された動作を繰り返す。
【００２７】
また、未処理の頂点がなく、すべての線分が終了した場合、前記線分情報加工部１１は、すべての頂点に対し処理が終わったと判断する。この場合、多角形情報は図７に示されるようになっている。そして、多角形描画処理部２２は、前記多角形情報を用いて多角形描画処理を行い、図形処理装置１０は処理を終了する。
【００２８】
なお、本実施の形態においては、図３に示される矩形を用いて図形処理装置１０の動作を説明したが、入力される各線分は、前述されたように、矩形を形成することができ、本線分と前線分との両端点の距離がペン幅以下であれば、平行でなくても良い。そのため、結果的に、例えば、図１０に示されるような台形を形成する情報であっても、本実施の形態における図形処理装置１０の動作は問題なく行われ、同様の効果を得ることができる。
【００２９】
さらに、本実施の形態においては、各頂点の位置関係を判断する条件としてＸ座標を用いたが、もちろんＹ座標を条件として用いることも可能である。この場合、図１１に示されるような入力が考えられ、例えば、図１２に示されるような台形においても同様の効果を得ることができる。
【００３０】
また、本実施の形態においては、入力されるデータを図３に示される順で処理する場合について説明したが、本線分と前線分との両端の位置関係を判断したり、本線分と前線分との両端点の距離がペン幅以下であるか否かを判断するときの比較の対象と、本線分の両端点の座標を格納するときの格納場所とを変更したりすれば、例えば、図４に示される順でデータが入力されても同様の動作を行うことができる。もちろん、座標の入力順は図１３に示されるようになっていてもよい。また、この場合も図１０及び１２に示されるような台形にも応用することができ、同様の効果を得ることができる。
【００３１】
また、本実施の形態においては、入力データのうち１線分でも多角形描画の条件を満たさない線分がある場合、入力データすべてを線分描画処理したが、入力データに多角形描画の条件を満たす部分と満たさない部分が混在するときは、多角形描画の条件を満たす部分毎に多角形描画処理を行うようにしてももちろんよく、効果を得ることができる。このとき、入力データの特性により、多角形描画の条件を満たす線分の本数に閾（しきい）値を設け、例えば、“２本以上の線分が連続して多角形描画の条件を満たしたら多角形描画処理を行う”とすると、より活用度も広く効果的に図形処理を行える。
【００３２】
次に、フローチャートについて説明する。
ステップＳ１  線分情報２３を入力する。
ステップＳ２  一本目の線分を取り出す。
ステップＳ３  線分終了であるか否かを判断する。線分終了である場合はステップＳ４に進み、線分終了でない場合はステップＳ５に進む。
ステップＳ４  線分描画処理を行い、処理を終了する。
ステップＳ５  一本目の線分の両端点を格納し、線分の頂点数を更新する。
ステップＳ６  次の線分を取り出す。
ステップＳ７  本線分と前線分との両端の位置関係は矩形の形成が可能なものであるか否かを判断する。本線分と前線分との両端の位置関係は矩形の形成が可能なものである場合はステップＳ９に進み、本線分と前線分との両端の位置関係は矩形の形成が不可である場合はステップＳ８に進む。
ステップＳ８  線分描画処理を行い、処理を終了する。
ステップＳ９  本線分と前線分との距離はペン幅以下であるか否かを判断する。本線分と前線分との距離はペン幅以下である場合はステップＳ１１に進み、本線分と前線分との距離はペン幅以下でない場合はステップＳ１０に進む。
ステップＳ１０  線分描画処理を行い、処理を終了する。
ステップＳ１１  本線分の両端点を格納する。
ステップＳ１２  線分の頂点数を更新し線分が終了したか否かを判断する。線分の頂点数を更新し線分が終了した場合はステップＳ１３に進み、線分の頂点数を更新し線分が終了しない場合はステップＳ６に戻る。
ステップＳ１３  多角形描画処理を行い、処理を終了する。
【００３３】
このように、本実施の形態においては、複数本の線分の描画に際し、隣接する各線分の距離が、それぞれ、ペン幅よりも小さいか否かを判断し、隣接する各線分の距離が、それぞれ、ペン幅よりも小さい場合は線分として処理を行わず、これを一つの台形又は矩形として処理を行うようになっている。これにより、従来複数回行う必要があった描画処理を一回の描画処理で済ませることができるため処理時間を大幅に軽減することができる。また、入力された線分の本数が多ければ多いほど、その軽減率は大きくなり、描画処理の高速化がより顕著になる。
【００３４】
次に、本発明の第２の実施の形態について説明する。なお、第１の実施の形態と同じ構造を有するものについては、同じ符号を付与することによってその説明を省略する。また、第１の実施の形態と同じ動作及び効果についてもその説明を省略する。
【００３５】
図１５は本発明の第２の実施の形態における図形処理装置の構成を示すブロック図である。
【００３６】
本実施の形態においては、線分情報加工部１１は、前記第１の実施の形態の図１に示される台形判定部１３及び台形データ加工部１４に代わり、図１５に示されるように、四角形判定部１５及び四角形データ加工部１６を有する。前記四角形判定部１５は前記線分位置解析部１２において解析した点の位置関係によって、入力された複数本の線分をすべて描画した際の描画結果を予想し、それが一つの任意の四角形又は任意の三角形と成り得るかどうかを判断する。また、前記四角形データ加工部１６は前記四角形判定部１５において一つの任意の四角形又は任意の三角形と成り得ると判断された場合は線分情報２３を一つの四角形情報に変換する。また、他の構成については、前記第１の実施の形態と同様であるので説明を省略する。
【００３７】
次に、本実施の形態における図形処理装置１０の動作について説明する。
【００３８】
図１６は本発明の第２の実施の形態における多角形を確定する輪郭情報を示す図、図１７は本発明の第２の実施の形態における多角形を生成する動作の例を示す第１の図、図１８は本発明の第２の実施の形態における多角形を生成する動作の例を示す第２の図、図１９は本発明の第２の実施の形態における図形処理装置の動作を示すフローチャートである。
【００３９】
本実施の形態においては、図１６に示されるような多角形Ｐ１Ｐ２Ｐ３Ｐ４を描画する場合の動作について説明する。まず、線分情報２３が線分情報加工部１１に入力される。この場合、前記線分情報２３は、図１７に示されるように、線分の集合が頂点Ｑ１、Ｑ２、Ｑ３・・・Ｑｎ−１、Ｑｎの順で、例えば、図６に示されるような形式で入力される。そして、前記線分情報加工部１１は、まず、入力された線分情報２３のうち、一本目の線分の線分情報２３を取り出す。該一本目の線分の線分情報２３とは図１７における点Ｑ１（ｑｘ１，ｑｙ１）及び点Ｑ２（ｑｘ２，ｑｙ２）の座標情報である。そして、入力された線分情報２３の数を図６に示される頂点数で判断し、線分情報２３の数によって線分終了であるか否かを判断する。ここで、前記線分情報２３の数が二点のみの場合は、一線分しかなく、多角形ではないので、わざわざ多角形の情報に持ち替える必要はないため、線分終了であると判断する。そして、線分描画処理部２１が、そのまま、線分描画処理を行い、図形処理装置１０は処理を終了する。
【００４０】
また、前記線分情報加工部１１は、線分情報２３の数が二線分以上ある場合、線分終了でないと判断して、図２８に示されるような形式で、図形情報としての多角形情報を作成する。この場合、図２８に示されるように、頂点数４と初めの線分の両端点として点Ｑ１及び点Ｑ２の座標（ｑｘ１，ｑｙ１）及び（ｑｘ２，ｑｙ２）を記憶エリアに格納して、入力線分の頂点数から処理頂点二頂点分を減らし、頂点数を更新する。
【００４１】
続いて、前記線分情報加工部１１は、後述されるように線分の位置関係を判断するときに必要となる位置関係基準情報を算出する。該位置関係基準情報は、最初の線分と最後の線分の情報から算出される。図１７に示される例において、前記位置関係基準情報は、線分Ｑ１Ｑｎ−１及び線分Ｑ２Ｑｎの情報であり、それぞれ、次の式（３）及び式（４）によって算出される。なお、算出された算出値は、記憶エリアに格納されて保持される。
線分Ｑ１Ｑｎ−１の情報：Ａ１＝（ｑｙn-1 −ｑｙ１）÷（ｑｘn-1 −ｑｘ１）、Ｂ１＝ｑｙ１−Ａ１×ｑｘ１  ・・・式（３）
線分Ｑ２Ｑｎの情報：Ａ２＝（ｑｙn −ｑｙ２）÷（ｑｘn −ｑｘ２）、Ｂ２＝ｑｙ２−Ａ２×ｑｘ２  ・・・式（４）
続いて、前記線分情報加工部１１は、次の線分の両端点である点Ｑ３及びＱ４を取り出す。図１７に示されるような線分の線分情報２３が入力されたときは、点Ｑ３が基準線分Ｑ２Ｑｎ上に、点Ｑ４が基準線分Ｑ１Ｑｎ−１上にあるか否かを判断する。すなわち、本線分（次の線分）と前線分（初めの線分）との両端の位置関係が、四角形の形成が可能なものであるか否かを判断する。ここで、どちらか一方でも基準線分上にない場合は、四角形とは成り得ないため、線分描画処理部２１が、そのまま、線分描画処理を行い、図形処理装置１０は処理を終了する。ここで、線分の端点と基準線分との位置は、前記端点が端点Ｑ３である場合、次の式（５）を満たせば端点Ｑ３が基準線分Ｑ２Ｑｎ上にあると判断することができる。
ｑｙ３＝Ａ２×ｑｘ３＋Ｂ２  ・・・式（５）
また、前記線分情報加工部１１は、本線分の両端の頂点座標が、それぞれ、基準線分上にある場合、四角形の形成が可能であると判断し、本線分と前線分との両端点の距離を算出する。一般に、点（ｘ０，ｙ０）と直線ａｘ＋ｂｙ＋ｃ＝０との距離Δは次の式（６）によって算出することができる。
距離Δ＝｜ａ・ｘ０＋ｂ・ｙ０＋ｃ｜÷√（ａ2 ＋ｂ2 ）  ・・・式（６）
そこで、前記線分情報加工部１１は、端点Ｑ３と線分Ｑ１Ｑ２との距離Δｑ３を、前記式（６）を用いて算出する。なお、線分Ｑ１Ｑ２の直線は次の式（７）によって表すことができる。
（ｑｙ２−ｑｙ１）・ｘ＋（ｑｘ１−ｑｘ２）・ｙ十Ｃ＝０  ・・・式（７）
ここで、Ｃ＝（ｑｘ２−ｑｘ１）・ｑｙ１−（ｑｙ２−ｑｙ１）・ｑｘ１である。
【００４２】
そして、端点Ｑ３の座標を（ｑｘ３，ｑｙ３）とすると、点Ｑ３と直線Ｑ１Ｑ２の距離Δｑ３は、次の式（８）によって表すことができる。
Δｑ３＝｜（ｑｙ２−ｑｙ１）・ｑｘ３＋（ｑｘ１−ｑｘ２）・ｑｙ３
＋Ｃ｜÷√｛（ｑｙ２−ｑｙ１）2 ＋（ｑｘ１−ｑｘ２）2 ｝  ・・・式（８）
ここで、Ｃ＝（ｑｘ２−ｑｘ１）・ｑｙｌ−（ｑｙ２−ｑｙ１）・ｑｘ１である。
【００４３】
続いて、前記線分情報加工部１１は、同様にして、点Ｑ４と直線Ｑ１Ｑ２との距離Δｑ４を算出する。そして、前記線分情報加工部１１は、距離Δｔ３又は距離Δｔ４のどちらか一方でもペン幅より大きくないか否かを判断する。ここで、距離Δｑ３又は距離Δｑ４のどちらか一方でもペン幅より大きい場合、すなわち、本線分と前線分との距離がペン幅以下でない場合、多角形描画に変更すると線分描画とは描画結果に相違が出るため、線分描画処理部２１が、そのまま、線分描画処理を行い、図形処理装置１０は処理を終了する。
【００４４】
また、距離Δｑ３及び距離Δｑ４がともにペン幅より小さい場合、すなわち、本線分と前線分との距離がペン幅以下である場合は、線分描画を多角形描画に変更しても描画結果に違いは出ない。そのため、処理時間の短い多角形描画用に、本線分の両端点として点Ｑ３及び点Ｑ４の座標（ｑｘ３，ｑｙ３）及び（ｑｘ４，ｑｙ４）を図８に示されるような形式で記憶エリアに格納する。
【００４５】
次に、前記線分情報加工部１１は、入力線分の頂点数から処理頂点二頂点分を減らし、、頂点数を更新する。そして、未処理の頂点があるか否か、すなわち、すべての線分が終了したか否かを判断する。ここで、未処理の頂点がある場合には、すべての線分が終了していないので、再び、次の線分の両端点を取り出す。この場合、次の線分の両端点である点Ｑ５及びＱ６を取り出す。そして、端点Ｑ５が基準線分Ｑ１Ｑｎ−１上に、端点Ｑ６が基準線分Ｑ２Ｑｎ上にあるか否かを判断し、線分Ｑ３Ｑ４のときと同様の処理を行い、図形として頂点座標を格納する場合は図９に示されるような形式で、点Ｑ５及び点Ｑ６の座標（ｑＸ５，ｑｙ５）及び（ｑｘ６，ｑｙ６）を記憶エリアに格納する。以降、すべての頂点について、処理し終わるまで前述された動作を繰り返す。
【００４６】
また、未処理の頂点がなく、すべての線分が終了した場合、前記線分情報加工部１１は、すべての頂点に対し処理が終わったと判断する。この場合、多角形情報は図７に示されるようになっている。そして、多角形描画処理部２２は、前記多角形情報を用いて多角形描画処理を行い、図形処理装置１０は処理を終了する。
【００４７】
なお、本実施の形態においては、図１６に示される四角形を用いて図形処理装置１０の動作を説明したが、結果的に任意の四角形を形成する情報であっても、本実施の形態における図形処理装置１０の動作は問題なく行われ、同様の効果を得ることができる。
【００４８】
また、本実施の形態においては、入力されるデータを図１７に示す順で処理する場合について説明したが、本線分の両端の頂点座標が、それぞれ、基準線分上にあるか否かを判断するときの比較の対象と、本線分の両端点の座標を格納するときの格納場所とを変更すれば、例えば、図１８に示される順でデータが入力されても同様の動作を行うことができる。
【００４９】
さらに、図１７における点Ｑｎ−１と点Ｑｎ、及び、図１８における点Ｒｎ−１と点Ｒｎが、それぞれ、同じ点を表していると想定すると、入力された線分情報が結果的に三角形を形成する場合であっても、図形処理装置１０は、本実施の形態で説明した動作と同様の動作を行うことができ、同様の効果を得ることができる。
【００５０】
次に、フローチャートについて説明する。
ステップＳ２１  線分情報２３を入力する。
ステップＳ２２  一本目の線分を取り出す。
ステップＳ２３  線分終了であるか否かを判断する。線分終了である場合はステップＳ２４に進み、線分終了でない場合はステップＳ２５に進む。
ステップＳ２４  線分描画処理を行い、処理を終了する。
ステップＳ２５  一本目の線分の両端点を格納し、線分の頂点数を更新する。
ステップＳ２６  位置関係基準情報を算出する。
ステップＳ２７  次の線分を取り出す。
ステップＳ２８  本線分と前線分との両端の位置関係は四角形の形成が可能なものであるか否かを判断する。本線分と前線分との両端の位置関係は四角形の形成が可能なものである場合はステップＳ３０に進み、本線分と前線分との両端の位置関係は四角形の形成が不可である場合はステップＳ２９に進む。
ステップＳ２９  線分描画処理を行い、処理を終了する。
ステップＳ３０  本線分と前線分との距離はペン幅以下であるか否かを判断する。本線分と前線分との距離はペン幅以下である場合はステップＳ３２に進み、本線分と前線分との距離はペン幅以下でない場合はステップＳ３１に進む。
ステップＳ３１  線分描画処理を行い、処理を終了する。
ステップＳ３２  本線分の両端点を格納する。
ステップＳ３３  線分の頂点数を更新し線分が終了したか否かを判断する。線分の頂点数を更新し線分が終了した場合はステップＳ３４に進み、線分の頂点数を更新し線分が終了しない場合はステップＳ２７に戻る。
ステップＳ３４  多角形描画処理を行い、処理を終了する。
【００５１】
このように、本実施の形態においては、複数本の線分の描画に際し、隣接する各線分の距離が、それぞれ、ペン幅よりも小さいか否かを判断し、隣接する各線分の距離が、それぞれ、ペン幅よりも小さい場合は線分として処理を行わず、これを一つの四角形又は三角形として処理を行うようになっている。これにより、複数回必要であった描画処理を一回の描画処理で済ませることができるため処理時間を大幅に軽減することができる。また、入力された線分の本数が多ければ多いほど、その軽減率は大きくなり、描画処理の高速化がより顕著になる。
【００５２】
次に、本発明の第３の実施の形態について説明する。なお、第１及び第２の実施の形態と同じ構造を有するものについては、同じ符号を付与することによってその説明を省略する。また、前記第１及び第２の実施の形態と同じ動作及び効果についてもその説明を省略する。
【００５３】
図２０は本発明の第３の実施の形態における図形処理装置の構成を示すブロック図である。
【００５４】
本実施の形態においては、線分情報加工部１１は、前記第１の実施の形態の図１に示される台形判定部１３及び台形データ加工部１４に代わり、図２０に示されるように、多角形判定部１７及び多角形データ加工部１８を有する。前記多角形判定部１７は、前記線分位置解析部１２において解析した点の位置関係によって、入力された複数本の線分をすべて描画した際の描画結果を予想し、それが一つの任意の多角形と成り得るかどうかを判断する。また、前記多角形データ加工部１８は、前記多角形判定部１７において一つの任意の多角形と成り得ると判断された場合は線分情報２３を一つの多角形情報に変換する。また、他の構成については、前記第１の実施の形態と同様であるので説明を省略する。
【００５５】
次に、本実施の形態における図形処理装置１０の動作について説明する。
【００５６】
図２１は本発明の第３の実施の形態における多角形を確定する輪郭情報を示す図、図２２は本発明の第３の実施の形態における多角形を生成する動作の例を示す第１の図、図２３は本発明の第３の実施の形態における多角形を生成する動作の例を示す第２の図、図２４は本発明の第３の実施の形態における多角形情報を示す第１の図、図２５は本発明の第３の実施の形態における多角形情報を示す第２の図、図２６は本発明の第３の実施の形態における多角形情報を示す第３の図、図２７は本発明の第３の実施の形態における図形処理装置の動作を示すフローチャート、図２９は本発明の第３の実施の形態における多角形情報を示す第４の図である。
【００５７】
本実施の形態においては、図２１に示されるような多角形Ｓ１Ｓ２Ｓ３Ｓ４Ｓ５Ｓ６を描画する場合の動作について説明する。まず、線分情報２３が線分情報加工部１１に入力される。この場合、前記線分情報２３は、図２２に示されるように、線分の集合が頂点Ｔ１、Ｔ２、Ｔ３・・・Ｔｎ−１、Ｔｎの順で、例えば、図６に示されるような形式で線分情報が入力される。そして、前記線分情報加工部１１は、まず、入力された線分情報２３のうち、一本目の線分の線分情報２３を取り出す。該一本目の線分の線分情報２３とは図２２における点Ｔ１（ｔｘ１，ｔｙ１）と点Ｔ２（ｔｘ２，ｔｙ２）の座標情報である。そして、入力された線分情報２３の数を頂点数で判断し、線分情報２３の数によって線分終了であるか否かを判断する。ここで、前記線分情報２３の数が二点のみの場合は、一線分しかなく、多角形ではないので、わざわざ多角形の情報に持ち替える必要はないため、線分終了であると判断する。そして、線分描画処理部２１が、そのまま、線分描画処理を行い、図形処理装置１０は処理を終了する。
【００５８】
また、前記線分情報加工部１１は、線分情報２３の数が二線分以上ある場合、線分終了でないと判断して、入力線分の頂点数から処理頂点二頂点分を減らし、頂点数を更新する。続いて、前記線分情報加工部１１は、図２９に示されるような形式で、図形情報としての多角形情報を作成する。この場合、まず、多角形情報を格納する記憶エリアである多角形情報格納領域を確保する。ここで、確保すべき多角形情報格納領域のサイズは次の式（９）によって算出することができる。
（領域のサイズ）＝（入力線分の頂点数：ｎ）×（Ｘ・Ｙ座標：２）
＋（頂点数格納領域：１）  ・・・式（９）
続いて、前記線分情報加工部１１は多角形の頂点を格納するが、この場合、多角形を構成する頂点は、輪郭線上を右回り又は左回りの順に格納されなくてはならない。そのため、初めの線分の両端点である点ＴＩ及び点Ｔ２の座標（ｔｘ１，ｔｙ１）及び（ｔｘ２，ｔｙ２）が、まず、図２９に示されるように、図形の頂点を格納する領域である多角形情報格納領域の真ん中に格納される。ここで、図形の頂点数がｎのときは、領域の（ｎ−１）番目とｎ番目に一点目のＸ、Ｙ座標を格納し、（ｎ＋１）番目と（ｎ＋２）番目に二点目のＸ、Ｙ座標を格納する。頂点を格納する場所は格納する度に更新し、次に格納する場所が分かるようにする。また、多角形の頂点数は、入力された線分の頂点数と同じくｎであり、多角形情報格納領域の０番目に格納される。
【００５９】
続いて、前記線分情報加工部１１は、次の線分の両端点である点Ｔ３及びＴ４を取り出し、各端点と前線分との距離を、それぞれ、算出する。一般に、点（ｘ０，ｙ０）と直線ａｘ＋ｂｙ＋ｃ＝０との距離Δは前記式（６）によって算出することができる。
【００６０】
そこで、前記線分情報加工部１１は、端点Ｔ３と線分Ｔ１Ｔ２との距離Δｔ３を、前記式（６）を用いて算出する。なお、線分Ｔ１Ｔ２の直線は次の式（１０）によって表すことができる。
（ｔｙ２−ｔｙ１）・ｘ＋（ｔｘ１−ｔｘ２）・ｙ十Ｃ＝０  ・・・式（１０）
ここで、Ｃ＝（ｔｘ２−ｔｘ１）・ｔｙ１−（ｔｙ２−ｔｙ１）・ｔｘ１である。
【００６１】
そして、端点Ｔ３の座標を（ｔｘ３，ｔｙ３）とすると、点Ｔ３と直線Ｔ１Ｔ２の距離Δｔ３は、次の式（１１）によって表すことができる。
Δｔ３＝｜（ｔｙ２−ｔｙ１）・ｔｘ３＋（ｔｘ１−ｔｘ２）・ｔｙ３
＋Ｃ｜÷√｛（ｔｙ２−ｔｙ１）2 ＋（ｔｘ１−ｔｘ２）2 ｝・・・式（１１）
ここで、Ｃ＝（ｔｘ２−ｔｘ１）・ｔｙ１−（ｔｙ２−ｔｙ１）・ｔｘ１である。
【００６２】
続いて、前記線分情報加工部１１は、同様にして、点Ｔ４と直線Ｔ１Ｔ２との距離Δｔ４を算出する。そして、前記線分情報加工部１１は、距離Δｑ３又は距離Δｑ４のどちらか一方でもペン幅より大きくないか否かを判断する。ここで、距離Δｔ３又は距離Δｔ４のどちらか一方でもペン幅より大きい場合、すなわち、本線分と前線分との距離がペン幅以下でない場合、多角形描画に変更すると線分描画とは描画結果に相違が出るため、線分描画処理部２１が、そのまま、線分描画処理を行い、確保していた多角形情報格納領域を開放して、図形処理装置１０は処理を終了する。
【００６３】
また、距離Δｔ３及び距離Δｔ４がともにペン幅より小さい場合、すなわち、本線分と前線分との距離がペン幅以下である場合は、線分描画を多角形描画に変更しても描画結果に違いは出ない。そのため、処理時間の短い多角形描画用に、本線分の両端点として点Ｔ３及び点Ｔ４の座標（ｔｘ３，ｔｙ３）及び（ｔｘ４，ｔｙ４）を図２５に示されるような形式で記憶エリアに格納し、格納場所を更新する。
【００６４】
次に、前記線分情報加工部１１は、入力線分の頂点数から処理頂点二頂点分を減らし、、頂点数を更新する。そして、未処理の頂点があるか否か、すなわち、すべての線分が終了したか否かを判断する。ここで、未処理の頂点がある場合には、すべての線分が終了していないので、再び、次の線分の両端点を取り出す。この場合、次の線分の両端点である点Ｔ５及びＴ６を取り出す。そして、線分Ｔ３Ｔ４のときと同様の処理を行い、図形として頂点座標を格納する場合は図２６に示されるような形式で、点Ｔ５及び点Ｔ６の座標（ｔＸ５，ｔｙ５）及び（ｔｘ６，ｔｙ６）を記憶エリアに格納する。以降、すべての頂点について、処理し終わるまで前述された動作を繰り返す。
【００６５】
また、未処理の頂点がなく、すべての線分が終了した場合、前記線分情報加工部１１は、すべての頂点に対し処理が終わったと判断する。この場合、多角形情報は図２４に示されるようになっている。そして、多角形描画処理部２２は、前記多角形情報を用いて多角形描画処理を行い、確保していた多角形情報格納領域を開放して、図形処理装置１０は処理を終了する。
【００６６】
なお、本実施の形態においては、入力されるデータを図２２に示す順で処理する場合について説明したが、線分の両端点の座標を格納する格納場所を変更すれば、例えば、図２３に示す順でデータが入力されても同様の動作を行うことができる。
【００６７】
次に、フローチャートについて説明する。
ステップＳ４１  線分情報２３を入力する。
ステップＳ４２  一本目の線分を取り出す。
ステップＳ４３  線分終了であるか否かを判断する。線分終了である場合はステップＳ４４に進み、線分終了でない場合はステップＳ４５に進む。
ステップＳ４４  線分描画処理を行い、処理を終了する。
ステップＳ４５  線分の頂点数を更新する。
ステップＳ４６  多角形情報格納領域を確保する。
ステップＳ４７  一本目の線分の両端点を格納し、格納場所を更新し、多角形の頂点数を格納する。
ステップＳ４８  次の線分を取り出す。
ステップＳ４９  本線分と前線分との距離はペン幅以下であるか否かを判断する。本線分と前線分との距離はペン幅以下である場合はステップＳ５２に進み、本線分と前線分との距離はペン幅以下でない場合はステップＳ５０に進む。
ステップＳ５０  線分描画処理を行う。
ステップＳ５１  多角形情報格納領域を開放し、処理を終了する。
ステップＳ５２  本線分の両端点を格納し、格納場所を更新する。
ステップＳ５３  線分の頂点数を更新し線分が終了したか否かを判断する。線分の頂点数を更新し線分が終了した場合はステップＳ５４に進み、線分の頂点数を更新し線分が終了しない場合はステップＳ４８に戻る。
ステップＳ５４  多角形描画処理を行う。
ステップＳ５５  多角形情報格納領域を開放し、処理を終了する。
【００６８】
このように、本実施の形態においては、複数本の線分の描画に際し、隣接する各線分の距離がそれぞれペン幅よりも小さいか否かを判断し、隣接する各線分の距離がそれぞれペン幅よりも小さい場合は線分として処理を行わず、これを一つの多角形として処理を行うようになっている。そのため、複数の線分一本一本に幅付け等の加工を施して処理し、描画する必要がない。したがって、より単純な描画処理で済ませることができるため、処理負担を軽減することができるものである。また、本実施の形態における図形処理装置１０は、任意の多角形を形成しようとする線分描画にも適用することができるため、汎（はん）用性が高い。
【００６９】
なお、前記第１〜第３の実施の形態における図形処理装置１０は、ペンプロッタなどのようにペンを用いて描画を行う装置の図形処理に特に有効であるが、ペンを用いて描画を行う装置以外の装置であっても、前述したように、図形を描画する際に複数本の線分を用いて結果的に多角形を描画する場合においても有効である。
【００７０】
また、本発明は前記実施の形態に限定されるものではなく、本発明の趣旨に基づいて種々変形させることが可能であり、それらを本発明の範囲から排除するものではない。
【図面の簡単な説明】
【００７１】
【図１】本発明の第１の実施の形態における図形処理装置の構成を示すブロック図である。
【図２】従来の多角形を確定する輪郭情報を示す図である。
【図３】従来の多角形を生成する動作の例を示す第１の図である。
【図４】従来の多角形を生成する動作の例を示す第２の図である。
【図５】従来の線に幅を付けて多角形を生成する動作の例を示す図である。
【図６】本発明の第１の実施の形態における多角形情報を示す第１の図である。
【図７】本発明の第１の実施の形態における多角形情報を示す第２の図である。
【図８】本発明の第１の実施の形態における多角形情報を示す第３の図である。
【図９】本発明の第１の実施の形態における多角形情報を示す第４の図である。
【図１０】本発明の第１の実施の形態における多角形を確定する輪郭情報を示す第１の図である。
【図１１】本発明の第１の実施の形態における多角形を生成する動作の例を示す第１の図である。
【図１２】本発明の第１の実施の形態における多角形を確定する輪郭情報を示す第２の図である。
【図１３】本発明の第１の実施の形態における多角形を生成する動作の例を示す第２の図である。
【図１４】本発明の第１の実施の形態における図形処理装置の動作を示すフローチャートである。
【図１５】本発明の第２の実施の形態における図形処理装置の構成を示すブロック図である。
【図１６】本発明の第２の実施の形態における多角形を確定する輪郭情報を示す図である。
【図１７】本発明の第２の実施の形態における多角形を生成する動作の例を示す第１の図である。
【図１８】本発明の第２の実施の形態における多角形を生成する動作の例を示す第２の図である。
【図１９】本発明の第２の実施の形態における図形処理装置の動作を示すフローチャートである。
【図２０】本発明の第３の実施の形態における図形処理装置の構成を示すブロック図である。
【図２１】本発明の第３の実施の形態における多角形を確定する輪郭情報を示す図である。
【図２２】本発明の第３の実施の形態における多角形を生成する動作の例を示す第１の図である。
【図２３】本発明の第３の実施の形態における多角形を生成する動作の例を示す第２の図である。
【図２４】本発明の第３の実施の形態における多角形情報を示す第１の図である。
【図２５】本発明の第３の実施の形態における多角形情報を示す第２の図である。
【図２６】本発明の第３の実施の形態における多角形情報を示す第３の図である。
【図２７】本発明の第３の実施の形態における図形処理装置の動作を示すフローチャートである。
【図２８】本発明の第１の実施の形態における多角形情報を示す第５の図である。
【図２９】本発明の第３の実施の形態における多角形情報を示す第４の図である。
【符号の説明】
【００７２】
１０    図形処理装置
１１    線分情報加工部
２２    多角形描画処理部
２３    線分情報
【図１】
2005275638.tif 000003
【図２】
2005275638.tif 000004
【図３】
2005275638.tif 000005
【図４】
2005275638.tif 000006
【図５】
2005275638.tif 000007
【図６】
2005275638.tif 000008
【図７】
2005275638.tif 000009
【図８】
2005275638.tif 000010
【図９】
2005275638.tif 000011
【図１０】
2005275638.tif 000012
【図１１】
2005275638.tif 000013
【図１２】
2005275638.tif 000014
【図１３】
2005275638.tif 000015
【図１４】
2005275638.tif 000016
【図１５】
2005275638.tif 000017
【図１６】
2005275638.tif 000018
【図１７】
2005275638.tif 000019
【図１８】
2005275638.tif 000020
【図１９】
2005275638.tif 000021
【図２０】
2005275638.tif 000022
【図２１】
2005275638.tif 000023
【図２２】
2005275638.tif 000024
【図２３】
2005275638.tif 000025
【図２４】
2005275638.tif 000026
【図２５】
2005275638.tif 000027
【図２６】
2005275638.tif 000028
【図２７】
2005275638.tif 000029
【図２８】
2005275638.tif 000030
【図２９】
2005275638.tif 000031