JPH0245889A - 領域塗り潰し方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［産業上の利用分野］ この発明は、領域塗り潰し方法に関するものであり、例
えば、グラフィックデイスプレィやページプリンタ等に
所要の図形を出力しようとするときに、所望のイメージ
展開をさせるべき対象の文字フォントや図形について、
塗り潰しを必要とする閉領域を、基本のベクトルデータ
から塗り潰していくようにされた領域塗り潰し方法に関
するものである。

［従来の技術］ 第１７図は、例えば、ジェイ、デイ−、フ才り−（Ｊ、
Ｄ、ＦＯＬＥＹ）著の［相互コンピュータ・グラフィ・
ンクスの基礎（Ｆｕｎｄａｍｅｎｔａｌｓ　ｏｆ　Ｉｎ
ｔｅｒａｃｔｉｖｅＣｏｓ＋ｐｕｔｅｒ　Ｇｒａｐｈｉ
ｃｓ）４（（著作権−１９８２、アヂソン・ウニズリ出
版社（八ｄｄｉｓｏｎ−Ｗｅｓｌｅｙ　Ｐｕｂｌｉｓｈ
ｉｎｇＣｏｍｐａｎｙ）、１９８４−７月改定版）の第
４４６頁に開示されているような、従来の領域塗り潰し
方法の説明図である。

この従来の領域塗り潰し方法によれば、対象の閉領域を
示すデータを所定の整数座標上に展開し、次いで、当該
閉領域内のある１点を指定する。そして、前記ある１点
から閉領域外にはみ出さないようにしながら描画点を移
動させて、所望領域の塗り潰しをしていく。このとき、
閉領域内の全部の点が移動・描画の対象となるために、
ある所定の着目点の上下左右の情報を常に観察しながら
描画点の移動をさせていく。そして、何等かの特異点が
見出されたときには、これに対応する情報を、特別な記
憶手段としてのスタックに蓄積していく。

そして、このスタック内の蓄積情報がなくなったときに
、ある対象の閉領域の塗り潰しが終了したものとされる
。

上記のような塗り潰しの際の描画手順を、より詳細に説
明する。まず、対象の閉領域内の任意の１点をスタート
点として指定する。所要の塗り潰し動作は、このスター
ト点から行われるものであるが、このときに上下左右の
点でのデータの黒（１）白（０）のいかんを適当に判定
する。描画動作を実行するときには、現在の点に対する
上下左右の各方向に優先順位を付して、所定の描画規則
に従った描画動作が実行される。

ここで第１７図（ａ＞を参照すると、スタート点”　ｓ
　”から右側への描画が実行される。いま、描画を実行
する点が“１”まで移動してきたものとすると、その上
部におけるデータが黒（１）から白（０）に変化する。

これが特異点として扱われて、対応の情報がスタック（
図示されない）に蓄積される。

ここでの前記情報は、点゛１゛の上部には対象の閉領域
内に塗り潰しを要する部分が存在することを指示するも
のである。また、この点“１°゛の右側でのデータは黒
（１）であることから、対象の領域の境界であるものと
解釈されて、右側への描画の実行は終了する。

次いで、スタート点゛Ｓ°′から左側への描画の実行が
再開される。いま、描画を実行する点が“２′′まで移
動してきたものとすると、その上部におけるデータが黒
く１）から白（０）に変化する。これが特異点として扱
われて、対応の情報がスタックに蓄積される。同様にし
て、描画を実行する点が“３゛まで移動してきたものと
すると、ここでも、その上部におけるデータが黒（１）
から白（０）に変化する。これも特異点として汲われて
、対応の情報がスタックに蓄積される。そして、描画を
実行する点の左側のデータが黒（１）になったときには
、対象の領域の境界に到達したものと解釈されて、左側
への描画の実行は終了する。

次に、前記のように完成したスタート点を含む横１ライ
ンの下側に関する情報がスタックに蓄積される。ここで
は、点“４゛に関する情報が蓄積されることになる。即
ち、前記の情報は、この点゛４゛°から左側をみて、対
象の閉領域内に塗り潰しを要する部分が存在することを
指示するものである。かくして、スタート点°を含む右
境界から左境界までの横１ラインの描画の実行が終了し
た時点で、点“１”ないし４°゛の情報がスタックに蓄
積されたことになる。即ち、ある所定の１ラインに対し
て、その上部での閉領域の空白部分および下部での当該
閉領域の空白部分が順次に指定されたことになる。

ここで、スタックに蓄積された情報から所要のものを取
り出し、その内容に基づいて、次に続く１ラインの描画
実行のためのスタート点を決定する。いま、第１７図（
ｂ）を参照すると、前記第１７図（ａ）における点“４
°゛に対応する情報の内容に基づき、先の１ラインの直
下に新規な１ラインの描画動作が施されたものである。

この第１７図（ｂ）においては、点“４″および“５”
に関する情報が、改めてスタックに蓄積されることにな
る。

次に、第１７図（Ｃ）は、前記第１７図（ｂ）における
点“５°′に対応する情報の内容に基づき、第３ライン
の左側部分の描画動作が施されたものである。これに続
けて第１７図（ｄ）、（ｅ）、（ｆ）の順で部分的な描
画動作が実行されて、第１７図（ａ）における横１ライ
ンより下部の全領域が塗り潰されたことになる。

この段階において、スタックに残留している情報は、点
“１゛、“２′′および“３′′番こ対応するものであ
る。そして、これらの情報を適当に使用することで、閉
領域の上部についての塗り潰し動作が実行されて、対象
とする閉領域全体の塗り潰しが完了することになる。こ
のときには、スタックに蓄積された情報は完全になくな
っている。

［発明が解決しようとする課題］ 従来の領域塗り潰し方法は以上のようになされるもので
あり、 ■二対像の閉領域内にある所定の１点を規定する必要が
あり、これを省略するためには、この内部点に関するデ
ータを対象の閉領域図形データとは別に用意しておく必
要があること： ■：ある１ラインについて１点毎の描画動作を実行する
ときに、それぞれの点に対する上下左右の点の状態を検
索して、所要の情報をスタックに蓄積させておく必要が
あること； ■；前記の描画動作の実行のためのアルゴリズムが複雑
になるとともに、これを格納させておくための大容量の
メモリが必要であること；■：上記のような動作のため
に多くの時間を必要とし、グラフィックデイスプレィ上
での表示やレーザプリンタによる印字のために多くを割
くことができないこと； というような問題点があった。

この発明は上記のような問題点を解決するためになされ
たもので、折れ線のような所定の線分で囲まれた閉領域
を形成する図形データの展開や領域塗り潰しのための描
画アルゴリズムを簡単化して、高速かつ的確な塗り潰し
処理が可能にされた領域塗り潰し方法を得ることを目的
とする。

［課題を解決するための手段］ この発明に係る領域塗り潰し方法は、対象の図形として
の閉領域の輪郭を構成する所定の輪郭点から、前記閉領
域を表わす座標系の中の１個の座標軸と平行に、前記閉
領域の輪郭に含まれる画素の中の特定のものについて反
転処理を施しながら走査していくことで前記閉領域の塗
り潰しを行うものである。

［作用］ この発明においては、対象の閉領域の輪郭設定のための
輪郭点が、ある所定の座標軸（例えばＹ軸）の座標値毎
に１個だけ選択されて、前記閉領域に対する塗り潰し処
理が、前記所定の座標値毎に、他の座標軸（例えばＸ軸
）に対して平行に、前記輪郭点から１回だけ行われるよ
うにされる。

［実施例］ 以下、この発明の一実施例を図について説明する。第１
図は、この発明の一実施例が適用されるＬＥＤプリンタ
のデータ処理部を示すブロック図である。この第１図に
おいて、文書や図形のような対象のデータは、入力Ｉ／
Ｆ（１）を介してＣＰＵ（２）に加えられる。このＣＰ
Ｕ（２）は描画ＬＳＩ（３）とともにデータ制御部を構
成しており、入力されたデータの解釈がなされて、描画
ＬＳＩ（３）で使用される描画用コマンドに変換される
。

このように変換されたコマンドに基づき対応の展開処理
が施されて、単位量毎に（例えば、所定の１ペ一ジ分の
データ毎に）次段のフレームメモリ（４）に格納される
。このフレームメモリ（４〉は、１画素が１ビツトに対
応する平面座標で表されているものである。そして、こ
のように展開されたデータは、出力指令が出される毎に
、プリンタＩ　／Ｆ　（５）を介して、出力手段として
の適当なプリンタ（図示されない）に供給される。

第２図は、この発明の実施例方法の説明のための閉領域
の頂点を示す座標データの例示図である。

また、第３図は、前記頂点の座標データに基づいて作成
された閉領域の例示図であり、ここに、各頂点の並べか
たは、前記閉領域の内部を常に右側に見るようにされて
いる。即ち、この第３図で例示されている前記閉領域は
、３本の線分で囲まれた形状のものである。

このようにして表示される平面座標系の全部の座標点に
対応して、黒（１）または白（０）のいずれかの値が付
与されている。例えば、ある閉領域の全部に白（１）が
付与されているときには、当該閉領域は全く塗り潰され
てはいないことを示すことになる。

第４図は、塗り潰し動作が実行されたときの例示図であ
って、前記第２図および第３図で示された閉領域に対す
る展開処理がなされた後の状態を示すものである。

ここで、平面座標系の中のＸ軸に沿った描画手順につい
て触れておく。

ステップ１：先頭の頂点を始点とし、次に続く頂点を終
点とする。

ステップ２：始点と終点とを結ぶ直線を生成させ、始点
の側から１点の画素を発生させる。

ステップ３：求めた１点からｘｌ、。まで、Ｘ軸に平行
な直線を反転モードで描く。なお、Ｘ　ｍ　ａ　ｗは図
形データの全部の頂点の中で最大のＸ座標値を表わすも
のである。

ステップ４：終点までの発生がなければ、ステップ２に
戻って、対応の処理をする。

ステップ５：終点までの描画動作が終了したときには、
現在の終点を始点に変更し、更に次に続く頂点を終点と
して、ステップ２〜４を実行する。

ステップ６：最後の頂点が始点にされたときには、前記
先頭の頂点を終点として、ステップ２〜４を実行して、
全部の動作を終了する。

この発明の実施例方法によれば、ある２個の頂点を結ぶ
直線を発生させた点からＸ　ｍ　ｓ　ｗまでの、塗り潰
しのための直線の描画動作が、次のようにしてなされる
。

（Ａ　　２　　　の　　　　　を　　ぶ　　　のいま、
整数座標平面のようなデジタル図形が対象であるとする
と、その上での直線は次のように表される。即ち、ある
１個の座標（ｘｓ、ｙｓ）から別異の１個の座標（Ｘ　
ｓ、３’　＠）までの直線を表すときには、ｌ　ｙ　ａ
　　ｙ　Ｉ］ｌ　／　ｌ　ｘ　ａ　　ｘ　ｓ　ｌ　＜　
１であるものとすると、前記の直線はｌ　ｘ　ａ　　ｘ
　ｓｌ　＋　１個の点列から構成されることになる。こ
こでの点は、Ｘ軸方向には、その始点から終点までの個
々のＸ座標値毎に１個ずつ置かれることになり、同一の
Ｘ座標値を有する点は存在しない。一方、Ｙ軸方向につ
いてみると、ｌ　ｙ　−ｙ　ｓ　ｌ　＋　１個のＹ座標
値に対してｌｘａ　　ｘｓｌ　＋　Ｉ　ＩＩＩの点があ
ることから、ｘ　ａ　　ｘ　ｓ　ｌ　　ｌ　ｙ　ａ　　
ｙ　ｇ　ｌ　ｇは、ｙ８からｙ、までのいずれかと重な
ることになる。

第５１２Ｉは、このような場合の例示図である。この第
５図において、（ｘ　ｓ、　ｙ　ａ）　＝　（０，０）
、（Ｘ、。

ｙ　、）＝　（６，２）なる直線は、対象の閉領域のア
ウトラインの一部を表している。そして、前記の直線は
、下記の７個の点列で構成されている。

ｙ＝ｏのとき：ｘ＝０．１； 、ｙ＝１のとき：　ｘ＝２．３，４　；、ｙ＝２のとき
：ｘ＝５，６； いま、これらの各点に対する描画手順は次のように実行
されることになる。

＝０のとき： 第１回目の手順で、座標（０，０）から反転処理が実行
されて、前記座標（０，０）を含む右側全部が、−旦反
転して・にされる； 第２回目の手順で、座標（０，１）から反転処理が実行
されて、前記座標（Ｏｌｌ）を含む右側全部が、再度反
転して○にされる。

側）： 第１回目の手順で、座標（２，１）から反転処理が実行
されて、前記座標（２，１）を含む右側全部が、−旦反
転して・にされる・ 第２回目の手順で、座標（３，１）から反転処理が実行
されて、前記座標（３，１）を含む右側全部が、再度反
転して○にされる。

第３回目の手順で、座標（４，１）から反転処理が実行
されて、前記座標（４，１）を含む右側全部が、更に反
転して・にされる。

＝２のとき： 第１回目の手順で、座標（５，２）から反転処理が実行
されて、前記座標（５，２）を含む右側全部が、−旦反
転して・にされる； 第２回目の手順で、座標（６，２）から反転処理が実行
されて、前記座標（６，２）を含む右側全部が、再度反
転して○にされる。

このような反転処理が実行された結果が、第６図に示さ
れている。この第６図から理解されるように、ある所定
の閉領域に対するアウトラインを規定するために、同−
Ｙ座標内に２個以上の点が選択されたときには、１ライ
ン毎に実行される反転処理の回数に依存して、所望の塗
り清しが行われないことがある。

ところて、この発明の実施例方法を直線の描画に適用す
るときには、理論的には、第７図に例示されているよう
な描画動作の実行が必要とされる。

デジタル式図形上でのこの描画動作においては、Ｙ座標
の始点から終点に至る個数の点を発生させるだけでよく
、対象の直線を構成する全ての点を求める必要はない。

ここで第５図に戻ってみると、ここでは、座標（０，０
）、（２，１）および（５，２）の３点だけを選択して
、所望のアウトラインとすれば良いことになる。

また、ｌ　ｙ　−ｙ　ｇｌ　／　ｌ　ｘ　−ｘ　ｓ　ｌ
≧１であるときには、Ｙ方向での直線の点は１点ずつ置
かれることになる。例えば、（ｘｓ＋　ｙｓ＞＝（０、
Ｏ）であり、そして、（ｘａ＋　ｙ−）＝（２，６）で
あるときには、第８図に例示されているような直線が生
成され、また、これについての描画手順を各点毎に１口
実行するだけで、第９図に例示されているような塗り潰
し図形が生成される。

従って、このやり方においては、ある２個の頂点を結ぶ
直線を構成するための点は、同一のＹ座標上に２個以上
存在してはならないことになる。

Ｂ　２　の育　の　ぎ 関連のある頂点を逐次直線で結びながら描画動作をして
いくときには、ある１個の直線の終点は、次に続く直線
の始点と同一の座標上にある。

例えば、第１０図に示されているように、２個の直線間
の小角θ（９０°≦θく１８０°）のときに描画手順の
実行をしたものとすると、前記のような継ぎ目の点では
２度の描画手順の実行がなされることになる。このため
に、第１１図に示されているように、当該継ぎ目の点で
の塗り潰しができなくなる。これに対して、第１２図に
示されるように、２個の直線間の小角θ（０°〈θ＜　
９０　”）のときに描画手順の実行をしたものとすると
、このときには、第１３図に示されるように、塗り潰し
ができることになる。

なお、これらの現象は、ある直線の方向とその直後の直
線の方向とによって規定されるものである。また、描画
動作を実行しようとする直線の始点を描画対象に含める
か否かは、描画しようとする直線の方向とその直前の直
線の方向とによって規定されるものである。

この発明の実施例方法をデジタル図形の塗り潰しのため
に適用するするときには、上記されたような事情に基づ
いて、第１４図に示されているように、対象の直線をそ
の方向に応じて１６種類に分けて各直線の発生点の変更
がなされている。また、各頂点に間する所要の情報、即
ち、ある対象の直線の始点ならびに終点を描画の対象に
加えるか否かの情報を適宜に取り出すことができるよう
にされている。第１５図は、上記１６種類の方向毎に描
画の有無を説明する例示図である。この第１５図におい
て、Ｘ印は描画の有無を後述の第１表で規定するもので
ある。Ｏ印は描画の対象ではないことを規定するもので
ある。また、・印は描画の対象であることを規定するも
のである。第１６図には、前記各種の直線について、描
画動作の上での条件が与えられた表口が示されている。

その中の第１６図（Ａ）である第１表、および、第１６
図（Ｂ）である第２表には、始点の描画をするか否かの
情報が示されている。

まず、第１表についてみると、その縦軸には直前の直線
の方向が示されており、また、その横軸には描画動作の
対象としての直線の方向が示されている。この第１表に
おいて、 ０：始点のＹ座標と同一の点はいずれも描画をしない； １：始点のＹ座標と同一の点の中で、始点および当該始
点から最も遠隔の点は描画をする；２．３．４：始点は
いずれも描画をする。

次に、第２表についてみると、その縦軸には最初の直線
の方向が示されており、また、その横軸にはＭ後の直線
の方向が示されている。この第２表においては、対象の
図形を閉じるための最後の点について、描画する（１）
が描画しない（０）がを指示する情報が示されている。

なお、上記実施例では描画ＬＳＩが使用されて、フレー
ムメモリへの展開のために反転描画がなされた場合につ
いての説明がなされたけれども、描画ＬＳＩを使用する
ことなく、ＣＰＵによる全制御の下に描画動作を実行す
るようにしても良い。

また、上記実施例では対象の図形のアウトラインを表す
直線を発生させる場合についての説明がなされたけれど
も、そのためのアルゴリズムが比較的簡単なことから、
当該ソフトウェアを適当にハードウェア化することも可
能であって、このようにすることで、より高速な描画動
作を実現することができる。

また、前記第１表および第２表における情報については
、ある直前の直線における終点の描画動牛の有無に応じ
て変化するものであるから、このような条件に合致する
ものでありさえすれば、これらの第１表および第２表に
例示されている情報に限定される必要はない。

また、上記実施例では、描画点と非描画点との区別を２
値化したデータ０．１で表わすものとして説明されたけ
れども、これに限らず、例えば、中間的な濃淡のある点
に対しても、適当な多段階の設定をしておいて、描画対
象の図形データの値に応じた段階での描画動作の実行を
することができる。

更に、上記実施例では、２次元平面上での場合について
説明されたけれども、これに限らず、例えば対象の図形
データがある平面上にあるときには、３次元空間での適
用も可能である。

また、上記実施例では、折れ線による座標表示に基づく
図形の塗り潰しの場合について説明されたけれども、こ
れに限らず、いわゆるスプライン曲線に基づく図形であ
っても、スプライン関数に従って得られる点を適当な間
隔をもって配置し、これらについて直線近似をさせるこ
とで、はぼ同様な効果が奏せられる。

［発明の効果］ 以上説明されたように、この発明に係る領域塗り潰し方
法は、対象の図形としての閉領域の輪郭を構成する所定
の輪郭点から、前記閉領域を表わす座標系の中の１個の
座標軸と平行に、前記閉領域の輪郭に含まれる画素の中
の特定のものについて反転処理を施しながら走査してい
くことで前記閉領域の塗り潰しを行うものであることか
ら、図形データを発生させながら、反転モードにより１
ラインずつ描画動作を実行して所要の塗り潰しをするよ
うにされているために、描画動作が高速で行われるとと
もに、スタックのような特別な記憶手段を必要とするこ
とがなく、また、描画動牛を実行するためのアルゴリズ
ムが簡単であることから、そのための実行プログラムを
短くすることができるという効果が奏せられるものであ
る。

【図面の簡単な説明】

第１図は、この発明の一実施例が適用されるプリンタの
データ処理部を示すブロック図、第２図ないし第１３図
は、この発明の一実施例の動作を説明するための例示図
、第１４図は、その方向に応じて１６種類に分けた対象
の直線毎の発生点の変更例示図、第１５図は、１６種類
の方向毎に描画の有無を説明する例示図、第１６図は、
前記各種の直線について、描画動作の上での条件が与え
られた表口、第１７図は、従来の領域塗り潰し方法の説
明図である。 （１）は入力Ｉ／Ｆ、（２）はＣＰＵ、（３）は描画Ｌ
ＳＩ１４）はフレームメモリ、（５）はプリンタ尾１図 尾２図 亮３図 昂７図 ｙ Ｗ−，５図 ■ 箔８図 悠９図 Ｗ１６図 障礎Ｍどにｙう〉Ｘ ７’ｆ、１ｏ図 扇１１図 、り１２図 萬１３図 、￥、１５図 方向４ γ句５ オ百６ 方向７ ・ ・ ・ ・ す勾８ 方向９ 方向１０ オ句１１ オ菌１２ オ（至）１３ 方向１４ オ句１５ ・ × （Ｃ１） （Ｃ） （ｅ） （ｂ） （ｄ） （ｆ）

Claims (1)

【特許請求の範囲】
1. （１）対象の図形としての閉領域の輪郭を構成する所定
   の輪郭点から、前記閉領域を表わす座標系の中の１個の
   座標軸と平行に、前記閉領域の輪郭に含まれる画素の中
   の特定のものについて反転処理を施しながら走査してい
   くことで、前記閉領域の塗り潰しを行うことを特徴とす
   る領域塗り潰し方法。