JPH01191275A

JPH01191275A - 多角形の充填方法

Info

Publication number: JPH01191275A
Application number: JP63310301A
Authority: JP
Inventors: Gary M Beauregard; ガリイ・マイケル・ボーレガード; Larry K Loucks; ラリイ・キイース・ロツクス; Khoa D Nguyen; コオ・ダング・ニユーエン; Robert John Urquhart; ロバート・ジヨン・アークハート
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1987-12-09
Filing date: 1988-12-09
Publication date: 1989-08-01
Anticipated expiration: 2010-12-06
Also published as: JPH07113977B2; US5710578A; DE3851046D1; DE3851046T2; EP0323558A2; BR8806303A; US4962468A; EP0323558B1; EP0323558A3

Abstract

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

Description

【発明の詳細な説明】Ａ、産業上の利用分野本発明はグラフィック・タスク・デイスプレィ、特にグ
ラフィック・タスク・デイスプレィ・システム上に表示
される多角形の境界線により定義された領域内を充填す
るシステム及び方法に関する。

Ｂ、従来技術Ｊ　、　Ｄ　、　Ｆｏｌｅｙ及びＡ　、　Ｖａｎ　Ｄａ
ｍ著ｒＦｕｎｔａｍｅｎｔａｌｓ　ｏｆ　Ｉｎｔｅｒａ
ｃｔｉｖｅ　ＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓＪ　（
Ａｄｄｉｓｏｎ　Ｗｅｓｌｅｙ、　１９８２年刊）、４
５６〜４６０ページに記載されているように、多角形を
充填（ｆｉｌｌ）する永めの一般的なアルゴリズムが存
在する。この一般的なアルゴリズムは辺テーブル駆動ア
ルゴリズムと呼ばれる。この型のアルゴリズムは、コン
ピュータ・グラフィックのアプリケーションで、あるグ
ラフィック・タスクを実行するために呼び出される標準
的なルーチンの１つとして使用される。それらのグラフ
ィック・タスクには、直線、円、弧等の描画及び多角形
充填が含まれる。これらのタスクは、典型的な場合、グ
ラフィック・サポート・ライブラリ（ＧＳＬ）等のグラ
フィック機能を含むライブラリとして供給される。一般
に、グラフィック・サポート・ライブラリは、典型的に
は処理システムと一緒に供給されるグラフィック・サブ
ルーチンのパッヶ一ジであり、従ってユーザーは具体的
なデイスプレィ装置の複雑さも又そのデイスプレィ装置
へどのように書き込みを行なうかも知ることなしに高レ
ベルのインターフェースを用いてデイスプレィに書込み
を行なうことができる。

いくつかの単純な形の多角形の場合、このアルゴリズム
は非常に時間がかかるようになる。グラフィック・アプ
リケーションのユーザーがライブラリから多角形充填ル
ーチンを選択した後にデイスプレィ・スクリーンが結果
の充填多角形を表示する前に待機しなければならない時
に、アルゴリズムは過度に時間を消費する。ユーザーを
満足させるには、充填される多角形の精度をトレード・
オフすることなしに可能な限り充填速度が速いことが重
要である。

他の公知のアルゴリズムでは、アルゴリズム・ルーチン
は、Ｊ　、　Ｅ　、　Ｂｒｅｓｅｎｂａｍ、　　ｒＡｌ
ｇｏｒｉｔｈｍｆｏｒ　Ｃｏｍｐｕｔｅｒ　Ｃｏｎｔｒ
ｏｌ　ｏｆ　ａ　Ｄｉｇｉｔａｌ　ＰｌｏｔｔｅｒＪ、
ＩＢＭ　Ｓｙｓｔｅｍ　Ｊｏｕｒｎａｌ、　Ｖｏｌ、　
４．　Ｎｏ、　１（１９６５）、２５〜３０ページに記
載されたＢｒｅｓｅｎｈａｍアルゴリズムを使用する。

ＢｒｅｓｅｎｈａｍアルゴリズムはＪ。

Ｄ、Ｆｏｌｅｙ及びＡ、　Ｖａｎ　Ｄａｍ著の前掲書の
４３３〜４３６ページにも記載されている。Ｂｒｅｓｅ
ｎｈａｍアルゴリズムは、多角形の境界線を走査し、多
角形の境界線を構成する点を生成するために使用される
。しかし、この公知の多角形充填アルゴリズムは、走査
線の変更後に最初の点を選択する。このアルゴリズムに
伴なう問題点は、それが多角形の境界内を正確に充填し
ないことである。結果として表示される多角形は、あた
かも不完全に充填されたかのように見える。即ち、充填
は、全ての位置で多角形の境界に到達するとは限らない
。

多角形には種々の異なった形の多角形よりもその特定の
多角形の形に関してより効率的な多角形充填ルーチンが
存在しうる。論文ｒＭｅｔｈｏｄ　ｔ。

ｄｅｔｅｒｍｉｎｅ　ｔｈｅ　Ｃｏｎｖｅｘｉｔｙ　ｏ
ｆ　ＰｏｌｙｇｏｎｓＪ　、　ＩＢＭＴｅｃｈｎｉｃａ
ｌ　Ｄｉｓｃｌｏｓｕｒｅ　Ｂｕｌｌｅｔｉｎ、　Ｖｏ
ｌ、　２８．　Ｎｏ。

５　（１９８５）　、　２２０３〜２２０８ページは、
凸型多角形に関して、一般的多角形に関するよりも効率
的な充填アルゴリズムが存在することを開示している。

第２Ａ図を参照すると、多角形１０は、頂点Ａ、Ｂ、Ｃ
，Ｄ、Ｅにおいてその内角の全てが１８０度よりも小さ
ければ、凸である。第２Ｂ図はこの定義により凸でない
多角形１１を示している。というのは頂点Ｅにおける内
角が１８０度よりも大きいからである。

この論文には、全ての内角が１８０度よりも小さいか否
かを、従って多角形が凸か否かを決定する方法が開示さ
れている。この方法は、多角形の辺によって与えられる
２つの隣接するベクトルに関して外積を取る。もし全て
の外積が同じ符号を有するならば、多角形は凸である。

外積は多角形の各側辺が同じ方向に転回しているか否か
を示す。

第２Ａ図に示すように、頂点Ｅから出発し矢印１２で示
される方向に多角形１０の周囲を進むと。

全ての転回は左側に向うものである。しかし、第１Ｂ図
では、頂点りから出発して矢印１３の方向に多角形１１
の周囲を進むと、頂点Ｅでの転回は右方向であるが、他
の全ての転回は左方向である。

しかし、上記のテストは、第３Ａ図及び第３Ｂ図に示す
。多角形２０．２１を凸として分類するであろう。とい
うのは、全ての内容が１８０度よりも小さいからである
。また第３Ａ図又は第３Ｂ図のどちらにも示されている
ように、多角形２０．２１の周囲を頂点Ｂから矢印２２
．２３の方向に進む時、全ての転回は衣向きである。し
かし、多角形２０．２１は交差線を有し、１周よりも多
く転回を行なう。これらの型の多角形は、より複雑であ
り、以前に従来技術で知られていたより単純で効率の良
い充填アルゴリズムによっては正確に充填されない。従
って、上述の論文に記載されている方法は、全ての型の
多角形に関して多角形の凸性を正確に判定しない。

他の問題点は、多角形をテストする以前の方法が、第４
Ａ図及び第４Ｂ図に示すような形の多角形を、他の全て
の一般的な多角形と一緒に分類した事である。第４Ａ図
及び第４Ｂ図の多角形３０．３１はＸ−凹性（ｘ　−ｃ
ｏｎｃａｖｉｔｙ）を有するものとして知られている。

また、第４Ｂ図の多角形３１はＸ凹性と交差線の両者を
有している。

Ｂ０発明が解決しようとする問題点本発明の目的は、結果として得られる充填多角形の境界
線を定めるＢｒｅｓｅｎｈａｍアルゴリズムの点を含め
ることによって多角形を正確に充填することである。

本発明の他の目的は、任意の与えられた型の多角形に関
して多角形が凸か否かを正しく判定することである。

本発明の他の目的は、多角形の境界線まで且つ境界線を
含めて多角形を完全に充填するようにユーザーに見える
、凸多角形のための高速充填ルーチンを利用することで
ある。

本発明の他の目的は、交差線を持たないＸ凹性の多角形
及び交差線を持つＸ凹の多角形に関して第２の高速充填
ルーチンを利用することである。

Ｃ１問題点を解決するための手段本発明のシステム及び方法は、多角形の具体的な形に依
存して多角形を充填するのに必要な処理時間を最適化す
るために３つの多角形充填アルゴリズムの１つを実施す
る。多角形が特定の多角形充填アルゴリズムにより充填
されるべき多角形の類に入るか否かを判定するために、
多角形に対して種々のテストが行なわれる。

多角形の１つの類、即ち狭い意味での凸多角形の場合、
多角形の充填に必要な処理時間は第１の多角形充填アル
ゴリズムにより最適化される。これは多角形の半分で多
角形の各走査線毎に１つの最大値と、多角形の他半分で
多角形の各走査線毎に１つの最小値を記憶することによ
る。このアルゴリズムは、多角形に沿った特定の点にお
いてその点が最大値又は最小値の一部か否かを知ってい
るので正確に１つの値を記憶する。

他の類の多角形、即ちＸ凹性多角形の場合、第１の多角
形充填アルゴリズムはこの数の多角形を正しく充填する
には不適当である。この類の多角形では、多角形を正し
く充填するのに必要な処理時間は、多角例の各走査線毎
に２つの最小値及び最大値を記憶することにより最適化
される。次に各走査線毎に、最も小さい最小値から最も
大きな最大値へ充填線が引かれる。

第１の多角形充填アルゴリズムは、厳密な意味で凸な多
角形を充填する。第２の多角形充填アルゴリズムは、第
１のアルゴリズムよりも大きな多角形集合を充填する。

第２の多角形充填アルゴリズムは、１回走査当り正確に
１本の連続線で充填できる全ての多角形を充填する。こ
の集合に属する多角形はＸ凹性と交差線を持つことがあ
る。

第１の多角形充填アルゴリズムは、２つの条件の組み合
せを検査することによって、多角形が厳密に凸か否かを
判定する。第１に、多角形は、−定の転回方向を有する
か否かが検査される。即ち、多角形の各々の連続した線
が同じ方向に曲がるか否かが判定される。このテストの
結果として、方向が時計回り又は反時計回りとして決定
される。

点（ｘｏ、　ｙＯ）、（ｘｉ、ｙｌ）、（ｘ２＋ｙ２）
を有する任意の２本の隣接線に関して、ベクトル積の符
号に関する計算は次式の通りである。

（ｙｌ−ｙＯ）　　申　　（ｘ２−ｘｌ）　　　　　（
ｙ２　　　３’１　）　　本　　（ｘｉ−ｘｏ）もし上記の式がゼロよりも大きければ、多角形は右回り
、すなわち時計回りである。もし上式がゼロよりも小さ
ければ、多角形は左回り、すなわち反時計回りである。

もし全ての隣接線が同じベクトル積の符号を有するなら
ば、多角形は、一定の転回方向を有するものとして、第
１の条件を満足する。

多角形が厳密に凸であるために満足しなければならない
第２の条件は、ｙ方向−周テストである。

これは内角の和が３６０度に等しいようにすることと等
価である。

１周テストは、もし出発位置が最下部の頂点であり多角
形の辺に沿って連続的に進むならば、連続した辺のｙ座
標は最初は全て増加し、次に減少しなければならないこ
とを述べている６言いかえると、多角形の辺の第１の群
は最初に全て上昇し。

多角形の辺の第２の群は全て下降しなければならない。

一周条件は、多角形の第１の辺で出発することにより全
ての隣接頂点に関してｙ　（ｉ＋１）　−ｙ（ｉ）の代
数的符号が正確に２又は３回変化するならば満足される
。水平線は以前の線と同じ符号を有しているものと考え
られる。このテストを通過した多角形はｙ旧姓を有して
いる。即ち、ｙの任意の値に関して、１つの且つ１つだ
けの連続的な充填線が存在する。−周テストのために多
角形の点の周りを巡回する時、ｙ値の最大値及び最小値
並びにその位置がメモリに記憶される。

もし一定転回方向テストと一周テストが満足されると、
その多角形は厳密に凸である。多角形の線は２組に分割
され、その１組の線は走査線の最大値を定め且つ他の組
は最小値を定めるようにできる。

厳密に凸の多角形の場合、ｙの値当り２つの値の単純な
表が使われる。ｙの値は、ゼロから、興味のあるデイス
プレィ上の走査線の最大数にわたる。ｙの最小値の点か
ら出発し反時計回りの方向に進むと、多角形の各線毎に
それが交差する走査線毎のその線の最大値が表に保存さ
れる。同じ走査線上で２つの線が交差する頂点では例外
処理が行なわれる。両方の線が共有する画素の走査線上
の１つの最大値を記憶するために特別な処理が行なわれ
る。これはｙ方向の最大頂点（ｙ　ｍａｘ）に至るまで
、多角形の各線毎に続行される。この点から、線は最小
走査線だけを定める。多角形の各線毎に、それが交差す
る走査線毎にその線の最小値が表に保存される。再び、
２つの線が同じ走査線で交わる頂点では例外処理が行な
おれる。両方の線が共有し得る画素の走査線上の１つの
最小値を記憶するために特別な処理が行なおれる。多角
形の全部の線を巡回することにより表を埋めた後。

１つの実施例では、ｙ　ｍ１１１からｙ　ｗａｘの範囲
内のｙ毎に１本の水平線を描くためにＧＳＬマルチライ
ン描画ルーチンが呼び出される。各走査線毎に、選ばれ
た最小画素から選ばれた最大画素まで線を描くために他
の良好な実施例は他の方法を用いてもよい。

第２の多角形充填アルゴリズムは、第１の多角形充填ア
ルゴリズムよりも大きな多角形集合を充填する。もし多
角形が走査線当り１本の連続的な線で充填できるならば
、そのような全ての多角形はこの第２の多角形充填アル
ゴリズムで充填できる。この集合中の多角形はＸ凹性及
び／又は交差線を有する。

唯一の検査は、上述のようなｙ方向の一周の条件に関す
るものである。同様に、ｙ　ｍｉｎ及びｙ　ｍａｘの値
並びにそれらに関連した頂点が記録される。

この場合、方向が時計回りか又は反時計回りかに関する
知識は存在しない。事実、交差線を有する多角形におい
て、時計回り及び反時計回りの区別は不適切である。

多角形の線は再び２組に分割される。それらは元々与え
られた順序でｙ　ｍｉｎとｙ　ｍａｘとの間に存在する
。いずれかの組の多角形の線は、与えられた走査線上の
最小値又は最大値を定め得る。従って、線の各組毎に１
つの、最小値又は最大値のいずれかを記憶するために２
つの表が使われる。

多角形のｙの最小値の点から出発し、第１組の線に沿っ
て進むと、走査線との交点における所定の線の最小値及
び最大値が記憶される。多角形をたどる時、同様に第２
の表が、多角形の第２の組の線に関して走査線との各交
点における所定の線の最小値及び最大値を記憶する。

与えられた走査線の最小値は、２つの表からのその走査
線に関する２つの値の最小値である。同様に、与えられ
た走査線の最大値は、２つの表からのその走査線に関す
る２つの値の最大値である。

この時点で２つの表が走査され組み合されて１つの表に
なり、ＧＳＬＳ用マルチ５４能が呼び出される。あるい
は、両方の表に対するポインタが新しいＧＳＬマルチラ
イン・ルーチンに渡され、そのルーチンはそれらを組み
合せて水平線を描画する。他の良好な実施例は、各走査
線毎に、選ばれた最小値画素から最大画素へ線を引くた
めに他の方法を用いてもよい。

上記の多角形充填アルゴリズムにおいて、２段階のアル
ゴリズムが存在する。第１段は多角形の全ての線を走査
する。多角形の線毎に、Ｂｒｅｓｅｎｈａｍアルゴリズ
ムが使用される。点の値が最小／最大表に記憶されるべ
きか否かの判定が、その特定の点に対してＢｒｅｓｅｎ
ｈａｍアルゴリズムが動作する時に行なわれるので、多
角形の充填に必要な処理時間は最適化される。このよう
にして、第２段階、即ち後処理は前処理、即ち第１段階
と一体的に行なわれる。第１段階、前処理が終了すると
、多角形を充填するのに最小限の量の付加的処理しか必
要でない。

第２段階、後処理は、第１の多角形充填ルーチンに関し
て事実上存在しない。Ｂｒｅｓｅｎｈａｍアルゴリズム
が動作する時、各走査線の各ｙ値毎に最小値及び最大値
を有する。表において単純な記憶が行なわれる。後処理
において、多角形は、配列をｙ最小値からｙ最大値へ走
査し、各ｙの値毎に記憶されている最小値から最大値ま
で線を引くことによって充填される。

第２の多角形充填アルゴリズムの後処理において、多角
形は、最初に各ｙの値毎に記憶されている複数の最大値
のうち最大の値を決定し、モして′　記憶されている複
数の最小値のうち最小の値が決定される。次に、各ｙの
値毎に、最小の最小値から最大の最大値へ線が引かれる
。

Ｅ、実施例本発明は高速多角形充填のための２つのアルゴリズム（
表３）及び（表５）より成る。これらのアルゴリズムは
ＩＢＭ　　ＲＴ　　ＰＣのような処理システム９０と共
に提供されるデイスプレィ９４（第５Ａ図）と共に使用
できる。第５Ｂ図は処理システム９０の論理的構造９１
を示す。第５Ｃ図は処理システム９０の物理的構造９２
を示す。ＲＴ　　ＰＣについてはｒＩＢＭ　ＲＴ　Ｐａ
ｒｓｏｎａｌ　ＣｏｍｐｕｔｅｒＴｅｃｈｎｏｌｏｇｙ
Ｊ　、Ｆｏｒｍ　Ｎｏ、　５Ａ２３−１０５７に完全に
説明されている。上記の各アルゴリズムは利点と欠点と
を有している。プロセッサ、デイスプレィ・アダプタ、
メモリ及び工／○の相対的なスピードに依存して、所定
のデイスプレィに関する具体的なインプリメンテーショ
ンにおいては他のアルゴリズムがより効率的であろう。

両者の多角形充填アルゴリズムは、特定の形の分類に属
する多角形を高速充填するのに使用される。第１の高速
多角形充填ルーチン（表３）は各ｙ位置１０１における
値１１０を記憶するために表１１０（第７図）を利用し
、第２の高速多角形充填ルーチン（表５）は、多角形を
充填するために必要な、各ｙ位置１０１毎に値１１３を
記憶するための２つの表１１１，１１２（第８図）を利
用する。

必要な表１００（第７図）、１１１，１１２（第８図）
の大きさは、使用する特定の表示スクリーン９４（第５
Ａ図）の大きさに依存する。もし使用するデイスプレィ
９４が、ｙ方向１０２に３７５個の画素を有するモノク
ローム・デイスプレィであれば、表１００，１１１，１
１２は、３７５個のエントリ１０３を必要とする。もし
デイスプレィ９４（第５Ａ図）が、ｙ方向１０２に５１
２画素を有するＡＰＡ８デイスプレィであれば、表１０
０．１１１．１１２は、５１２のエントリ１０３を必要
とする。もしデイスプレィ９４（第５Ａ図）が、ｙ方向
１０２に１０２４０２４画素る精密デイスプレィであれ
ば、表１００，１１１゜１１２は、１０２４個のエント
リ１０３を必要とする。表１００．１１１，１１２中の
ｙエントリ１０１は、ゼロからスクリーンのサイズ引く
１の範囲にわたる。したがって、表１００．１１１゜１
１２の大きさは、デイスプレィ９４の大きさによって決
まる。

多角形充填アルゴリズムは、もし実際の多角形１２０が
、ｙ方向において、ｙ＝１０の値からｙ＝４７の値まで
範囲にあれば表１１１，１１２（第８図）が多角形１２
０の位置に応じて初期化をする必要のないように構成さ
れている。ｙ方向において多角形の領域（ｙ＝１０から
ｙ＝４７まで）内のｙ値１０１を有する、表１００．１
１１゜１１２中のエントリのみが使用される。もし多角
形１２０の最下位値の頂点Ａが表示スクリーン９４の下
端からｙ方向に１０番目の画素で始まるとすると、表１
００．１１１，１１２は、ゼロのエントリ１０５が１０
番目の画素位置の頂点Ａを表わすように初期設定する必
要がない。もし多角形が３７画素の全体的高さを有する
ならば、表１００に対する１１番目から４８番目までの
エントリ１０３だけが利用される。

第２のアルゴリズムは、第８図に流す表１１１゜１１２
を利用する。各表１１１．１１２は最小列１１６及び最
大列１１８を有する。また表１１１．１１２はゼロ１０
５から、スクリーンのサイズから１を引いた数１０７に
わたるサイズを有する。

第１図を参照すると、デイスプレィａ４（第５Ａ図）上
に示される時、多角形１２０の線１２１〜１２４は、走
査線１３２ｙｌＯ〜ｙ１８上でオン状態にある画素１３
０等の画素によって表現される。多角形１２０の線１２
１〜１２４はスクリーン９４上に実際には表示されない
が、ここでは説明のために示されている。表示が行なわ
れる時に線１２１〜１２４の各々を最も良く表現するた
めしこは各走査線１３２毎にどの画素がオンになるべき
かを決定する事、Ｂｒｅｓｅｎｈａｍアルゴリズムを用
いて行なわれる。このアルゴリズムはＪ、Ｅ。

Ｂｒｅｓｅｎｈａｍ、　　”Ａｌｇｏｒｉｔｈｍ　ｆｏ
ｒ　Ｃｏｍｐｕｔｅｒ　Ｃｏｎｔｒｏｌｏｆ　ａ　Ｄｊ
４ｉｔａｌ　Ｐｌｏｔｔｅｒ”、　ＩＢＭ　Ｓｙｓｔｅ
ｍ　Ｊｏｕｒｎａｌ。

Ｖｏｌ、　４．　Ｎｏ、　１　（１９６５）　、及びＪ
　、　Ｄ　、　Ｆｏｌｅｙ　ａｎｄＡ、Ｖａｎ　Ｄａｍ
、　　”Ｆｕｎｄａｍｅｎｔａｌｓ　ｏｆ　　Ｉｎｔｅ
ｒａｃｔｉｖｅＣｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ”
、　Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ刊、１９８２年に記
載されている。

両者の多角形充填アルゴリズムにおいて、多角形１２０
（第１図）の点１３０はＢｒｅｓｅｎｈａｍアルゴリズ
ムを用いて生成される。線１２１を表現するためにＢｒ
ｅｓｅｎｈａｍアルゴリズムによって選択された画素１
３０は第１２図では黒丸で示されている。多角形１２０
の線’１２１’　を表現するためにＢｒｅｓｅｎｈａｍ
アルゴリズムにより選択されなかった画素１３１はＸ印
で示されている。画素１３０゜１３１の連続した列を表
わす走査線１３２の組がＸ方向１０２に存在する。多角
形１２０の各線１２１〜１２４に関して、多角形１２０
の線１２１〜１２４を集合的に表わすために点１３０が
走査線１３２上で一度に生成される。

２つの多角形充填アルゴリズムは各々、そのアルゴリズ
ムで充填できる異なった範囲の組の多角形３３（第６Ａ
図）、３４（第６Ｂ図）、３５（第６Ｃ図）を有してい
る。第２のアルゴリズムは第１のアルゴリズムよりも大
きな範囲の多角形３３．３４．３５を充填できる。この
集合は多角形３３．３４．３５を充填するために各々の
ｙの値に関して単一の線１３３が存在するような全ての
多角形を含む。この組の多角形３３．３４．３５はＸ方
向１０４に凹部２８を有する多角形を含み得る。さらに
、この組は交差線３７．３８を有する多角形３５を含む
。多角形３６（第６Ｄ図）は、各ｙの値に関して、多角
形３６を充填するのに使用できる一意的で単一の線が存
在しないような例を示す。近い値のｙに関して、各ｙの
値毎に２本の線１３４．１３５が存在する。従って、ｙ
方向に凹部２９を有する多角形３６は第２の多角形充填
アルゴリズムを用いて充填できない。第１の多角形充填
ルーチンの場合、多角形の集合は厳密に凸の多角形３３
しか含まない、Ｘ又はｙ方向のどちらにも旧姓は存在せ
ず、且つ交差線も存在できない。

従って、各アルゴリズム（表３、表５）には、各々、そ
の特定の多角形充填アルゴリズムに適した多角形の範囲
内に多角形が入っているか否かを決定するフロント・エ
ンド・ルーチン（表２及び表４）が存在する。次に、特
定の多角形がどの多角形の範囲に属するかを決定するた
めに多角形に対して行なわれるテストを述べる。

以下の説明は第１図の多角形１２０を中心に行なう。最
初に、多角形の方向敏感性という用語の定義に関する説
明が必要である。多角形１２０は。

多角形１２０の周りの時計回り２５又は反時計回り２６
のいずれかの順序のＸ及びｙｓ、標の系列により記述さ
れる。任意の与えられた多角形充填アルゴリズムは、そ
の多角形充填アルゴリズムが時計回りの多角形に適用さ
れても又反時計回りの多角形に適用されても同じ結果を
与えるべきである。

即ち、多角形充填アルゴリズムを適用する時に多角形を
たどる方向に無関係に、多角形は同じ充填結果を与える
べきである。本発明の多角形充填アルゴリズムの両者に
おいて、結果のＢｒｅｓｅｎｈａｍ画素１３０の座標が
与えられる順序にかかわりなく、方向敏感性は存在しな
い。さらに、厳密凸の多角形のための第１の多角形充填
アルゴリズムに関する第１のテストは、多角形１２０の
対応する画素１３０の座標を与える時に多角形をたどる
方向、即ち時計回り２５又は反時計回り２６を決定する
。

第１の多角形充填アルゴリズムは方向敏感でない。

というのはこの多角形充填アルゴリズムに関するテスト
の一部として方向が特別に検出されるからである。もし
方向が時計回り２５であると判明すると１点（画素）１
３ｏが走査される順序は逆転される。点１３０は常に多
角形の周りを反時計周り２６に走査される。

第２の多角形充填アルゴリズムにおいて、多角形１２０
の各側１１５．１１４毎に２つの表１１１．１１２（第
８図）が存在するので、方向敏感性は存在しない。各々
の表１１１．１１２は、Ｘ方向１０２の各走査線１３２
毎にＸ方向１０４の最小値１１６及び最大値１１８を有
する。従って、多角形１２０の一方の側を上方へそして
他方の側を下方へたどっても又その逆方向にたどっても
無関係である。その結果は、Ｘ方向１０２の各走査線１
３２毎に最小値１１６及び最大値１〕、８を有する２つ
の表１１１，１１２である。各走査線１３２毎に、２つ
の表１１１，１１２に関する２つの最大値１１８からの
最大値が選択され、２つの表１１１，１１２に関する２
つの最小値１１６からの最小値が選択される。次に選択
された最小値画素から最大値画素へ線が引かれる。

これは第８図及び第１図を参照することにより説明され
る。ｙ＝１３のｙ値１０１を表わす走査線１３２に関し
て、多角形１２０の線１２１に関する最大値１１８は、
この例ではｘ＝２６３の値１１８を有する画素である。

この値はテーブルＢ（１１２）に記憶される。走査線ｙ
＝１３における多角形１２０の線１２１に関する最小値
１１６は画素４５におけるｘ＝２６２である。Ｘ＝２６
２のこの値はテーブルＢのエントリｙ＝１３に記憶され
る。多角形１２０の線１２４に関して、ｙ＝１３の走査
線１３２において画素５４の値はＸ＝２５６である。こ
の走査線上の線１２４に関してＢｒｅｓｅｎｈａｍアル
ゴリズムによりオンになる画素１３０は１つしかないの
で、この値はｙ＝１３におけるＸの最大値及び最小値の
両者である。Ｘ＝２５６のこの値はテーブルＡのエント
リｙ＝１３に記憶される。テーブルＡ及びテーブルＢか
ら、最大値１１８の最大のものはｙ＝１３に関しては２
６３であり、最小値１１６の最小のものはｙ＝１３に関
しては２５６である。次に各画素位置で記号「口」によ
り示されるように画素５４と４６との間の全ての画素１
３０，１３１をオンにすることにより、画素５４から画
素４６へ充填線１４２が引かれる。

第１の多角形充填ルーチンの場合、多角形１２０がこの
特定の充填アルゴリズム用の多角形の範囲に適合するか
否かの判定が行なわれる。第１の多角形充填アルゴリズ
ム（表３）のフロント・エンド（表２）に含まれるこの
テストには３つの部分が存在する。即ち、表２の５０７
１行の時計回り／反時計回りテスト、表２す５０８０行
の又又はｙ方向のいずれかの一部テスト、及び表２の５
０８４行のｙ最小値及びｙ最大値の決定である。

もし多角形がこれらのテストを満足すると、ｇｅｎｌｉ
ｎｅと呼ばれる第１の多角形充填ルーチンが、表２の５
１４４行のｇｓｆｆルーチンから呼び出される。もし多
角形がこれらのテストの１つに失敗すると、Ｊ　、　Ｄ
　、　Ｆｏｌｅｙ及びＡ　、　Ｖａｎ　Ｄａｎの前掲書
４５６〜４６０ページに記載されているような一般的な
充填アルゴリズムに以降する（表２の５１０６行）。

第１の多角形充填アルゴリズムに関する第１のテストは
時計回り／反時計回りテスト（転回テスト）である。こ
のテストは”Ｍｅｔｈｏｄ　ｔｏ　Ｄｅｔｅｒｍｉｎｅ
ｔｈｅ　Ｃｏｎｖｅｘｉｔｙ　ｏｆ　Ｐｏｌｙｇｏｎｓ
ｌ′、　ＩＢＭ　ＴｅｃｈｎｉｃａｌＤｉｓｃｌｏｓｕ
ｒｅ　Ｂｕｌｌｅｔｉｎ、　Ｖｏｌ、　２８．　Ｎｏ、
　５．１９８５年１０号に記載されている。

より具体的には、本発明の良好な実施例はこの転回テス
ト（表２．５０７１行以下）を、一定の回転方向の検査
のために含んでいる。即ち、多角形の線から線へ移動し
ながら、新しい線が同じ方向に折れ曲がるか否かを判定
する。このテストの副産物として５時計回り又は反時計
回りも決定される。もし２つの隣接した線１２１．１２
２（第１図）が点（ＸＯｌｙＯ）、（ｘｉ、ｙｌ）。

（ｘ２、ｙ２）を有するならば、ベクトル積の符号の計
算は次のようにして行なわれる。

（ｙｌ　　ｙＯ）＊　（ｘ２−ｘｉ）−（ｙ２−ｙｌ　
）　　傘　　（ｘｉ−ｘｏ）もし上式がゼロよりも大きければ、多角形はこの２本の
線に関して右向きに折れ曲がっている。

この例では、多角形１２０の線１２１及び１２２のベク
トル積はゼロよりも小さく、多角形１２０が左側又は反
時計回り２６に折れ曲っていることを示す。この転回テ
ストは多角形６２つの隣接線の各々について反復される
（表２の５０８９行以下）。もしこのテストの結果が同
符号であれば、多角形は転回方向一致テストを満足する
。

多角形が厳密に凸であるために満足しなければならない
第２の条件は、表２の５０９９行以下のｙ方向−周テス
トである。これは内角の和が３６０度に等しいという条
件と等価である。

−周テストは、多角形をたどるための出発位置が最下位
値の頂点１（第１図）であり多角形を辺１２１．１２２
．１２３．１２４に沿って順にたどってゆく場合、順次
の辺１２１，１２２，１２３．１２４のｙ座標１０２は
最初に全て増加し、次に減少することを定めている。言
いかえると、多角形の第１群の辺１２１，１２２は最初
に全て上昇し、第２群の辺１２３．１２４は次に全て下
降しなければならない。

一周条件は、多角形１２０の第１の辺１２１から出発す
ることにより全ての隣接頂点に関するｙ（ｉ＋１）　　
ｙ　（ｉ）の代数的符号が正しく２又は３回変化すれば
満足される。水平線は、以前の線と同じ符号を有するも
のと考えられる。このテストにパスした多角形はｙ旧姓
を有している。即ち、ｙの任意の値について、１つだけ
の連続な充填線１４２が存在する。−周テスト（表２，
５０９９行以下）のために多角形１２０の点１３０の周
りをたどる時、最大及び最小のＸ値及びその位置がメモ
リに記憶される。この多角形充填アルゴリズムでＢｒｅ
ｓｅｎｈａｍアルゴリズムが使われる前に、ｙ最小値２
及びｙ最大値１の値が、それらの位置のＸ値を用いて表
１００中で初期化される。ｙ最小値２に関するこの同じ
Ｘ値が、ｙ最大値エントリ１０３に関する表１００中の
ｍａｘｌ’０７及びｍ１ｎ１０６エントリの両者に記憶
される。同様に、ｙ最小値１に関する同じＸ値が、ｙ最
小値エントリ１０３に関する表１００中のｍａｘ　１０
７及びｍｉｎ　１ｏ６エントリの両者に記憶される。

転回方向一致テストとｙ方向−周テストを共に満足する
ことは、多角形の内角の総和が３６０度であり、多角形
が厳密に凸であると言う事と等価である。これら２つの
テストを通過した結果として、転回方向一致テスト中で
計算されたベクトル積の符号が多角形の方向を決定する
のに使われる。

もし上式の値がゼロよりも大きければ、多角形１２０は
時計回りの方向にたどったことになる。また上式の値が
ゼロよりも小さければ、多角形１２０は反時計回りにた
どったことになる。第１の多角形充填アルゴリズム（表
３）は反時計回りの方向に基いているので、もし式の符
号が時計回りの方向を示したならば、点１３０をたどる
方向は逆にされなければならない。

第１図を参照すると、多角形１２０が上述のように厳密
に凸であることが決定されると、多角形１２０の線１２
１．１２２．１２３，１２４は２つの組１１４．１１５
に分割される。１つの組１１４の線１２１，１２２は走
査線１３２の最大値を定め、他方の組１２３，１２４は
最小値１０６を定める。上記両者のテストにおける多角
形の前処理を経た多角形１２０の提示に無関係に、頂点
１がｙ最小値と決定され、頂点２がｙ最大値と決定され
る。

多角形１２０をｙ最小値１から反時計回りにｙ最大値２
へたどると、適当なｙの指標１０３に関して表１００の
ｗａｘエントリ１ｏ７（第７図）中に走査線１３２の最
大値が記憶される。第１の多角形充填アルゴリズムが１
つの走査線から次の走査線に進むと共に、以前の走査線
のＸの最大値１０７が記憶される。これはｙ最大値２に
到達するまでｙの各走査線１３２に関して繰り返される
。

ｙ最大値２に到達すると、多角形１２０は、ｙ最大値２
からｙ最小値１へ、以前に分割した線１２３．１２４を
トラバースされる。分割された腺１２３．１２４の組１
１５に関して、走査線１３２上の最後の点１３０が、各
ｙエントリ１０３に関する表１００中のＸの最小値１０
６として記憶される。これはｙ走査線毎に反復される。

第１の多角形充填アルゴリズムの場合、アルゴリズムは
ｙ最小値（第１図の画素１）で始まり。

反時計回りの方向にｙ最大値へ向って直行する。

ｙ最小値１からｙ最大値２へのこのトラバース中に、各
ｙ毎にｍｉｎ及びＩＩＩａｘのエン１−リ１１０を有す
る表１００が使用される。各ｙに関する最大Ｘ値（これ
は走査線１３２上の最後の点（画素）１３０である）が
表１００に記憶される。トラバース中にｙ最大値に到着
すると、多角形はｙ最大値２からｙ最小値１ヘトラバー
スされる。この部分の多角形トラバース中に、各走査線
１３２上の画素に関する最小値が表に記憶される。言い
かえると。

それは、次のｙ走査線に進んだ後に、以前の走査線上で
走査された最後の点１３０である。反時計回りに最下部
頂点１から最上部頂点２へ進むと、最大値が配列に記憶
される。最上部頂点２から最下部頂点１へ反時計回りに
進むと、最小値が配列に記憶される。

例えば、線１２１から出発して反時計回りに多角形をト
ラバースする時、ｙ＝１１に関する走査線１３２を表わ
すｙ＝１１のエントリ１０３に関するｍ　ａ　ｘエント
リ１０７に画素４２のＸ値が記憶される。ｙ＝１２の次
の走査線１３２の場合は、ｙ＝１２のｙエン１−リ１０
３に関するｍａｘエントリ１０７に画素４４の値が記憶
される。これは各走査線１３２毎に反復される。同様に
、多角形１２０を頂点２から下向きにトラバースする時
、走査線１３２の画素１３０に関する最小値が、対応す
るｙエントリ１０３に関する最小値エントリ１０６に記
憶される。例えば、画素５４，５３．５１の値が、各々
表１００の中のそれぞれｙ＝１３、ｙ＝１２及びｙ＝１
１を表わす走査線に関する最小値エントリ１０６に記憶
される表２は第１の多角形充填アルゴリズムをＣ言語のコード
で表したものである。これはｇｓｆｆと呼ばれ、その第
１引数１ｎｌｉｎｅは多角形の辺の数である。

第２の引数ｉｘｙは多角形のＸ点の配列である。

第３の引数ｉｎｙは多角形のｙ点の配列である。

これら最初の３つのパラメータは入力パラメータである
。引数ｘｓは第７図に示されているように交互にｍｉｎ
　１０６及びｍａｘ１０７の値を両方含む配列１００の
開始点へのポインタである。その最初のエントリはｙ＝
Ｑのｘｍｉｎ１０６であり、２番目のエントリはｙ＝Ｑ
のｘｍａｘ１０７である。そして３番目のエントリはｙ
＝ｌのｘｍｉｎ１０６．４番目のエントリはｙ＝ｌのｘ
ｍａｘ１０７である。

これはスクリーンのサイズから１を引いた値まで、例え
ば、１０２４画素のスクリーンの場合は１０２３まで、
ｙ方向１０２に続く。引数ｙｓは実施上の細部に関する
もので１点Ｏ，Ｏ１１，１，２，２，３，３・・・・・
・スクリーン・サイズ−１例えば１０２３．１ｏ２３の
配列である。ｙ　配列１０１は１度初期化される（行５
０５２）。この配列１０１が呼び出される時、Ｘに伴な
う正しいｙを得るためにｘｌｌｏ及びｙｌｏｌの対とし
て呼び出される。

行５０５７〜５０８７は、ｙ−周テスト及び転回テスト
の初期化を行なう。行５０９５〜５０９７は、転回テス
トで使われる式である。行５０８４〜５０８７は最初の
点のｙ　ｍｉｎ及びｙ　ｗａｘを初期化する。次に、ｆ
ｏｒループ（行５０８９）がある。

これは以前に説明した３つのテストを行なう。

ｆｏｒループは転回テスト（行５０９０〜５０９７）を
計算し続け、ｙ　ｌｌｌ１ｎ及びｙｍａｘを更新しく行
５１０９〜５１１１）、そして−周テスト（行５０９９
〜５１０２）を更新する。−周テスト（行５０９９〜５
１０２）中で、新しい符号は、それが負であれば０に等
しく、正であれば１に等しい。新しい符号が古い符号に
等しくなければ、カウントに１が加算される。このカウ
ントは符号の変化の数である。もしループの外側の方向
が、ちょうど計算した所の方向と違っていたら、又はｙ
の符号の変化の数が４以上であれば（行５１０４）、テ
ストは失敗しく行５１０５）、ループから出る（行５１
０６）。もしテストが失敗しなかったら、アルゴリズム
は次のように継続する。

次のステップ（行５１０９）はｙの高さのテストである
。もし新しいｙが以前のｙ　ｍａｘよりも高ければ、ｙ
　ｍａｘは新しい値に更新される。新しいｙ　ｍａｘが
見い出された所のインデックスが記憶される。同じこと
が最小値についても行なわれる。

もし最大値を越えなければ、新しいｙ値が以前のｙ　ｍ
ｉｎ値よりも小さいか否かを見るために、ｙ　ｍｉｎ値
が検査される。もしそうであれば、ｙ　ｌｌｌ１ｎ値は
新しいｙ　ｍｉｎ値で更新される。またｙ　ｍｉｎ値の
位置を記録するためにインデックスも更新される。これ
は行５１１２でループを終了させる。行５０８９〜５１
１２は事前テストである。ｇｓｆｆアルゴリズムは、ｆ
ａｉｌフラグが事前テスト中にセットされていなければ
、行５１１４に続く。

行５１１４は、ｙ配列１０１（第７図）に関する点の総
数は、ｙｍａｘ　−ｙｍｉｎ＋　１の和の２倍である。

行５１１６〜５１１８はデバッグ目的の条件付きのプリ
ント・アウトである。行５１１９〜５１３４は診断出力
である。もしｆａｉｌフラグが１に等しければ、事前テ
ストは失敗である。もし方向が違っていれば、アルゴリ
ズムは旧姓テストに失敗したことをプリント・アウトす
る。もし符号変化が４以上であれば、アルゴリズムは一
部テストの失敗をプリント・アウトする。

アプリケーション・コードにおいて、事例テストが失敗
した場合に多角形充填を行なうためによリ一般的なアル
ゴリズムが呼び出されるのが、この地点、即ち行５１２
５である。もし事前テストに失敗すると、ユーザーによ
り充填するように選択された多角形に関して第１の多角
形充填ルーチンは使用できない。

行５１４０は、もし方向がゼロであれば、それは既に反
時計回りであり、点１３０が下部の点から反時計回りに
多角形の各線１２１〜１２４毎に走査される。行５１４
０〜５１５３は、下部の点が多角形の最初の線でない場
合に多角形の線がどのように走査されるかを示す。

行５１４４は、第１の多角形充填アルゴリズムの核心部
に対する実際の呼び出しである。行５１４４に先行する
ステップは、正しい線が指示されそれが反時計回りであ
る事等を保証している。

ｇｅｎｌｉｎｅ　（行５１４４）は５つの引数を有する
。

第１の引数は、各ｙの値毎に、ｘ　ｍｉｎ及びｘ　ｎ＋
ａｘの値が記憶されているｍｉｎ／ｍａｘ配列１００　
（第７図）へのアドレスである。次に２つの引数は、走
査中のｉ番目の点のＸ及びｙである。その次の２つの引
数は、ｉ番目の点の直後の点のＸ及びｙである。

従って、ｇｅｎｌｉｎｅは配列１００へのポインタ、並
びに第１の画素に関するＸ及びｙ、第２の画素に関する
次の隣接Ｘ及びｙにより記述される線を指定して呼び出
される。

ｇｅｎｌｉｎｅは走査線１３２の各々のｙの値について
最小値１０６及び最大値１０７を計算する。多角形１２
０は厳密に凸であり、且つ反時計回りの順序で提供され
ていると仮定する。従って、多角形１２０は、各ｙの値
毎に単一の水平線１４２で充填できる。１つの表１００
しか使用せず、各走査線１３２毎にこの表に最大値１０
７と最小値１０６だけが保存される。同じｙに複数の画
素を有する線は、ｙが変化する時にＸを更新することに
よってのみ取り扱われる。８全円領域Ｉ、■、■、■中
の線の場合更新は最大値１０７であり、一方８分円領域
■、■、■、■の場合更新は最小値である。第９図に示
されているように、８分用地域Ｉは０度で始まり（但し
ｙはゼロ、Ｘは任意の正の値である）、４５度で終る。

８分円領域■は４５度から９０度の範囲にわたる。これ
は領域Ｉ〜■に関して同様である。多角形の線は、線の
角度が０度と４５度との間にあれば８分円領域Ｉ中にあ
る。多角形の線は、線の角度が４５度と９０度との間に
あれば８分周領域■中にある。多角形の線は、その線の
角度に依存して８分円領域の１つの中にある。多角形１
２０は、前面１２１，１２２を上方ヘトラバースされる
時に点が８全円領域■、■、■、■内にしか入らないよ
うに８分円領域内に位置付けられる。

表１００　（第７図）はこの処理に特有であるが。

他のインプリメンテーションに関しても使用できるであ
ろう。鍵は、各ｙに関して１つのＸ最大値と１つのＸ最
小値しか存在しないので、全てのｙが定数であり初期化
の時に一度だけ計算されることである。表は第７図に示
されるように下記のように構成される。

ｙＯｘｍｉｎｙＯｘｍａｘｙｌ　　ｘｍｉｎｙｌ　　ｘｍａｘｙ２　　ｘｍｉｎｙ２　　ｘｍａｘｙ　ｍａｘ　　ｘ　ｍ１ｎｙ　ｍａｘ　　　ｘ　ｍａｘｘ　ｌ１ｉｎはｙｍａｘに関して初期化され、ｘ　ｗａ
ｘはｙｌＩｌａｘに関して初期化される。これにより線
の最初の点で最小値又は最大値の同じＸ値を保持する必
要がなくなる。最初の点１４１，１６１（第１図）は、
線を引く時に除外されるが、それ以後のあらゆる点１３
０が含められる。与えられた多角形１２０のｙ　ｍｉｎ
　１からｙ　ｗａｘ　２までの表１００の一部だけが多
角形充填に使用される。

従ってｇｅｎｌｉｎｅは多角形１２０の１つの線１２１
〜１２４に関する点１３０を生成する。行６０４９及び
行６０５ｏは線の傾斜を生成する。行６０５５は配列中
の現在の位置のアドレスを計算するこれは現在の位置の
表１００中のＸ最小値１０６を指す。例えば、もしｙが
１０であれば、ポインタは配列１００の２００番目位置
１０８を指す。

エントリ１０８はｙ＝１０に関するＸ最小値１０６を含
み１次のエントリ１０９はｙ＝１０に関するＸ最大値１
０７を含む。

ｇｅｎｌｉｎｅアルゴリズムの行６０６０は、多角形の
線が水平である特別な場合を処理する。もし最初のｙが
２番目のｙに等しければ、水平線が存在する。もし水平
線上でｘ２がｘｌよりも大きければ、全ての点は同一の
走査線上にあり、Ｂｒｅｓｅｎｈａｍアルゴリズムのイ
ンプリメンテーションは不要である。この場合、Ｘの最
大値、ｘ２がｘ　ｍａｘに記憶される。もしｘ２がｘｌ
よりも小さければ、線は８全円領域■、■、■、■のい
ずれかの中にあり、Ｘの最小値、ｘｌがｘｍｉｎ１０６
として記憶される。

行６０７０〜６１２１は、線１２１〜１２４がどの８分
円領域に入るかを決定する。論理は、Ｘｌ又はＸ２のど
ちらが大きいが、ｙｌ又はｙ２のどちらが大きいか、ｙ
ｌ又はｙ２のどちらが大きいか、及び傾斜の相対的な符
号に応じて分岐する。

これらの３つの変数に依存して、８つの異なった場合が
存在する。そして線が引がれる８分円領域が、Ｂｒｅｓ
ｅｎｈａｍ定数ａ及びｂと共定数室備される。

行６１２４，６１２５．６１２６はａ及びｂの結果を受
は取り、さらに３つのＢｒｅｓｅｎｈａｍ定数を生成す
る。ｂマイナスａ　（ｂｍａ）と呼ばれる定数はｂ−ａ
の２倍に等しい。ｂ２定数はｂの２倍に等しい、ｉ定数
はエラ一定数であり、２掛けるｂマイナスａマイナスｘ
　２　（ｘ　１に等しい。項Ｘ２〈Ｘｌは丸めを正しく
させるので、多角形をトラバースする方向に無関係に同
じ点が選択される。

この例は第１０図に示されている。

典型的には、Ｂｒｅｓｅｎｈａｍ線は１方向のトラバー
スする点により引かれ、点が反対方向にトラバースされ
るならば同じＢｒｅｓｅｎｈａｍ線は生じない。これを
示す単純な方法は、第１０図に示すような１／２に等し
い傾斜を持つ線８である。もし線が（Ｏｌｏ）、画素８
１でスタートし、（２，１）、画素８４で終了するなら
ば、理想的な線は画素８２と８３との間にある。Ｂｒｅ
ｓｅｎｈａｍアルゴリズムはそのような場合、繰り上げ
を行なう。従って、線が第１の８分円領域にあれば画素
８２の代りに画素８３がオンになる。従ってＢｒｅｓｅ
ｎｈａｍ線は画素８１．８３．８４から成る。この同じ
線が第５の８分円領域に存在するかのように描かれるな
らば、スタート位置は（２，１）であり、終点は（０，
０）である。反対方向に進むと、繰り上げにより画素８
２が選択される。どちらの方向に引かれる同じ線も同じ
点から成る事を保証するように、方向に無関係に丸めは
常に同じに強制される。

行６１２８から始まるｇｅｎｌｉｎｅアルゴリズムの残
りは、線１２１〜１２４がどの８分円領域に入るかに依
存する８つの異なった場合をカバーする。

例えば、８全円領域■の場合、線は８分周領域Ｉ、■、
■、■に関して以前に定義したように上昇している。従
ってｇｅｎｌｉｎｅアルゴリズムは各ｙに関してＸの最
大値を記憶しようとする。第１の点１４１（第１図）は
ループ中で除外される。ループはｘ１＋１に等しいＸで
開始する。このループはＸがｘ２に等しいか又はそれよ
りも小さい限り実行される。もしエラー係数がゼロより
も小さければ、これはその値が、次の走査線へ移動する
のに充分な程に大きくなかったことを意味する。定数ｂ
２がｉに加算され、再びループが実行される。

もしｉがゼロに等しいか又はそれよりも大きければ、こ
れは半分の点を越え次の走査線がアクセスされることを
意味する。この場合、以前の走査線上の以前の値（ｘ　
−１）　４２　、４４．４６等は。

以前のｙの値に関するｘｍａｘ１０７として表中に保存
される。従って、行６１２９〜６１３９の間のコードは
、各走査線１３２の最後の最大値４２゜４４．４６を記
憶している。走査線１３２の終端に到達し且つ何の値も
まだ記憶されていないという特別な場合も存在する。こ
の場合、その走査線に関する最後のｙ値（ｆｏｒループ
が既にＸを増計数しているのでｘ−１により表わされる
）が記憶される。

他の場合の全ても、以前の走査線から最後の画素を記憶
する。多角形１２０の各線１２１〜１２４毎に、ｇｅｎ
ｌｉｎｅアルゴリズムが呼び出される。

インプリメントされたアルゴリズムの一部は、線がどの
８分円領域に存在するかに依存する。

ｇａｎｌｉｎｅアルゴリズムは、多角形１２０の各線１
２１〜１２４に関する各走査線毎に１つの画素位置１３
０しか記憶しない。これは実行しなければならない記憶
動作の数を最小限にする。多角形は厳密に凸なので、各
走査線１３２毎に正確に１つの最小値１０６と最大値１
０７が記憶される。

−膜内なプログラムｆｆｐｆｌ　（表１）は主ドライバ
・プログラムである。このプログラムのｃａｓｅ　５に
おいて（行４１３６）、第１の多角形充填ルーチンｇｓ
ｆｆ　（表２）に対する呼び出しが存在する。

次にプログラムｇｓｆｆはｇｅｎｌｉｎｅ　（表３）を
呼び出す。プログラムｆｆｐｆ　１のｃａｓｅ　６の場
合は、第２の多角形充填アルゴリズムｇｓｆｆ２　（表
４）に対する呼び出しが存在する。もし第２の多角形充
填アルゴリズムｇｓｆｆ　２の条件が満たされると、ｇ
ｓｆｆ　２は第２のｇｅｎｌｉｎｅプログラムｇｅｎｌ
ｉｎｅ　２　（表５）を呼び出す（表４の行７０９９）
。

第２の多角形充填ルーチンｇｓｆｆ　２は、特定の多角
形が第２の多角形充填アルゴリズムの適用可能な多角形
の範囲内にあるか否かを見るために検査される。このテ
ストは第１多角形充填アルゴリズムのためのテストより
も単純である。というのは第２の多角形充填アルゴリズ
ムのためのテストはｙ方向の一部テストしか含まない（
表４　行７０５６〜７０７０）からである。多角形のｙ
値が増加し次に減少すれば、その多角形はこの第２の多
角形充填アルゴリズムにより充填できる。

閉じた多角形上の任意の場所から出発し、ｙ２−ｙｌの
代数的符号が２又は３回変化するか否かを検査する。こ
れはｙ旧姓の条件を与える。即ち、ｙの任意の値に関し
て、ただ１本だけの連続な充填線１３３が存在する（第
６Ａ図〜第６ＡＣ図）。

水平線は以前の線と同じ符号を持つものと考えられる。

また、最大及び最小のｙ値は同時に記録される（行７０
６０〜７０６３）。多角形がテストに失敗すると（行７
０６９〜７０７０）、標準的なＧＳＬ多角形充填アルゴ
リズムが、第２の多角形充填ルーチンｇｅｎｌｉｎｅ　
２の代りに使用される。

この−周テストに関して第１１Ａ図を参照し、頂点Ｐか
ら出発して時計回り２５に進む時、Δｙ符号の変化が記
録される。頂点Ｐから頂点Ｑに進むと、Δｙは正である
。頂点Ｑから頂点Ｒに進むと、Δｙは負である。頂点Ｒ
から頂点Ｓに進むと、Δｙは負である。頂点Ｓから頂点
Ｔに進むと、Δｙは負である。頂点′ｒから頂点Ｕに進
むと、Δｙは正である。頂点Ｕから頂点Ｐに進むと、Δ
ｙは正である。Δｙの変化を分析すると、それは３回符
号を変えている。もし多角形が一部テストに合格すると
、異なった符号変化は正しく２又は３回である。第１１
Ａ図のこの同じ多角医において、もし多角形６１が頂点
Ｔから開始して時計回りの方向２５にトラバースされる
と、符号変化のカウントは２である。頂点Ｔから頂点Ｑ
まで、全てのΔｙは正であり、時計回りに頂点Ｑから頂
点Ｔまで、全てのΔｙは負である。

Δｙの符号変化の各群のカウントが３よりも大きければ
、多角形は第１１Ｂ図に示すように一部テストに失敗す
る。第１１Ｂ図の多角形６２は、多角形が頂点Ｖから出
発して時計回りにトラバースされるΔｙの符号に４つの
異なった変化を示す。

第１１Ｂ図に示される多角形６２は、この第２の多角形
充填アルゴリズムを用いて充填できない多角形を示して
いる。この多角形６２は点５及び点６の間に示すように
１本の走査線を用いて充填することができない。点５及
び点６の両者は同じｙ値１０２を有している。にもかか
わらず、多角形６２を充填するのに２本の異なった線１
３４．１３５が必要である。

第２の多角形充填アルゴリズムは第１１Ｂ図の多角形６
２の特性を有する多角形を充填するように修正できるが
、アルゴリズムはより複雑になる。

例えば、アルゴリズムは２組の最小値及び最大値を設け
それらの値を初期化することによって拡張できる。しか
し、アルゴリズムはより複雑になり且つアルゴリズムの
一般性は失われる。

第１１Ｃ図に示される多角形６３は厳密に凸ではないが
、第２の多角形充填アルゴリズムに適合する。この多角
形６３は、Ｘ方向に凹部を有する。

しかしこの多角形は一部テストに合格する。多角形を頂
点Ｊから出発して時計回り２５にトラバースすると、頂
点Ｊから頂点ＫまでΔｙは正である。

△ｙの符号は頂点Ｋから頂点りまで及び頂点りから頂点
Ｍまで正である。次にΔｙの符号は頂点Ｍから頂点Ｊま
で正である。出発位置に無関係に、△ｙの符号に２又は
３の変化が存在する。この多角形は各ｙ値１０２毎に１
本のｙ走査線１３２により充填できる。

もし多角形が一部テストに失敗すると、第２の多角形充
填アルゴリズムの代りに標準的なＧＳＬ多角形充填アル
ゴリズムが使用される。もし−周テストに合格すると、
ｇｓｆｆ　（表４）は行７０９９で第２の多角形充填ア
ルゴリズムｇｅｎｌｉｎｅ　２　（表５）を呼び出す。

ｇｅｎｌｉｎｅ　２はｇａｎｌｉｎｅに類似している。

しかし、走査線上の最後の点を記憶する代りに、それは
走査線の最初と最後の点を記憶する。行８０６２．８０
６３で、ｇｅｎｅｌｉｎｅ　２はｇｅｎｌｉｎｅと同様
に傾斜を計算する。行８０７２と８１２１との間にはｇ
ｅｎｌｉｎｅと同様の８分円領域論理が存在する。行８
１２６〜８１２８はＢｒｅｓｅｎｈａｍアルゴリズムと
同じ初期化を行なう。行８１３９以下には、Ｘ＝ｘ＋１
からＸ≦ｘ２までの同じｆｏｒループが存在する。もし
行８１４０でｉがゼロよりも小さければ、これは何も変
化していないことを意味する。

ｉ　＝　ｉ　十ｂ　−ａ時、　ｔａｂｌｅ＋　１に、Ｘ
の以前の最大値が記憶される。即座に、ｔａｂｌｅは増
計数され、新しい走査線上にあるＸの現在値も記憶され
る。

任意の走査線に関して、充填線は、２つの配列に記憶さ
れている値の最小の最小値から最大の最大値へ引かれる
。

第１図を参照すると、第２の多角形充填アルゴリズムｇ
ｅｎｌｉｎｅ　２は、ｙが最小値１を有する点から開始
する。各線１２１〜１２４毎に、各走査線１３２上の最
小値及び最大値が第８図の２つの表１１１．１１２に保
存される。各表１１１．１１２は各ｙの値１０３毎に２
つのエントリ１１６゜１１８を有する。ｙｍｉｎｌとｙ
　ｍａｘ　２との間の時計回りの線１２１．１２２に関
しては、第２の表１１２中にエントリが形成される。ｙ
　ｍａｘ　２とｙ　ｍ１ｎ１との間の、反時計回りの線
１２３．１２４に関しては、第１の表１１１にエントリ
が形成させる。

多角形１２０を上方ヘトラバースする時、表８１１２が
使用され、多角形１２０を下方ヘトラバースする時、表
Ａ１１１が使用される。このルーチンでは第１の多角形
充填アルゴリズムよりも多くの記憶及び処理が行なわれ
る。従って第２の多角形充填ルーチンは第１の多角形充
填ルーチンよリも低速になる。しかし、その利点は、そ
れが大きなりラスの多角形を充填できることである。そ
れにもかかわらず、第２の多角形充填ルーチンは一般的
な多角形充填アルゴリズムよりも高速であり、処理時間
が短かい。

表１１１，１１２を埋めた後、複数ライン描画ルーチン
が呼び出される（行７１１１〜７１１２）。

これは範囲ｙｍｉｎｌ〜ｙｍａｘ２にｙ毎に水平線１４
２を引くためである。このルーチンは、ＧＳＬ複数ライ
ン・ルーチンを呼び出す前に、行７１０４で、２つの表
１１１，１１２を組み合せて１つの表にする。組み合せ
は、各走査線毎に２つの最大値のうち最大のもの及び２
つの最小値のうち最小のものを見つけることより成る。

またその代りに、複数ライン・ルーチンは、両者の表１
１１．１１２へのポインタを受は取り、各走査線毎にｍ
ｉｎ及びｍａｘを形成するように書かれることも可能で
ある。

多角形１２０を上方ヘトラバースする時、各走査線１３
２上の最初の画素４１．４３．４５及び最終の画素４２
．４４．４６が記憶される。これが終了すると、Ｂ配列
１１２に各走査線１３２に関するＸの最小値及び最大値
が記入される。多角形１２０を下方ヘトラバースする時
、各走査線１３２に関するＸの最小値及び最大値がＡ配
列１１１に記憶される。凸性の要求により、上昇及び下
降時に正確に１本の線が存在する。最終的な後処理とし
て、両者の配列に対するポインタがデイスプレィに送ら
れるか、又は後処理装置が最小の最小値及び最大の最大
値を各走査線毎に決定し、これがデイスプレィに送られ
る。

本発明を特定の実施例に則して説明してきたが、種の変
更が可能なことはいうまでもない。例えば、Ｘ及びＸ方
向を参照しながら本発明を説明したが、その方向は交換
してもよい。従って本発明はＸ方向の代りにＸ方向に走
査線を有する事によって動作する任意のデイスプレィに
適用できる。

右６１　　　　　　　　　や −（′Ｊ　ｒｎゞ４０ゝ０■０−〜ｒマ。ψ８の。０−
０゜ワー。、。。（（）　（）　（）　（）　（）（）
　（）　（）　Ｏ＋＋Ｐ−−−＋＋＋＋　＋＋　−−（
’Ｊ　（％Ｊ　（’Ｊ　（％Ｊ　Ｃ％Ｊ　（’Ｊ　（％
Ｊ　（’Ｊ　Ｃ％Ｊ　（％Ｊ　Ｔ’０００００００００
０００００００００００００００　Ｃｌ００００Ｃ’？
？？？臂ぐ！寸臂寸！！マ！ぐぐ守ぐぐママ豐マママ寸
ぐ寸寸〜【−４どｕｂｆ　ｇｓｌ　ａｎｄ　Ｈｐｌ　ａｒｅ　ｅｑｕａｌ　　
４／参本　　　　　　　　　　　　　　　　・−５１６
ス　＃１ｆｄｓｆ　Ｇ！；１ ”　ｙｍｉｎｌ、　ａｙｓ［２’　ｙｍｉｎｌ　ｌ；、
４６９− ＼　　−鴫牢　　へ！　ω −ω　　　− ζ カ０＋＋−〜ｎ！ＧψＮの（ＦＩ　ＯＷ〜哨ぐいφトω
Φ０！〜っ望０’−ト１’−１”−ｒ”−トトトトトω
のωωのωのののω■ｃｎ　ｃｎ　ｃｎΦ）ＯＯＯＯｏ
ｏｏｏｏｏｏｏｏ（）ＯＯＯＯＯＯＯＯＯ００ｐψψψ
ψＷψψψψψψψψψψψφψψψψψΦψψＣｒ１Ｏ？〜−寸む■トｃｏｃｎ　ｏ−〜つ望ＯψトのΦ
０１へＯ（ｎ　Ｏ’ｌ　ａｎ　ｃｙｔ　（ｎ　ｃｎ　ｃ
ｎ　ｃｎ　ｃｎ　ｃｙｔ　ＯＯＯ００００００Ｑ　−−
−６３ご５Ｊ〕；ごごＪ５認認認認淵氾さ８認さ認鑓ト
　　　　　　　　　　　　　φ Φ牢　　　　　　　　　　　　　　　ｔｎ　　　　　　
　　　　　　　　　　　　　　　　　　　−１の　　　
　　　　　　　　　　　　　本　　　　　　　　　　　
　　　　　　　　　　　　　　　Ｘ傘ト　　　　　　　
　　　　　　　　　　　　ｖ率　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　へ、　　
　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　−−亨率　
　　Ｊ車　　本

【図面の簡単な説明】

第１図は本発明のアルゴリズムにより充填される多角形
を示す図、第２Ａ図は凸多角形を示す図、第２Ｂ図は非凸多角形を示す図、第３Ａ図及び第３Ｂ図は従来技術の方法により凸と定義
される多角形を示す図。第４Ａ図及び第４Ｂ図は一般的な多角形として分類され
る多角形を示す図、第５Ａ図は本発明が実施される処理システムの図、第５Ｂ図は第５Ａ図の処理システムの論理構造を示す図
、第５Ｃ図は第５Ａ図の処理システムの物理的構造を示す
図、第６Ａ図は第１及び第２の多角形充填アルゴリズムによ
り充填できる多角形の図。第６Ｂ図及び第６Ｃ図は第２の多角形充填アルゴリズム
により充填できる多角形の図、第６Ｄ図は第１及び第２
の多角形充填アルゴリズムにより充填できない多角形の
図、第７図は第１の多角形充填アルゴリズムで使われる配列
を示す図。第８図は第２の多角形充填アルゴリズムで使われる２つ
の配列を示す図、第９図は８分円領域中の多角形を示す図、第１０図はト
ラバースの方向が反転された時の丸め誤差を説明するた
めの図、第１１Ａ図は一周テストに合格し第２の多角形充填アル
ゴリズムにより充填可能な多角形の図、第１１Ｂ図は一
周テストに失敗し第２の多角形充填アルゴリズムにより
充填不可能な多角形の図。第１１Ｃ図は厳密に凸ではないが一周テストに合格し第
２の多角形充填アルゴリズムにより充填可能な多角形の
図である。出願人　　インターナショナ７いビジネス・マシーンズ
φコーホレーｙＭン代理人弁ｒ１士　頓　　宮　　孝　
　−外１名ゴ→ 第５Ａ図 −、ｆ川ｆ−７１ＬＡ　　　　　　　　ヤー、−，，，４１２第
８図第１０図第１１Ａ図第１１Ｃ図

Claims

【特許請求の範囲】グラフィック・ディスプレイ・システムにおいて、複数
の選択可能な画素により定義可能な境界を有する多角形
を充填する方法であって、上記境界を順次に、上記複数の選択可能な画素に沿って
トラバースし、上記トラバース中に、上記多角形の複数の走査線の各々
に関する複数の選択可能な画素の最小値及び最大値を選
択し、上記最小値と上記最大値との間に充填線を描くステップ
を含む多角形充填方法。