JPS63219087A - 多角形の面塗り装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、多角形の面塗り装置に関し、更に詳しくは、
多角形の内部を塗りつぶすだめの装置に関する。特に、
プリンタ装置やＶＤＴ装置において有用である。

従来技術 第１７図に示すように、ΔＡＢＣが与えられ、その内面
を塗りたいものとする。

この場合に、まず、ｙ＝１として、２点Ａ−Ｂ間を練塗
りし、次に、ｙ＝２とし、線分ＡＣの方程式から点Ｐ、
を算出し、また、線分ＢＣの方程式から点Ｐ、を算出し
、点ｐ、−ｐ２間を練塗りし、これをＬ＝３．４，５．
６について繰り返してΔＡＢＣの内部を面塗りする技術
が従来公知である。

この従来技術では、多角形が、第１８図で示すように、
複雑な多角形ＡＢＣＤＥＦの場合には、第１９図に示す
ように、２つの比較的簡単な多角形Ａ１ＢＣＤ、とＡ、
０２ＥＦとに分解し、それぞれの多角形について別々に
面塗りを行っている。

かかる従来技術としては、例えば特開昭６１−８７３号
公報に開示のものがある。

従来技術の問題点 上記従来技術では、複雑な多角形を面塗りする場合に、
それをいくつかの簡単な多角形に分解し、それぞれにつ
いて面塗りを行う必要があり、処理が煩雑となり、所要
時間を要する問題点がある。

しかし、複雑な多角形を簡単な多角形に分解しないで面
塗りしようとすると、例えば第１８図に示すように、ｙ
＝３のときに３点Ｂ−Ｄ−Ｆ間を練塗りする例外的処理
や、Ｆ＝５の場合に２点Ｃ−Ｅ間を練塗りしない例外的
処理がある等、却って処理が煩雑となり、所要時間を要
することになる問題点がある。

発明の目的 本発明の目的とするところは、複雑な形状の多角形でも
、簡単な処理で、且つ、高速で面塗りすることができる
多角形の面塗り装置を提供することにある。

発明の構成 本発明の多角形の面塗り装置は、多角形の各頂点のｙ座
標値の中から最小値りと最大値Ｔとを抽出する最大最小
値抽出手段、多角形の１つの頂点をＱｎ、前方向に隣接
する頂点をＱｎ＋、、後方向に隣接する頂点をＱｎ−１
とするとき、頂点Ｑｎが前後の頂点と比較して極大又は
極小となる極点か否かを判定する極点判定手段、頂点Ｑ
ｎが極点であるときは辺Ｑｎ−Ｉ　Ｑｎについて、頂点
Ｑが極点でないときは辺Ｑｎ−＋　Ｑｎ　’　　（ただ
し点Ｑｎ′は頂点Ｑｎよりｙ方向に１だけ頂点Ｑｎ−１
に近付いた点）について、ｙ方向の最小値ｙｓ、、、ｙ
方向の最大値３’ｍ、）’方向の最小値ｙｍｉをもつ点
のＸ座標値”１ｍ　　およびその辺のΔｘ／Δｙを算出
し、この１組のデータ（Ｖ　ｗ　、Ｙ　ｌ＋ＩＸ　＋　
　ｘ７　ｍａ＋　＋　Δｘ／Δｙ）を得ることを全頂点
について行って辺テーブルを作成する辺テーブル作成手
段、辺テーブルからｙｍａｘ＝Ｌの組データを抽出して
ワークテーブルを作成するワークテーブル作成手段、ワ
ークテーブルの組データをＸｙｌ、、の順に２組づつ対
として、ｙ座標がＬ、ｘ座標が各対のＸ７＋ｎである２
点間を塗りつぶす練塗り手段、ワークテーブルの中から
ｙ−ａ−＝Ｌの組データを消去する組データ消去手段、
ワークテーブルの各組データについて”ｒｍにΔｘ／Δ
ｙを加算した和を新たにＸＹｍとする更新手段、Ｌをイ
ンクリメントし、辺テーブルからｙｍａｘ＝Ｌの組デー
タを抽出してワークテーブルに付加する組データ付加手
段、および上記練塗り手段から組データ付加手段を、Ｌ
≦Ｔの範囲で反復させる反復作動手段を具備してなるこ
とを構成上の特徴とするものである。

実方缶ｆタリ 以下、図に示す実施例に基づいて、本発明を更に詳しく
説明する。ここに第１図は本発明の一実施例の多角形の
面塗り装置を含むレーザブリンク装置の構成概念図、第
２図は与えられた多角形と境界領域の例示図、第３図は
境界領域でクリッピングされた新たな多角形の例示図、
第４図は新たな多角形を面塗りした状態を示す例示図、
第５図は第１図に示すレーザプリンタ装置における画像
処理の作動の一例のフローチャート、第６図は第１図に
示すレーザプリンタ装置の多角形クリッピング処理の作
動の一例のフローチャート、第７図は新しい辺を求める
処理の作動の一例のフローチャート、第８図は線分と境
界線の関係を示す例示図、第９図は辺クリッピング処理
の作動の一例のフローチャート、第１０図は境界点出力
処理の作動の一例のフローチャート、第１１図〜第１４
図は多角形を境界線でクリッピングすることによりでき
る新たな多角形の例示図、第１５図は辺テーブル作成処
理の作動の一例のフローチャート、第１６図は辺テーブ
ルの一例の例示図である。なお、図に示す実施例により
、本発明が限定されるものではない。

第１図に示すレーザプリンタ装置１において、コンピュ
ータから多角形の頂点の座標データと境界領域が与えら
れると、コントローラ２は、与えられた多角形を境界領
域でクリンピングして新たな多角形を生成し、次いで、
その新たな多角形の内部を塗りつぶした画像のデータを
生成し、これをピントマツプメモリ３にストレージする
。

そして、コントローラ２は、ビットマツプメモリ３にス
トレージした画像データを順に読み出し、レーザダイオ
ードドライバ４に出力する。

レーザダイオードドライバ４は、レーザダイオード５を
発光させ、画像をプリントアウトする。

具体例を示すと、第２図に示すように、多角形Ａ　Ｇ　
ＣＤ　Ｅ　Ｈが与えられると共に、境界領域としてｘ、
１．≦Ｘ≦”　ｌａＸ　Ｉ　　Ｖ　ＩＩＩ≦ｙ≦ｙ−が
与えられると、第３図に示すように、多角形Ａ　Ｇ　Ｃ
Ｄ　Ｅ　Ｈを境界領域でクリッピングして新たな多角形
ＡＢＣＤＥＦを生成し、この多角形ＡＢＣＤＥＦの内部
を、第４図に示すように、面塗りした画像をプリントア
ウトする。

以下、第５図〜第１６図を参照してこのレーザプリンタ
装置１における画像処理の作動を詳細に説明する。

まず、コントローラ２は、第５図に示すように、コンピ
ュータから多角形の頂点の座標と境界領域を入力される
（ＬＪＩ）、説明の都合上、第２図に示す如き多角形Ａ
ＧＣＤＥＨと、境界領域Ｘ、、。

≦ｘＳｘ１．ｙ、ｌ５ｙ５ｙ１がコンピュータから与え
られたものとする。

次に、コントローラ２は、多角形クリッピング処理を行
う（ｔＪ２）。

多角形クリッピング処理では、第６図に示すように、境
界線として、ｘ””　Ｘ　ＩＩＩを選択する（Ｇｌ）。

次に、その選択した境界線ｘ”　Ｘ　ａｌｌで、与えら
れた多角形をクリッピングして出来る新しい多角形の新
しい辺を求める処理を行う（Ｇ２）。

新しい辺を求める処理では、第７図に示すように、多角
形の各辺の内から一辺を取り出し、その両端点の座標を
得る（Ｈｌ）。例えば、多角形ＡＣＣＤＥＨの一辺ＡＣ
を取り出し、その端点Ａ。

Ｇの座標（ｘ＋＋　、ｙａ、）、　　（Ｘｇ　、Ｖｇ　
）を得る。

次いで、辺りリフピング処理を行う（Ｈ２）。

辺タリンビング処理とは、第８図に示すように、２点α
、βを結ぶ線分αβを境界線Ｘ＝Ｘ３でクリッピングし
て、新たな線分子βを得る処理である。

境界線ｘ−ｘ３としては、前記ステップＧｌで境界線Ｘ
　”　Ｘ　Ｉｎが与えられており、点αには前記端点Ｇ
が対応し、点βには前記端点Ａが対応する。

なお、辺ＡＧに関する点γを点Ｂと名付ける。

第９図に示すように、コントローラ２は、まずＸ工＜Ｘ
、であるか否かをチェックする（Ｓｌ）。

第８図に示す関係の場合は、ｘｃＬ＜Ｘ３だから、ステ
ップＳ２に移行する。

ステップＳ２では、ＸＢ＜Ｘ３であるか否かをチェック
する。第８図に示す条件の場合は、ＸＢ＜Ｘ３でないか
らステップＳ３に移行する。

ステップＳ３では、ＸＢ−Ｘ３か否かをチェックする。

第８図に示す例では、ｘＢはＸ、でないから、ステップ
Ｓ４に移行する。

ステップＳ４では、α点を２３点と置き、かつ、β点を
２２点と置く、すなわち、ＸニーＸ　Ｉ　ｒｙ、−ｙＩ
と置き、ＸＢ　＝Ｘ２．ＹＢ　→Ｖ２と置く。

次いで、境界点出力処理を行うが（Ｓ５）、この境界点
出力処理は第１Ｏ図に詳細に示すものであまず、Ｘ座標
値同志を加算して加算値Ｘ、を求めると共に、ｙ座標同
志を加算して加算値ｙ、を算出する（Ｒ１）。

次に、加算値Ｘ、をＬＳＢ方向へ１ビツトシフトしてシ
フト値Ｘｆとする（Ｒ２）。これは、加算（ａ　Ｘ　、
を２で除算することに相当するが、シフト処理であるか
ら、除算処理に比べて格段に高速に行うことができる。

次に、加算値ｙ、をＬＳＢ方向へ１ビツトシフトしてシ
フト値ｙ１とする（Ｒ３）、これも加算（直ｙ、を２で
除算することに相当するが、格段に高速に処理できる。

上記ステップＲ１〜Ｒ３は、点ＰＨ（Ｘ＋＋　　ＹＩ）
と点Ｐ２　　（Ｘ２１　　ｙ２）の区分点を算出する処
理に外ならないので、第８図における点αとβの２分点
が得られることになる。

次に、シフト値Ｘ（と境界線のＸ座標値ｘ３の差の絶対
値が１より小であるか否かをチェックする（Ｒ’４）。

シフト値ＸＩがｘａより１以上小ならば（Ｒ４、Ｒ６）
、算出した１分点は境界線Ｘ−Ｘ３より左にあるので、
ｘｆ−Ｘ＋　、３’ｆ−３’＋とおいて（Ｒ７）、前記
ステップＲ１に戻る。これは、２点α、βを結ぶ線分を
、区分点とβを結ぶ線分に置き換えたことに相当する。

一方、Ｘｉがｘａより１以上大ならば（Ｒ４゜Ｒ６）％
　Ｘｆ−＋３（２，ｙｆｍｙ２と置き（Ｒ８）、前記ス
テップＲ１に戻る。これは、２点α、βを結ぶ線分を、
αと区分点を結ぶ線分に置き換えたことに相当する。

このようにして線分の区分点を次々に求めて行き、ｘａ
に実質的に一致するまで繰り返す。

Ｘ、に実質的に一致すると、シフト値ｘＩと境界線のＸ
座標値ｘ３の差の絶対値が１より小となるので、シフト
値ｙ４を境界点Ｐ３のｙ座標値ｙ３として設定する（Ｒ
５）。

ステップＲ１〜Ｒ８によって、境界点Ｐ３のｙ座標値ｙ
、が求まるが、この処理は乗算、除算を含んでいないの
で、高速かつ高精度にｙ３を得ることができる。

境界点出力処理（Ｓ５）によって、境界点Ｐ。

の座標ＯＮ、）’３）が得られると、その境界点Ｐ３を
１点と置き（Ｓ６）、プリントアウトすべき線分として
線分子βをセットする（Ｓ７）。

かくして、第８図に示すように、境界線！””Ｘ３より
右側の線分子βが得られるが、これは新たな辺ＡＢが得
られたことを意味する。

さて、第８図に示す例では、Ｘ、ｔ＜ｘａ　＜ＸＢであ
ったが、その他の場合でも同様にして新たな辺が得られ
る。

例えば、ｘ、＞ｘａ　＞ｘＢならば、第９図のα点とβ
点とを入れ換えた処理（８２′〜３７′）によって新た
な辺を得られる。

また、）’ｃ＋ｊ８がＸ、に一致する場合は、境界点出
力処理を行うまでもなく、新たな辺を得られる（Ｓ８，
８’　）。

また、２点α、β共に領域内にあれば、元の辺αβがそ
のまま新たな辺となる。（３１０）。

さらに、２点α、βのいずれの点も領域内になければ、
元の辺から新たな辺を生じないこととなる（３１１）。

さて、第７図に戻り、上記□辺りリフピング処理（Ｒ２
）によって、新しい辺が得られると、その辺をメモリに
ストアする（Ｒ３）、例えば第８図の場合は、元の辺Ａ
Ｇが新たな辺ＡＢに置き換えられてストアされる。

次に、上記処理を行った辺が最後の辺でなければ（８４
）、次の辺を取り出して、その端点の座　　・標を得（
Ｒ５）、前記辺りリフピング処理Ｈ２に戻る１例えば、
多角形ＡＧＣＤＥＨの場合、辺ＡＧが終われば、次の辺
ＧＣについて再び辺クリッピング処理（Ｒ２）が行われ
るわけである。また、それが終われば、辺ＣＤ、辺ＤＥ
、辺ＥＨ，辺ＨＡについて各々辺クリッピング処理が行
われることになる。

そこで、第１１図に示すように、辺ＡＧからは新たな辺
ＡＢが得られ、辺ＧＣからは新たな辺を生じず、辺ＣＤ
、ＤＥ、ＥＨ，ＨＡからは元の辺がそのまま新しい辺と
して得られる。

すべての辺について処理を終了すると（Ｈ４）、新たな
辺で形成される多角形の頂点テーブルが作成される（Ｈ
６）。第１１図に示す例の場合は、新たに得られた辺が
、ＡＢ、ＣＤ、ＤＥ、ＥＨ。

ＥＡであるから、その頂点はＡ、Ｂ、Ｃ，Ｄ、　　Ｅ、
Ｈとなり、多角形であることが分かる。そして、その多
角形の新たな辺は、ＡＢ、ＢＣ，ＣＤ。

ＤＢ、ＥＨ，ＨＡであることが分かる。

第６図に戻り、ステップＧ２によって、境界線ｘ”　Ｘ
　ＩＩｍでクリッピングした多角形の新しい辺が求まる
と、次には、境界線をｙ＝ｙ−としくＧ３）、その境界
線で、先に得た新たな多角形をクリッピングして、新し
い辺を求める処理を行う（Ｇ４）。

第１２図はその結果を示すもので、多角形ＡＢＣＤＥＨ
の元の辺はそのまま新しい辺となり、変更を生じない。

次に、ステップＧ５．　Ｇ６によって、第１３図に示す
ように、頂点Ａ、Ｂ、Ｃ，Ｄ、Ｅ、Ｆが得られ、新しい
多角形が得られる。

同様に、ステップＧ７．Ｇ８によって、第１４図に示す
ように、新たな多角形へＢＣＤＥＦが得られ′るが、第
３図を参照すれば理解されるように、これは結局のとこ
ろ、元の多角形を境界領域Ｘ１．。

≦Ｘ≦ｘ、、、ｙ、１゜ＳＶ　ＳＶ−Ｌｍでクリッピン
グした新たな多角形である。

さて、第５図に戻り、上記多角形クリッピング処理（Ｕ
２）を行うことによって新しい多角形ＡＢＣＤＥＦが得
られると、次に、辺テーブル作成処理（Ｕ３）を行う。

辺テーブル作成処理は、第１５図に示すように、まず、
連続する３つの頂点の座標値（Ｘ＋、）’＋）　、　　
（Ｘ２　、）’２　＞　、　　（Ｘ３　、　　ｙ３　）
を取り出す（Ｗｌ）、例えば、３点Ａ、Ｂ、Ｃを取り出
すと、各座標値は、（３，１）、　　（１，３）、　　
（１゜５）となる。

次に、３’１＝３１２であるか否かをチェックする（Ｗ
２）、Ｙ＋　＝３’２であれば、後述するステップＷｌ
ｌへ移行するが、３’ｌ＝３’２でなければ、次のステ
ップＷ３に移行する。例えば、点Ａと点Ｂとでは、ＹＩ
＝１＋　　３１２−３であるから、ステップＷ３に移行
する。

ステップＷ３では、Δｘ／Δｙを算出する０例えば、点
Ａと点Ｂとでは、（１−３）／　（３−１）−一１とな
る。

次に、中心点（Ｘ２．７２）が前後の点と比較して極大
または極小となる極点か否かをチェックする（Ｗ４）、
もし、ｙｌ−’！ｚであるなら、点（Ｘｉ−ｙｚ）より
更に前の点（ｘ４１７４）を読み出し、そのＶ＋とｙｌ
とを比較して極大、極小を判断する。極点なら後述する
ステップＷｔＯに移行し、極点てないなら次のステップ
Ｗ５に移行する。例えば、点Ｂは、点Ａ、Ｃと比較する
と、極大でも極小でもないので、極点ではないと判定さ
れる。

中心点（１２，３１２）が極点でないと判定されると、
ｙｌとｙ３の大小がチェックされる（Ｗ５）、そして、
ｙｌ〉ｙ３でなければ、ステップＷ６に移行し、３’ｌ
　＞ＦｔであればステップＷ６゛に移行する０例えば点
Ａと点Ｃとでは、ｙｌ　＞ｙ３でないから、ステップＷ
６に移行する。

ステップＷ６では、ｙ、をデクリメントする。

一方、ステップＷ６′では、ｙ、をインクリメントする
。これは、中心点をｙ方向に１だけ後ろの点に近づける
ことを意味している。例えば、点Ｂの場合は、点Ａに近
づけられ、ｙ２＝３−１＝２となる。

次に、Ｙ＋−１２か否かがチェックされ（Ｗｌ）、等し
いならば後述するステップｗｔｔに移行し、等しくない
ならば、次のステップＷ８に移行する１例えば、点Ａと
Ｂとでは、）’Ｉ＝ｙ２でないから、ステップＷ８に移
行する。

ステップＷ８では、Ｆｌ　＞ｙｌであるか否かがチェッ
クされる＊）’＋　〉）’ｚならばステップＷ９に移行
し、そうでないならばステップＷ９をスキップする０例
えば、点Ａと点Ｂの場合、ｙｌ　＞ｙｌでないから、ス
テップＷ９をスキップし、ステップＷＩＯに移行する。

ステップＷＩＯでは、辺テーブルに組データ（３’　ｖ
ｓ　＋　　Ｙ　１＊　　Ｘ　Ｙ　ｍ　、Δｘ／Δｙ）を
ストアする。

ここで、ｙ、、、、ｙ−とは、ｙｌとｙ２のうち小なる
値がｙｍｉであり、大なる値がｙ−である、また、ｘｙ
ｍｉとは、Ｘ皿とｘ２のうち前記ｙ１１．に対応する方
の値である０例えば、点Ａと点Ｂの場合、Ｖ　ｍ　＝　
１．１１＝　２　（スフ　ｙ　）Ｗ　６　テ３’２　ヲ
テクリメントしているので）　、ｘＹ　ｍ　７３＋　Δ
ｘ／Δｙ＝−１となり、これらが１組として辺テーブル
にストアされる。

上記では点（Ｘ＋、）’＋）と点（Ｘ２’、ｙ２）とに
点Ａと点Ｂとを対応させたが、以下同様に多角形の各辺
の両端の頂点について全て対応させるように上記ステッ
プＷ１〜ＷＩＯを繰り返しくＷｌｌ、Ｗ１２）、全ての
辺について処理が終わると辺テーブルの作成を終了する
。

辺テーブル作成処理（Ｕ３）を終了することによって、
例えば第３図に示す多角形ＡＢＣＤＰ：Ｆの場合は、第
１６図に示す如き辺テーブルが得られる。

第５図に戻り、次に、組データ列を作成する（Ｕ４）。

これはＩ＆ｔするワークテーブルを作成する前処理とし
て行うものである。

組データ列の作成は、辺テーブルからｙｍｉの小さいも
の順に組データを取り出して、１列に並べるものである
、ｙｍｉは省略し、代わりに異なるｙ、１゜の組データ
の間には、ｙｍｉの差と同数の区切コードを挿入する０
例えば、第１６図に示す辺テーブルからは次のような組
データ列が生成される。

ｒ２，３．−１．３，３．ＩＪＪ　５，１，０゜５．３
．−１．５，３．ＩＪ　５，５．０」次に、コントロー
ラ２は、多角形の各頂点のｙ座標値の中から、最少値り
を抽出し、走査線をその最少値しにセットする（Ｕ５）
、例えば、第３図に示す多角形ＡＢＣＤＥＦの場合は、
Ｌ＝１となるので、走査線を１にセットする。

次に、組データ列の中から）’　ｍ　＝　Ｌの組データ
を抽出してワークテーブルを作成する（Ｕ６）。

例えば、Ｌ＝１ならば、ｙ、、、＝　１である組データ
を抽出するが、これは、［２，３，−１，１と（３，３
，１１があるから、ワークテーブルは、〔２，３，−１
，３，３，ｌ） となる。

次に、得られたワークテーブルの組データをＸ７ｗＹ　
＠Ｉｓの小さいもの順に並べ替える（Ｕ７）、例えばワ
ークテーブル（２，３，−１，３，３，１）の場合は、
ｘＹｅｎが等しいから、そのままの順序となる。

次に、ワークテーブルの組データを”Ｙ＊＋ｍの順に２
組づつ対となし、ｙ座標がＬ、ｘ座標が各対の”１ｗで
ある２点間を塗りつぶす（Ｕ８）、例えば、上記ワーク
テーブルからは”ｙｍとして３だけが得られるので、Ｌ
＝１だから、（３，１）の点だけを塗ることになる。す
なわち、第１８図のＡ点が塗られることになる。

次に、ワークテーブルの組データの中から、ｙ。

の値が走査線の値すなわちＬに一致するものを消去する
（Ｕ９）。例えば、ワークテーブルが〔２，３，−１，
３，３，１）の場合で、Ｌ＝１ならば、取り除かれる組
データはないことになる。

次に、ワークテーブルの組データのｘ７ｍＩＩにΔｘ／
Δｙの値を加算し、それを新たなｘｙｍｉと置＜（ＵＩ
Ｏ）、例えば、上記ワークテーブル［２，３，−１，３
，３，１］は、（２，２，−１゜３．４．１）になる。

次に、多角形の各頂点のｙ座標値の中で最大の値Ｔを抽
出し、その最大値Ｔと走査線の値りとが一致するか否か
をチェックする（Ｕｌｌ）、例えば、第３図に示す多角
形ＡＢＣＤＥＦの場合は、Ｔ＝５である。

Ｔと走査線の値りとが一致しなければ、走査線の値りを
インクリメントしくＵ１２）、前記ステップＵ６に戻る
。

インクリメントされて、Ｌ＝２となってステップＵ６に
戻ると、再びｙｍａｘ＝Ｌの組データが組データ列から
抽出され、ワークテーブルに加えられる０例えば、Ｌ＝
２では、これに等しいｙ、５．を持つ組データがないの
で、ワークテーブルには新たな組データが付は加えられ
ない。

次に、ステップυ７とＵ８とが行われ、インクリメント
された走査線で線塗りが行われる０例えば、点（２，２
）と点（４，２）の間が塗られることになる、すなわち
、第１８図のＰ、−Ｐ２間である。

次に、ステップＵ９では、例えば、前記ワークテーブル
（２，２，−１，３，４，１）で、Ｌ＝２を考えると、
この中から組データ＋２．２．−１）が消去されるので
、ワークテーブルは〔３゜４．１〕だけが残る。

次に、ステップＵＩＯでは、例えば、ワークテーブル（
３，４，１）は（３，５，１）となる。

次に、Ｌ＝３となってステップＵ６に戻ると、ｙ−＝Ｌ
＝３の組データがワークテーブルに追加され、ワークテ
ーブルは、例えば、（３，５，１，５，１，０，５，３
，−１，５，３，１）となる。

このワークテーブルは、ステップＵ７でｘｙｌ、。

の小さいもの順に並べ替えられ、（５，１，０゜５．３
．−１．５，３，１．３，５．１）となる。

そして、ステップＵ８において、点（１，３）と点（３
，３）の間が塗られ、また、点（３，３）と点（５，３
）の間が塗られる。すなわち、第１８図のＢ−Ｄ間、Ｄ
−Ｆ間である。

次いで、ステップＵ９において、ｙ−＝　Ｌ　＝　３の
組データが消去されるので、ワークテーブルは、（５，
１，０，５，３，−１，５，３，ｌ）となる。

次に、ステップＵＩＯで、ワークテーブルは、（５，１
，０，５，２，−１，５，４，１）となる。

次に、Ｌ−４となってステップＵ６に戻ると、ワークテ
ーブルは、（５，１，０，５，２，−１，５，４，１，
５，５，Ｏ）となる。

このワークテーブルは、ｘｙｗ＋＋の小さい順に並んで
いる。従って、ステップＵ７を経過しても同じワークテ
ーブルである。

ステップＵ８では、点（１，４＞と点（２，４）の間及
び点（４，４）と点（５，４）の間が塗られる。すなわ
ち、第１８図のＰ３−Ｐ４間、Ｐ５−ＰＧ間である。

ステップＵ９では消去する組データはなく、ステップＵ
ＩＯではワークテーブルは、（５，１゜０、５．１．−
１．５．５．１．５．５．　Ｏ）となる。

次に、Ｌ＝５となってステップＵ６に戻ると、ワークテ
ーブルは変化がなく、ステップＵ７でも変化がなく、ス
テップＵ８において、点（１，５）が塗られ、かつ、点
（５，５）が塗られる。すなわち、第１８図の点Ｃと点
Ｅとが塗られる。

ステップＵ９では、組データが全て消去される。

従ってステップＵＩＯでは何も行われない。

ステップＬｌｌｌでは、Ｌの値が最大値Ｔに一致したの
で、全ての処理が終了される。

かくして、第４図に示すように、多角形ＡＢＣＤＥＦの
内部が面塗りされたこととなる。

以上の説明から理解されるように、このレーザプリンタ
装置１では、与えられた多角形を与えられた境界領域で
クリッピングして新たな多角形を生成し、その内部を面
塗りした画像をプリントアウトすることができる。

発明の効果 本発明によれば、多角形の各頂点のｙ座標値の中から最
小値りと最大値Ｔとを抽出する最大最小値抽出手段、多
角形の１つの頂点をＱｎ、前方向に隣接する頂点をＱｎ
＋１．後方向に隣接する頂点をＱｎ−１とするとき、頂
点Ｑｎが前後の頂点と比較して極大又は極小となる極点
か否かを判定する極点判定手段、頂点Ｑｎが極点である
ときは辺Ｑｎ−１０ｎについて、頂点Ｑが極点でないと
きは辺Ｑｎ−５Ｑｎ′　（ただし点Ｑｎ′は頂点Ｑｎよ
りｙ方向に１だけ頂点ＱＴｌ−１に近付いた点）につい
て、ｙ方向の最小値Ｙ　ＩＩ。、ｙ方向の最大値ｙ、、
ｙ方向の最小値ｙｍｉをもつ点のＸ座標値ｘｙ＠ｎ　　
およびその辺のΔｘ／Δｙを算出し、この１組のデータ
（Ｖ　ｖｓ　＋　　３’　ｓｕｒ　＋　　Ｘ　Ｙ　ｖｓ
　＋　　Δｘ／Δｙ）を得ることを全頂点について行っ
て辺テーブルを作成する辺テーブル作成手段、辺テーブ
ルからｙ、１、＝Ｌの組データを抽出してワークテーブ
ルを作成するワークテーブル作成手段、ワークテーブル
の組データをＸＦｍ＋＋の順に２組づつ対として、ｙ座
標がり、　　ｘ座標が各対のｘｒ、ｎである２点間を塗
りつぶす線塗り手段、ワークテーブルの中からＹ、＝Ｌ
の組データを消去する組データ消去手段、ワークテーブ
ルの各組データについて、Ｘ１ｍ１＋にΔｘ／Δｙを加
算した和を新たにｘｒｕｎとする更新手段、Ｌをインク
リメントし、辺テーブルから３’　ｗ　＝　Ｌの組デー
タを抽出してワークテーブルに付加する組データ付加手
段、および上記練塗り手段から組データ付加手段を、Ｌ
≦Ｔの範囲で反復させる反復作動手段を具備してなるこ
とを特徴とする多角形の面塗り装置が提供され、これに
より多角形の内部を簡単な処理で且つ高速に面塗りする
ことが出来るようになる。

【図面の簡単な説明】

第１図は本発明の一実施例の多角形の面塗り装置を含む
レーザプリンタ装置の構成概念図、第２図は与えられた
多角形と境界領域の例示図、第３図は境界領域でクリッ
ピングされた新たな多角形の例示図、第４図は新たな多
角形を面塗りした状態を示す例示図、第５図は第１図に
示すレーザプリンタ装置における画像処理の作動の一例
のフローチャート、第６図は°第１図に示すレーザプリ
ンタ装置の多角形クリッピング処理の作動の一例のフロ
ーチャート、第７図は新しい辺を求める処理の作動の一
例のフローチャート、第８図は線分と境界線の関係を示
す例示図、第９図は辺りリフピング処理の作動の一例の
フローチャート、第１０図は境界点出力処理の作動の一
例のフローチャート、第１１図〜第１４図は多角形を境
界線でクリッピングすることによりできる新たな多角形
の例示図、第１５図は辺テーブル作成処理の作動の一例
のフローチャート、第１６図は辺テーブルの一例の例示
図、第１７図は面塗りの基本を示す例示図、第１８図は
複雑な多角形の面塗りを示す例示図、第１９図は従来例
による複雑な多角形の面塗りを示す例示図である。 （符号の説明） １・・・レーザプリンタ装置 ２・・・コントローラ ３・・・ビットマツプメモリ ４・・・レーザダイオードドライバ。 ０１２３４５６Ｘ ０１２３４５Ｘ ０１２３４’：＋　ｘ 第１図 プＣ 第７図 第６図 第１３図　　　　　　　　　　　例１図第１４図　　　
　　　　　　　　　　第し図第１０図 第１８図 第１９図 ０１２３４５　　Ｘ ゛第１６図 辺テーブル 第１７図 ０１２３４５　Ｘ

Claims (1)

1. 【特許請求の範囲】 １、 （ａ）多角形の各頂点のｙ座標値の中から最小値Ｌと最
   大値Ｔとを抽出する最大最小値抽出手段、（ｂ）多角形
   の１つの頂点をＱ＿ｎ、前方向に隣接する頂点をＱ＿ｎ
   ＿＋＿１、後方向に隣接する頂点をＱ＿ｎ＿−＿１とす
   るとき、頂点Ｑ＿ｎが前後の頂点と比較して極大又は極
   小となる極点か否かを判定する極点判定手段、 （ｃ）頂点Ｑ＿ｎが極点であるときは辺Ｑ＿ｎ＿−＿１
   Ｑ＿ｎについて、頂点Ｑが極点でないときは辺Ｑ＿ｎ＿
   −＿１Ｑ＿ｎ′（ただし点Ｑ＿ｎ′は頂点Ｑ＿ｎよりｙ
   方向に１だけ頂点Ｑ＿ｎ＿−＿１に近付いた点）につい
   て、ｙ方向の最小値ｙ＿ｍ＿ｉ＿ｎ、ｙ方向の最大値ｙ
   ＿ｍ＿ａ＿ｘ、ｙ方向の最小値ｙ＿ｍ＿ｉ＿をもつ点の
   ｘ座標値ｘｙ＿ｍ＿ｉ＿ｎ及びその辺のΔｘ／Δｙを算
   出し、この１組のデータ｛ｙ＿ｍ＿ｉ＿ｎ、ｙ＿ｍ＿ａ
   ＿ｘ、ｘｙ＿ｍ＿ｉ＿ｎ、Δｘ／Δｙ｝を得ることを全
   頂点について行って辺テーブルを作成する辺テーブル作
   成手段、 （ｄ）辺テーブルからｙ＿ｍ＿ｉ＿ｎ＝Ｌの組データを
   抽出してワークテーブルを作成するワークテーブル作成
   手段、 （ｅ）ワークテーブルの組データをｘｙ＿ｍ＿ｉ＿ｎの
   順に２組づつ対として、ｙ座標がＬ、ｘ座標が各対のｘ
   ｙ＿ｍ＿ｉ＿ｎである２点間を塗りつぶす線塗り手段、
   （ｆ）ワークテーブルの中からｙ＿ｍ＿ａ＿ｘ＝Ｌの組
   データを消去する組データ消去手段、 （ｇ）ワークテーブルの各組データについて、ｘｙ＿ｍ
   ＿ｉ＿ｎにΔｘ／Δｙを加算した和を新たにＸｙ＿ｍ＿
   ｉ＿ｎとする更新手段、 （ｈ）Ｌをインクリメントし、辺テーブルからｙ＿ｍ＿
   ｉ＿ｎ＝Ｌの組データを抽出してワークテーブルに付加
   する組データ付加手段、および （ｉ）上記（ｅ）から（ｈ）を、Ｌ≦Ｔの範囲で反復さ
   せる反復手段 を具備してなることを特徴とする多角形の面塗り装置。