JP3552823B2 - 直線描画装置 - Google Patents
直線描画装置 Download PDFInfo
- Publication number
- JP3552823B2 JP3552823B2 JP34472595A JP34472595A JP3552823B2 JP 3552823 B2 JP3552823 B2 JP 3552823B2 JP 34472595 A JP34472595 A JP 34472595A JP 34472595 A JP34472595 A JP 34472595A JP 3552823 B2 JP3552823 B2 JP 3552823B2
- Authority
- JP
- Japan
- Prior art keywords
- sequence
- quotient
- address
- control sequence
- straight line
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Landscapes
- Image Generation (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は、紙の上に直線を描画するＸ−Ｙプロッタや、表示装置の画面に直線を表示する装置、記憶装置の内部に直線を描く作業をする計算装置などに利用することができる直線描画装置に関し、特に、高速な直線描画を可能にするものである。
【０００２】
【従来の技術】
格子状に配置された記憶素子に直線を描画する場合、図２のように、データを書き込むべき格子点として、描画すべき直線に最も近いものが選ばれる。しかし、水平に並ぶ描画点の数は、一般に一定ではない。図２は、直線Ｌの傾きが３／８の例であるが、描画点が水平に３個と２個並ぶ場合が出現する。
【０００３】
従来、このような点、即ち、垂直格子線上で直線に最も近い点を算出する方法としてＤＤＡ（Ｄｉｇｉｔａｌ Ｄｉｆｆｅｒｅｎｃｉａｌ Ａｎａｌｙｓｉｓ）及びＢｒｅｓｅｎｈａｍのアルゴリズムがよく知られている。後者は前者における積算誤差を取り除く方式である。これらについての説明は、例えばＷ．Ｍ．Ｎｅｗｍａｎ ＆ Ｒ．Ｆ．Ｓｐｒａｕｌｌ著“Ｐｒｉｎｃｉｐｌｅ ｏｆ Ｉｎｔｅｒａｃｔｉｖｅ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ” ＰＰ２５−２７，１９８１に詳しく述べられている。
【０００４】
これらの方式は描画点のＸ座標とＹ座標とを逐次的に算出するものである。そのアルゴリズムをプログラムの形にした一例を図３に示す。図３では従来一般的に利用されているＤＤＡに従って描画点の座標Ｘ，Ｙを計算する。図中のｐｌｏｔ（Ｘ，Ｙ）は座標（Ｘ，Ｙ）に一点を描画する関数であり、描画する直線の傾きはＭ１／Ｍ０であるものとする。これから分かるように、描画点１個につき２回の加算（第４行、第５行）と１回の判定（第６行）、更に数点につき１回の減算（第８行）が必要である。
【０００５】
図３のアルゴリズムを図４を用いて更に詳しく説明する。図４は図２の中の一つの描画点の付近を拡大した図である。点Ｔｎは真の点、即ち、直線Ｌと垂直格子線との交点である。描画点Ｐｎは真の点Ｔｎに最も近い格子点である。従って点ＴｎからＰｎまでのＹ座標の差をＲｎとすると、
−１／２≦Ｒｎ＜１／２ （１−１）
である。但し、説明の簡単のため、格子間隔は縦、横とも１とする。Ｔｎ＋１とＴｎとのＹ座標の差はＭ１／Ｍ０であるから
Ｒｎ＋１＝Ｒｎ＋Ｍ１／Ｍ０， （Ｒｎ＋Ｍ１／Ｍ０＜１／２のとき） （１−２）
Ｒｎ＋１＝Ｒｎ＋Ｍ１／Ｍ０−１，（Ｒｎ＋Ｍ１／Ｍ０≧１／２のとき） （１−３）
という関係が成立する。以上の事実に基づき、描画点のＸ，Ｙ座標を計算する手法の一つが図３に掲げたＤＤＡのアルゴリズムである。
【０００６】
図３の第１行は、変数Ｒｎの初期値を設定するものである。第２行と第１０行は対になっており、ｉを１から１ずつ増加させながら第３行から第９行までをＭ０回繰り返すことを意味している。第３行は、点Ｐｉ、即ち座標（Ｘｉ，Ｙｉ）に点を描画すること、即ちデータを書き込むことを意味する。第４行は、次の描画点のＸ座標を計算する、即ちＸ座標を１だけ増加することを意味する。つまり、第３行で描画した点の次の点、即ちＰｉ＋１のＸ座標が求められる。第５行は残差ＲｍをＭ１／Ｍ０だけ増加することを意味する。格子間隔は１と仮定しているのでＸが１だけ増加するとＹ座標はＭ１／Ｍ０だけ増加する。Ｒｍは直線Ｌと格子線との交わる真の点のＹ座標の少数部分である。従って、第６行で残差が１／２より大きくなったか否かを調べ、もし１／２より大きければ、第７行で座標を１だけ増加し、第８行で残差から１を減ずる。
【０００７】
実際にはこれを改良したＢｒｅｓｅｎｈａｍのアルゴリズムが多く利用されている。図３のプログラムを実際の計算機で実行する場合には図３の第５行で加算されるＭ１／Ｍ０は有限の長さのレジスタに保持される。従ってこの値には丸め誤差が入り込む場合がある。Ｂｒｅｓｅｎｈａｍのアルゴリズムは、この誤差が発生しないようにしたものである。
【０００８】
【発明が解決しようとする課題】
図３のようなアルゴリズムで直線を描画する場合、座標計算には以下の４つの操作が必要であった。即ち、
（１）一描画点当りＸ座標計算のための加算１回
（２）一描画点当りＹ座標計算のための加算１回
（３）一描画点当りＹ座標の残差の大きさの判定１回
（４）数個の描画点につき１回の減算
が必要であった。従って、描画すべき点の数の２倍の加算操作、描画点と同数の判定操作、及び描画点数よりは少ないが描画点数に比例した回数の減算操作が必要であった。そのため、計算に多くの時間を要し、描画作業の高速化には限界があった。
【０００９】
本発明は、こうした従来の問題点を解決するものであり、高速で直線を描画することができる直線描画装置を提供することを目的としている。
【００１０】
【課題を解決するための手段】
そこで、本発明の直線描画装置では、直線の傾きを整数比Ｍ１／Ｍ０で表現した場合に、Ｍ１とＭ０とをそれぞれ保持する第１及び第２の整数保持手段と、Ｍ１とＭ０とから商数列（即ち、Ｍ０をＭ１で除算したときの商がＱ１、余りがＭ２であるとき、次にＭ１をＭ２で除算して、その商Ｑ２と、余りＭ３とを求め、これを順次繰り返して得られるＱ１，Ｑ２，Ｑ３，‥の数列）を計算する商数列計算手段と、この商数列から、隣接する描画点間の格子点上の差異を表す制御数列（即ち、右隣の描画点のＹ座標と１だけずれている場合に“１”、ずれが無い場合に“０”と表した数列）を計算する制御数列計算手段と、この制御数列から描画点の座標を計算する座標計算手段とを設けている。図２の下部に制御数列の例を示す。
【００１１】
この装置では、この制御数列を簡単に求めることによって、従来に比べて少ない操作で描画点の座標を求めることができ、高速での直線描画が可能となる。
【００１２】
【発明の実施の形態】
本発明の請求項１に記載の発明は、格子点上に直線の近似点を描画する直線描画装置において、直線の傾きを定める第１及び第２の整数をそれぞれ保持する第１及び第２の整数保持手段と、第１及び第２の整数保持手段に保持された２つの整数による除算で商と余りとを求め、次に、先行する除算の除数を被除数とし、余りを除数とする除算を繰り返して各除算の商から成る商数列を計算する商数列計算手段と、この商数列から、隣接する描画点間の格子点上の差異を表す制御数列を計算する制御数列計算手段と、この制御数列から描画点の座標を計算する座標計算手段とを設け、前記商数列計算手段は、前記商数列を求める際、除算の結果の余りが生じた場合、除算の余りが０になるまで計算を繰り返すようにしたものであり、商数列の計算、制御数列の計算、及び、制御数列を基に１描画点当たり２回の加算、によって描画点の座標を求めることができる。
【００１３】
請求項２に記載の発明は、前記商数列計算手段が、被除数を保持する被除数保持手段と、除数を保持する除数保持手段と、被除数保持手段に保持された被除数を除数保持手段に保持された除数で除算する除算手段と、この除算における商を保持する商数列保持手段と、この除算における余りを保持する余り保持手段と、余り保持手段の内容がゼロであることを検出するゼロ検出手段とを具備し、被除数保持手段及び除数保持手段が最初にそれぞれ第１の整数及び第２の整数を保持し、除算手段の除算が行なわれた後、除数保持手段の内容を被除数保持手段に転送し、余り保持手段の内容を除数手段に転送して、除算手段の次の除算を行ない、これを余り保持手段の内容がゼロとなるまで繰り返すようにしたものであり、これにより、制御数列の計算の基礎となる商数列を生成することができる。
【００１４】
請求項３に記載の発明は、前記制御数列計算手段が、生成された制御数列を記憶する制御数列記憶手段と、制御数列記憶手段の第１のアドレスを保持する第１のポインタと、制御数列記憶手段の第２のアドレスを保持する第２のポインタと、商数列を記憶する商数列記憶手段とを具備し、制御数列記憶手段の０番地から第１のポインタの指示する番地までの内容を複製の単位として、商数列記憶手段から読出した商数列要素の値の回数だけ複製して、制御数列記憶手段の第２のポインタが指示する番地の次の番地から始まる領域に格納し、第２のポインタの保持するアドレスを格納後の最終番地に変更し、第１のポインタの保持するアドレスを、次の複製の単位となる番地に変更し、この動作を、商数列記憶手段に記憶された商数列要素について１回ずつ繰り返すようにしたものであり、これにより、商数列を用いて制御数列を生成することができる。
【００１７】
以下、本発明の実施の形態について、図面を用いて説明する。
【００１８】
本発明の直線描画方法は、新しく発明された数学的理論に基づいているので、次のような順で説明を行なう。即ち、
第１節 本発明の直線描画装置で使用される数学的概念の説明
第２節 本発明の直線描画装置の実施の形態とその動作説明
第３節 数学的証明
の３節に分けて説明する。
【００１９】
第１節 本発明の直線描画装置で使用される数学的概念の説明
本発明の描画装置は、図２に示すように、直線を描画するための制御数列Ｃｎを簡単な操作で生成することによって、高速な描画を達成するものである。この制御数列は、一つの描画点の左に隣接する描画点が水平方向に存在するときに０、また、左に隣接する描画点が斜め方向に存在するときに１と表現した数列である。図４の直線Ｌの近似点ＰｎのＸ座標とＹ座標とは、制御数列Ｃｎから次のようにして算出することが出来る。即ち、
Ｘｎ＝Ｘｎ−１＋１ （２−１）
Ｙｎ＝Ｙｎ−１＋Ｃｎ−１ （２−２）
上記の式（２−１），（２−２）はＣｎがゼロであればＰｎはＰｎ−１の右隣り、Ｃｎが１であればＰｎはＰｎ−１の右上となることを示している。
【００２０】
式（２−１）と（２−２）から明らかなように、予め制御数列が知れていれば、一点を描画するのに２回の加算だけが必要で、判定は不要である。しかも、これらの加算は１または０を加えるという単純な整数演算である。この制御数列Ｃｎは、以下に述べる商数列から生成することができる。
【００２１】
１．１ 商数数列の定義
制御数列は、別の新たな数列（以下、商数列と呼ぶ）から生成することができる。商数列とは次のようにして求められる数列である。即ち直線Ｌの傾きをＭ１／Ｍ０とする。但しＭ１，Ｍ０は整数とする。このときまず、
Ｍ０＝Ｑ１Ｍ１＋Ｍ２， Ｍ１＞Ｍ２＞０ （２−３）
を満足する整数Ｑ１、Ｍ２を求める。以下
Ｍｎ−１＝ＱｎＭｎ＋Ｍｎ＋１， Ｍｎ＞Ｍｎ＋１＞０ （２−４）
を満足する整数Ｑｎ、Ｍｎを式（２−５）が成立するまで次々と求める。即ち
ＭＮ−１＝ＱＮＭＮ （２−５）
となるまで、言い換えれば
ＭＮ＋１＝０ （２−６）
となるまで繰り返す。
【００２２】
以上の計算は、Ｍｎ−１をＭｎで割ったときの商と余りをそれぞれＱｎとＭｎ＋１とするものである。以下、このようにして求めた数列Ｑ１，Ｑ２，・・・，ＱＮを商数列Ｑ、数列Ｍ０，Ｍ１，Ｍ２，・・・，ＭＮを除数列Ｍと呼ぶことにする。即ち、
Ｑ＝｛Ｑ１，Ｑ２，・・・ＱＮ｝ （２−７）
Ｍ＝｛Ｍ０，Ｍ１，Ｍ２，・・・ＭＮ｝ （２−８）
である。
【００２３】
なお、ＭＮ＋１＝０となるようなＮは必ず存在する。即ち、Ｍ０、Ｍ１から出発して（２−４）の除算を繰り返すと、最後には余りがゼロになる。なぜならば、Ｍｎは正の整数でありＭｎ＞Ｍｎ＋１であるから、ｎが増加するとともにＭｎはＭｎ−１に比べて小さくなる。従って、最後には次のどちらかの場合に到達する。即ち、
（ア） ＭＮ＝１となり、ＭＮ＋１＝０となる。
【００２４】
（イ） ＭＮ＋１≠１で且つ、ＭＮがＭＮ＋１で割り切れ、従ってＭＮ＋１＝０となる。のどちらかである。従ってＭＮ＋１＝０となるＮが必ず存在する。ＭＮはＭ０とＭ１との最大公約数であることは、ユークリッドのアルゴリズムから明らかである。
【００２５】
１．２ 制御数列の定義
１．１で定義した商数列Ｑから、図２の制御数列Ｃは次のようにして生成することができる。即ちまず、中間の長さの数列Ｃａ，ｎとＣｂ，ｎとを以下のような漸化式で定義する。即ち、
Ｃａ，０＝｛０｝ （２−９）
Ｃｂ，０＝｛１｝ （２−１０）
Ｃａ，ｎ＝｛Ｃｂ，ｎ−１＆（Ｑｎ−１）＊Ｃａ，ｎ−１｝ （２−１１）
Ｃｂ，ｎ＝｛Ｃａ，ｎ＆Ｃａ，ｎ−１｝ （２−１２）
但し、記号＆及び＊は以下のような意味を持つものとする。即ち、有限の長さの数列α、βに対して
α＆βは、数列αの右側に数列βを接続して出来る数列
γ＊βは、数列βをγ個繰り返して出来る数列
を意味するものとする。
【００２６】
このような数列Ｃａ，ｎから式（２−９）〜（２−１２）によって制御数列Ｃを求めることができる。即ち、ＭＮ＋１＝０であるとき
Ｃ＝ＭＮ＊Ｃａ，Ｎ （２−１３）
である。式（２−９）〜（２−１３）が正しいことは「第３節 数学的証明」の項で後述する。
【００２７】
第２節 本発明の直線描画装置の実施の形態とその動作説明
以上の説明から分かるように、制御数列Ｃｎは、商数列、除数列を求める少数回の除算と、（２−９）〜（２−１３）に従って１と０とのビット列をコピーする作業とによって求めることができ、本発明の直線描画装置は、こうして得た制御数列から描画点の座標を計算し、格子点上に直線の近似点を描画する。この具体的方法とそれを実施する装置とについて以下に述べる。但し、直線Ｌの傾きは整数比Ｍ１／Ｍ０であるものとする。
【００２８】
実施形態の直線描画装置は、図１に示すように、直線の傾きを表す２つの整数Ｍ０とＭ１とをそれぞれ保持するレジスタ１０１、１０２と、Ｍ０とＭ１とから商数列を計算する商数列計算装置１０３と、商数列から制御数列を生成する制御数列計算装置１０４と、制御数列から描画点の座標Ｘ、Ｙを計算する座標計算装置１０５との５つの部分から構成される。
【００２９】
直線の傾きを表す２つの整数を保持するレジスタ１０１、１０２の必要な大きさは、直線の傾きの表現精度によって決まってくる。この実施形態では、直線の傾きを整数比Ｍ１／Ｍ０で表現することとしているため、Ｍ１及びＭ０の大きさの数字を保持できればよい。例えば２０００×２０００の画素数を持つ表示装置に適用する場合では、これら２つのレジスタ１０１、１０２は１２ビットあれば十分である。なぜならＭ１及びＭ０の最大値は２０００であるからである。
【００３０】
商数列計算装置１０３は、図５に示すように、被除数を記憶する被除数レジスタ５０１と、除数を記憶する除数レジスタ５０２と、被除数レジスタ５０１から読出した値を除数レジスタ５０２で読出した値で除算する除算器５０５と、除算器５０５で行なわれた除算の剰余を記憶する剰余レジスタ５０４と、剰余レジスタ５０４がゼロであるときにそれを検出して検出信号５１１を出力するゼロ検出装置５０６と、商数列を記憶する商数列記憶装置５０３と、商数列記憶装置５０３のアドレスを指示するアドレスポインタ５０７と、入力する二つの信号の一方を選択して出力するセレクタ５０８、５０９、５１６と、この商数列計算装置１０３の各部の動作を制御する商数列制御装置５１０とを備えている。
【００３１】
この商数列計算装置１０３は、数値Ｍ０とＭ１とから、図８に示すフローチャートに従って商数列を計算し、商数列記憶装置５０３に格納する。
【００３２】
まず、初期状態では、アドレスポインタ５０７はゼロを指定する。また、商数列制御装置５１０は、セレクタ５０８及び５０９の入力信号の選択を指示するセレクタ制御信号５１４としてゼロを設定し、それに応じて、セレクタ５０８及び５０９は両方とも左側の入力、即ち、Ｍ０とＭ１とをそれぞれ選択し通過させる。このことを前提に、商数列計算装置は次のように動作する。
【００３３】
ステップ８０１：商数列制御装置５１０は、信号５１５によりアドレスポインタ５０７の内容をゼロに設定し、また、被除数レジスタ５０１及び除数レジスタ５０２に対してデータの格納を指示する制御信号５１２をＯＮにする。それにより、数値Ｍ０とＭ１とが、それぞれ、セレクタ５０８及び５０９を経由して、被除数レジスタ５０１と除数レジスタ５０２とに格納される。
【００３４】
ステップ８０２：被除数レジスタ５０１に格納された数値Ｍ０と除数レジスタ５０２に格納された数値Ｍ１とは除算器５０５に入力し、除算器５０５はＭ０／Ｍ１を計算し、その商、即ちＱ１を信号５１９によりセレクタ５１６に出力し、余りＭ２を信号５２０により剰余レジスタ５０４に出力する。
この余りＭ２の出力は剰余レジスタ５０４に格納される。ゼロ検出器５０６は、剰余レジスタ５０４に格納されたＭ２の内容がゼロであるか否かを調べ、ゼロである場合には検出信号５１１をＯＮに、ゼロでなければＯＦＦにする。セレクタ５１６は、検出信号５１１がＯＦＦのときは、除算器５０５から出力されたＱ１信号５１９を選択して商数列記憶装置５０３に出力する。一方、商数列制御装置５１０は、商数列記憶装置５０３に対してデータ格納を指示する制御信号５１３をＯＮにする。それにより、商数列記憶装置５０３のアドレスポインタ５０７の指示するアドレスには、除算器５０５の商出力が格納される。
【００３５】
ステップ８０３：ゼロ検出器５０６の出力する検出信号５１１がＯＦＦのとき、つまり、剰余レジスタ５０４の内容がゼロでないときには、
ステップ８０４：商数列制御装置５１０は、アドレスポインタ５０７の内容を１だけ増やすことを指示する信号５１５を出力し、アドレスポインタ５０７は、アドレスを１だけ増加させる。
【００３６】
ステップ８０５：商数列制御装置５１０は、セレクタ５０８と５０９とが両方とも右側の入力をそれぞれ選択するようにセレクタ制御信号５１４を１に設定し、また、制御信号５１２をＯＮにする。その結果、除数レジスタ５０２の内容が被除数レジスタ５０１に転送され、また、剰余レジスタ５０４の内容が除数レジスタ５０２に転送される。
【００３７】
この後、ステップ８０２に移り、剰余レジスタ５０４の内容がゼロになるまで、ステップ８０２、８０３、８０４、８０５の手順を繰り返す。
ステップ８０３において、剰余レジスタ５０４の内容がゼロになり、ゼロ検出器５０６の検出信号５１１がＯＮになると、
ステップ８０６：セレクタ５１６は、左側の入力を選択する。これにより除数レジスタ５０２の内容が、セレクタ５１６を経て、商数列記憶装置５０３に格納され、動作を終了する。
【００３８】
以上の動作により、商数列記憶装置５０３には、図９に示すように、商数列全部が格納され、その後に最後の除算に使用された除数が格納される。
【００３９】
商数列から制御数列を生成する制御数列計算装置１０４は、図６に示すように、生成された制御数列を格納する制御数列記憶装置６０１と、制御数列記憶装置６０１のアドレスを指示するアドレスポインタ６０２、６０３と、商数列記憶装置５０３のアドレスを指示するポインタ６０４と、制御数列計算装置１０４の各部を制御して制御数列記憶装置６０１の中に制御数列を生成する制御数列制御装置６０５とを備えている。なお、商数列記憶装置５０３とそのアドレスを指示するアドレスポインタ５０７とは、図５の５０３及び５０７そのものであり、アドレスポインタ５０７は、商数列記憶装置５０３に格納されたデータの最後のアドレス位置をポイントしている。
【００４０】
この制御数列計算装置１０４の動作を説明する前に、制御数列と商数列との関係を具体例を用いて説明する。
【００４１】
後述するように、直線が７／１８の傾きを有する場合、即ち、Ｍ０の値が１８、Ｍ１の値が７である場合には、描画点は図２０に示すように描かれる。この制御数列は｛１００１０１００１００１０１００１０｝であり、直線に沿ってこの数列の単位が繰返される。水平格子線上に並ぶ描画点の個数は３の場合と２の場合とがあり、制御数列をこの二種類のブロックの組合せとして、「１００」「１０」「１００」「１００」「１０」「１００」「１０」と表すことができる。この「１００」のブロックをＢ１タイプ、「１０」のブロックをＡ１タイプとすると、Ａ１タイプは水平格子線上にＱ１（Ｑ１＝２）個の描画点が並び、Ｂ１タイプはＱ１＋１個の描画点が並んでいる。つまり、商数列の最初のＱ１の値により、Ａ１タイプ及びＢ１タイプのブロックに含まれる描画点の数が決まってくる。
【００４２】
また、制御数列は、このＡ１及びＢ１を用いて、Ｂ１，Ａ１，Ｂ１，Ｂ１，Ａ１，Ｂ１，Ａ１のブロックの連結として表すことができるが、これはＢ１の後に続くＡ１の数が１のブロックと、Ｂ１の後に続くＡ１の数が０のブロックとの組合せ、即ち、「Ｂ１Ａ１」「Ｂ１」「Ｂ１Ａ１」「Ｂ１Ａ１」と表すことができる。この「Ｂ１Ａ１」をＢ２タイプ、「Ｂ１」をＡ２タイプとすると、Ａ２タイプはＱ２（Ｑ２＝１）個のブロックを含み、Ｂ２タイプはＱ２＋１個のブロックを含んでいる。つまり、商数列の次のＱ２の値により、Ａ２タイプ及びＢ２タイプに含まれるブロック数が決まってくる。
【００４３】
また、制御数列は、このＡ２及びＢ２を用いて、Ｂ２，Ａ２，Ｂ２，Ｂ２のブロックの連結として表すことができるが、これはＢ２の後に続くＡ２の数が１のブロックと、Ｂ２の後に続くＡ２の数が０のブロックとの組合せ、即ち、「Ｂ２Ａ２」「Ｂ２」「Ｂ２」と表すことができる。この「Ｂ２Ａ２」をＢ３タイプ、「Ｂ２」をＡ３タイプとすると、Ａ３タイプはＱ３（Ｑ３＝１）個のブロックを含み、Ｂ３タイプはＱ３＋１個のブロックを含んでいる。つまり、商数列のその次のＱ３の値により、Ａ３タイプ及びＢ３タイプに含まれるブロック数が決まってくる。
【００４４】
また、制御数列は、このＡ３及びＢ３を用いて、Ｂ３，Ａ３，Ａ３のブロックの連結として表すことができるが、これはＢ３の後にＡ３が２つ続く１つのブロックである。これをＡ４タイプとすると、Ａ４タイプはＱ４（Ｑ４＝３）個のブロックを含んでいる。つまり、商数列のその次のＱ４の値により、Ａ４タイプに含まれるブロック数が決まってくる。
【００４５】
この段階のＡ４のように、Ｂ４に対応するブロックが存在しない状態は、商数列の算出において剰余が０の状態に相当している。このときＡ４×Ｍ（Ｍは除数レジスタ５０２の内容。この具体例の場合Ｍ＝１）が制御数列となる。
【００４６】
さて、制御数列計算装置１０４の制御数列制御装置６０５は、商数列とこのような関係にある制御数列を、商数列記憶装置５０３に格納されている商数列を用いて、制御数列記憶装置６０１の中に生成する。その手順を図１０及び図１１に示すフローチャートを用いて説明する。
【００４７】
ステップ１００１：制御数列制御装置６０５は、制御数列記憶装置６０１の第１ワード（即ちアドレス０）に“１”を書き込む。更に商数列ポインタ６０４の内容を０に設定する。これによりアドレスポインタ６０４は、商数列記憶装置５０３の第１番地、即ちＱ１が格納されている番地を指示する。
【００４８】
ステップ１００２：制御数列制御装置６０５は、アドレスポインタ６０４の指示するアドレスを読み出し（この場合はアドレス０を読むことになるのでＱ１が読み出される）、制御数列記憶装置６０１の第２ワード（即ちアドレス１）から、今読み出された値の個数だけ、即ち、Ｑ１個だけの語にデータ“０”を書き込む。
【００４９】
ステップ１００３：次いで、制御数列制御装置６０５は、アドレスポインタ６０２に数値Ｑ１−１を、アドレスポインタ６０３に数値Ｑ１を書込み、
ステップ１００４：アドレスポインタ６０４の内容を１だけ増加する。
【００５０】
このときの制御数列記憶装置６０１の内容とアドレスポインタ６０２及びアドレスポインタ６０３のポイント位置とを図１２に示している（アドレス０からポインタ６０２の指し示すアドレスＱ１−１までのデータが、先の具体例のＡ１タイプのデータであり、アドレス０からポインタ６０３の指し示すアドレスＱ１までのデータがＢ１タイプのデータとなる）。
【００５１】
次に、制御数列制御装置６０５は、図１１に示す手順に従って、
ステップ１１０１：商数列記憶装置５０３からポインタ６０４の指示する番地を読出す。この時読み出される値は、これまでに読み出された商数列の次の要素である。この値をＱｎとする。
【００５２】
ステップ１１０２：制御数列記憶装置６０１の先頭番地、即ち、０番地からアドレスポインタ６０２が指示する番地までの内容をＱｎ回繰り返して、アドレスポインタ６０３の指示する番地の次の番地から始まる領域にコピーする（この操作は、先の具体例において、ブロックＢｎ−１の後にブロックＡｎ−１をＱｎ回繋げてブロックＢｎを生成することに相当している）。この動作を図示したものが図１３である。即ち、ゼロ番地からポインタ６０２が指示する番地までの内容をＣａ，ｎとすると、Ｃａ，ｎをＱｎ繰り返してアドレスポインタ６０３の指示する番地の次から始まる領域へコピーする。
【００５３】
ステップ１１０３：アドレスポインタ６０３には格納最終番地を格納する。即ち、アドレスポインタ６０３は破線で示した番地を指示することになる（アドレス０からアドレスポインタ６０３のポイントする番地までのデータが先の具体例におけるブロックＢｎのデータとなる）。更に、アドレスポインタ６０３から以前のアドレスポインタ６０２の内容を減じた値に更に１を減じた値をアドレスポインタ６０２に格納する。即ち、アドレスポインタ６０２は図１３の破線で示した番地を指示するようになる（アドレス０からアドレスポインタ６０２のポイントする番地までのデータが先の具体例におけるブロックＡｎのデータとなる）。この段階で０番地からアドレスポインタ６０２の指示する番地までの内容がＣａ，ｎ＋１、０番地からアドレスポインタ６０３の指示する番地までの内容がＣｂ，ｎ＋１となっている。この後、アドレスポインタ６０４の内容を１だけ増加する。
【００５４】
ステップ１１０４：ポインタ６０４の内容とポインタ５０７の内容とを比較し、不一致であればステップ１１０１へ移行する。一致した場合は、
ステップ１１０５：既に商数列のすべての要素についてステップ１１０１〜ステップ１１０３を実行したことになる。従って、式（２−１３）を計算する過程に移行する。ポインタ６０４が指示している番地を読み出す。即ち、ＭＮが読み出される。
【００５５】
ステップ１１０６：制御数列記憶装置６０１の０番地からアドレスポインタ６０２の指示する番地にはＣａ，Ｎが格納されている。従って、これをＭＮ−１回繰り返してアドレスポインタ６０２の指示する番地の次の番地から始まる領域に格納する。これにより、ＭＮ＊Ｃａになる。
【００５６】
ステップ１１０７：最終格納番地をアドレスポインタ６０２に格納する。これにより、０番地からアドレスポインタ６０２の指示する番地までの内容が制御数列Ｃとなる。
【００５７】
こうして生成された制御数列記憶装置６０１の内容の内、０番地からポインタ６０２の指示する番地までに格納されたデータが求める制御数列となる。
【００５８】
制御数列から描画点の座標Ｘ、Ｙを計算する座標計算装置１０５は、図７に示すように、制御数列記憶装置６０１のアドレスを指示するポインタ７０１と、制御数列記憶装置６０１から読みだされたデータを格納するバッファ７０２と、描画点のＸ座標を保持するレジスタ７０４と、描画点のＹ座標を保持するレジスタ７０５と、バッファ７０２から出力された値とレジスタ７０５から出力された値とを加算する加算器７０３と、座標計算装置の各部を制御する座標計算制御装置７０６とを備えている。なお、制御数列記憶装置６０１及びアドレスポインタ６０２は、図６の６０１及び６０２そのものであり、アドレスポインタ６０２は制御数列記憶装置６０１の最終格納番地を指し示している。
【００５９】
座標計算制御装置７０６は、制御数列記憶装置６０１から制御数列の要素を最初から一つずつ読み出し、これを基に描画点の座標（Ｘ，Ｙ）を出力する。その動作をフローチャートにしたものが図１４である。以下、図１４に沿って動作を説明する。但しレジスタ７０４と７０５には、それぞれ（Ｘ，Ｙ）の初期値、即ち最初の描画点の座標が格納されているものとする。
【００６０】
ステップ１４０１：ポインタ７０１をゼロに設定する。これによりポインタ７０１は制御数列記憶装置６０１の先頭番地を指示することになる。
【００６１】
ステップ１４０２：座標計算制御装置７０６は、ポインタ７０１の指示する番地を読み出すための制御信号７１０をＯＮにして、その読み出されたデータをバッファ７０２に格納する。
【００６２】
ステップ１４０３：座標計算制御装置７０６は、信号７１１をＯＮにする。これによりレジスタ７０４は格納している値を１だけ増加する。同時にレジスタ７０５は、加算器７０３から出力された値、即ち、レジスタ７０５がそれまで保持していた値にバッファ７０２の内容を加えた値を格納する。バッファ７０２の内容は０または１であるので、レジスタ７０５の内容は元のままの値かあるいは１だけ増加した値となる。
【００６３】
ステップ１４０４：レジスタ７０４と７０５の出力を描画点の座標（Ｘ，Ｙ）として描画する。
【００６４】
ステップ１４０５：座標計算制御装置７０６は、ポインタ７０１とポインタ６０２の保持する値同志を比較する。両者の内容が一致していればステップ１４０１へ移る。内容が一致するということは制御数列の最終要素を使ってステップ１４０２〜ステップ１４０３を実行したことを意味する。
【００６５】
ポインタ７０１とポインタ６０２の内容が不一致である場合は、
ステップ１４０６：ポインタ７０１の内容を１だけ増加し、制御数列の次の要素を読み出す準備をする。この後、ステップ１４０２へ移行する。
【００６６】
以上の動作により、描画点の座標（Ｘ，Ｙ）が次々と生成され出力７１３と出力７１４とに出力される。
【００６７】
以上の動作を具体的数値例を用いて再度説明する。Ｍ０とＭ１の値をそれぞれ１８と７であるとして説明する。この場合、商数列Ｑは以下の計算より式（２−１５）のようになる。この商数列は、４回の除算で生成することができる。
【００６８】
１８＝２×７＋４ より Ｑ１＝２，Ｍ１＝７，Ｍ２＝４
７＝１×４＋３ より Ｑ２＝１， Ｍ３＝３
４＝１×３＋１ より Ｑ３＝１， Ｍ４＝１
３＝３×１＋０ より Ｑ４＝３， Ｍ５＝０
Ｑ＝｛２，１，１，３｝ （２−１５）
図１のレジスタ１０１と１０２とにそれぞれ数値１８と７とが格納されている状態から説明を始める。まず、商数列制御装置５１０は、ステップ８０１とステップ８０２とを実行すると、商数列記憶装置５０３の０番地に数値２が、レジスタ５０４に数値４が格納される。次に、ステップ８０３を実行し、剰余レジスタ５０４の内容がゼロでないのでステップ８０４の実行へ移る。これによりポインタ５０７の内容は１となる。次にステップ８０５を実行すると、レジスタ５０１とレジスタ５０２にはそれぞれ数値７と４が格納される。再度ステップ８０２の実行により、商数列記憶装置５０３の１番地とレジスタ５０４にそれぞれ数値１と３とがそれぞれ格納される。この後、ステップ８０３、８０４、８０５を実行した後、第３回のステップ８０２の実行で商数列記憶装置５０３の２番地に１が、レジスタ５０４に１が格納される。
【００６９】
更にステップ８０３、８０４、８０５を実行した後、第４回目のステップ８０２の実行により、商数列記憶装置５０３の３番地に数値３が、レジスタ５０４に数値０が格納される。この後ステップ８０３を実行すると、剰余レジスタ５０４の値がゼロであるので、ステップ８０６により、レジスタ５０２の内容、即ち数値１が商数列記憶装置５０３に格納される。この後、動作は終了する。この結果、商数列記憶装置５０３には、商数列
Ｑ＝｛２，１，１，３｝
と、その後にＭ４、即ち数値１が記憶され、商数列記憶装置５０３の内容は図１５のようになり、ポインタ５０７は最終要素格納番地、即ち４番地を指示した状態になる。以上の過程をまとめると表１のようになる。
【００７０】
【００７１】
次に、制御数列計算過程の説明に移る。図１５のように、商数列Ｑと除数列Ｍの最終要素ＭＮとが商数列記憶装置５０３に記憶された状態で制御数列制御装置６０５がステップ１００１〜ステップ１００４を実行する。即ち、制御数列制御装置６０５は、商数列記憶装置５０３の先頭アドレスを読み出す。この結果、数値“２”が読み出されるので、制御数列記憶装置６０１は図１６のような状態になる。即ち、０番地に数値１が書き込まれ、その次から２語に数値０が書き込まれた状態になる。ポインタ６０２と６０３にはそれぞれ数値“１”と“２”が保持される。
【００７２】
次に、制御数列制御装置６０５が、再度ステップ１１０１〜ステップ１１０４を実行すると、制御数列記憶装置６０１の内容は図１７のようになる。即ち、ステップ１１０１において商数列記憶装置５０３から読み出される値は“１”であるから、図１７の０番地からポインタ６０２の指示する番地の内容、即ち｛１，０｝が１回だけ３番地から始まる領域にコピーされる。この後、ポインタ６０３には数値４が、ポインタ６０２には数値４−１−１、即ち数値２が格納される。
【００７３】
この後、ポインタ６０４とポインタ５０７の内容が比較される。それぞれには数値１と４が格納されているので、再度ステップ１１０１〜ステップ１１０３が実行される。この結果、制御数列記憶装置６０１の内容は図１８のようになる。
【００７４】
この後、ポインタ６０４の内容は２であるから、第３回目のステップ１１０１〜ステップ１１０３が実行され、制御数列記憶装置６０１の内容は図１９のようになる。この後、ステップ１１０４を実行すると、ポインタ６０４の内容はポインタ５０７と一致する。従って、ステップ１１０５〜ステップ１１０７が実行されるが、Ｍ４の値は１であるのでステップ１１０６は０回繰り返される。従って、制御数列記憶装置６０１の０番地からポインタ６０２の指示する１７番地までの内容が求める制御数列となり、ここで終了する。以上の過程をまとめると表２のようになる。
【００７５】
【００７６】
次に、この結果に基づいて、座標計算装置１０５の動作を説明する。説明を簡単にするため（Ｘ，Ｙ）の初期値は（０，０）とする。一般には最初の描画点Ｐｎ（Ｘ０，Ｙ０）である場合には初期値を（Ｘ０−１，Ｙ０−１）にすれば良い。
【００７７】
まず、座標計算制御装置７０６がステップ１４０１〜ステップ１４０３を実行すると、信号線７１３と７１４とには１と１とが出力される。レジスタ７０４は１だけ増加するから“１”となる。レジスタ７０５にも１が加算されるから“１”となる。これは制御数列記憶装置６０１の先頭番地の内容、即ち１が読み出されるからである。第２回目のステップ１４０１〜ステップ１４０３を実行すると、出力７１３と７１４とにはそれぞれ“２”と“１”が出力される。これは、出力７１３の出力は毎回１だけ増加するが、出力７１４、即ちＹ出力は今回は増加しない。これは制御数列記憶装置６０１の第２ワード、即ち１番地には“０”が書かれているからである。
【００７８】
このようにしてステップ１４０２〜ステップ１４０６のループが繰り返されると、出力７１３と７１４は表３のように変化していく。これを描画点にしたものが、図２０である。
【００７９】
以上のとおり、制御数列が求まると、描画点の座標の計算には加算のみが必要であり、Ｂｒｅｓｅｎｈａｍのアルゴリズムのような条件判定は不要である。また前述したように、商数列を生成するのに必要な除算回数は４回であり、これにより１８個の点が描画できる。
【００８０】
第３節 数学的証明
以上のように、式（２−３）〜（２−１３）によって制御数列を求め、式（２−１）、（２−２）によって描画点の座標を算出する描画方法は、従来の方法（例えば図３の方法）で得られる、直線Ｌの最も良い近似点を表す座標と同一の座標を生成する。このことの数学的説明を以下に述べる。
【００８１】
本発明の描画方法は、式（２−１１）及び（２−１２）の関係が成立することに基盤を置いている。この関係におけるｎ＝１，ｎ＝２，ｎ＝３及びｎが一般の値を取る場合について説明する。
【００８２】
直線Ｌの傾きをＭ１／Ｍ０（Ｍ１、Ｍ０は整数）とする。そしてＭ１、Ｍ０に対して、式（２−３）〜（２−６）が成立しているものとする。図２１のように、直線Ｌを近似する描画点Ｐｉが同一水平格子線上に並ぶ個数をＫ１とすると
Ｋ１＝Ｑ１ （３−１）
または
Ｋ１＝Ｑ１＋１ （３−２）
である。式（３−１）及び（３−２）の証明は後の＜証明１＞に述べる。図２２のように、描画点が水平にＱ１＋１個並んだものをまとめてＢ１タイプのブロックとし、図２３のように、描画点が水平にＱ１個並んだものをまとめてＡ１タイプのブロックと呼ぶことにする。すると、直線Ｌを近似する描画点の集合は、図２４のようにＡ１とＢ１の２種類のブロックを連結したものになる。このようにＫ１が１だけ異なる２つの値を取り得るのは、式（２−４）において、
Ｍ２≠０
の場合である。言い換えれば、Ｍ０がＭ１で割り切れれば、Ｋ１はＱ１の値だけを取る。
【００８３】
図２４のように、Ｂ１タイプのブロックから数えて次のＢ１タイプのブロックが出現するまでのブロックの個数をＫ２とする。言い換えればＡ１タイプのブロックが連続する個数をＫ２−１とすると
Ｋ２＝Ｑ２ （３−３）
または
Ｋ２＝Ｑ２＋１ （３−４）
である。式（３−３）及び（３−４）の証明は＜証明２＞に示す。
【００８４】
従って、タイプＢ１のブロックの次にタイプＡ１のブロックがＱ２個続く場合と、Ｑ２−１個続く場合とが存在する。図２５のように前者をブロックＢ２、後者をブロックＡ２と呼ぶことにする。更に、タイプＢ２のブロックから数えて次のタイプＢ２のブロックが出現するまでのブロック数をＫ３とすると、同様に
Ｋ３＝Ｑ３ （３−５）
または
Ｋ３＝Ｑ３＋１ （３−６）
である。このことの証明は＜証明３＞に述べる。
【００８５】
一般に図２６のように、ブロックＢｍから次のブロックＢｍまでのブロック数をＫｍ＋１とすると、
Ｋｍ＋１＝Ｑｍ＋１ （３−７）
または
Ｋｍ＋１＝Ｑｍ＋１＋１ （３−８）
である。このことを更に厳密に表現すると以下のようになる。即ち、一般に、ある直線Ｌに対して垂直格子線上で最も近い格子点列を次の条件を満たす２つの集合ＡｍとＢｍとに分けることができる。そして、これらのＡｍとＢｍとは、式（２−４）の集合Ｑの要素である整数Ｑｍに対して次の関係を持つ。
【００８６】
Ａｍ＝Ｂｍ−１＆（Ｑｍ−１）＊Ａｍ−１ （３−９）
Ｂｍ＝Ｂｍ−１＆Ｑｍ＊Ａｍ−１ （３−１０）
但し、Ｘ＆Ｙは集合Ｘの右に集合Ｙを接続したものを意味し、α＊Ｙは集合Ｙをα個接続したものを意味する。このことの証明は＜証明４＞に述べる。
【００８７】
このようにＫｍが１だけ異なる２つの値を取るのは、式（２−４）のＭｍ＋１≠０であるからである。このようなプロセスをｎ＝Ｎとなるまで続けることができる。ｎ＝Ｎとなると式（２−４）の余りはゼロ、即ち
ＭＮ＋１＝０
であるから以後、描画点はブロックＡＮだけの繰り返しとなる。
【００８８】
図２６から分かるように、ブロックＡｎはブロックＢｎ−１のうしろにＱｎ−１個のブロックＡｎ−１を接続したものであり、ブロックＢｎはこれにもう一つブロックＡｎ−１を接続したものである。従って、ブロックＡｎとＢｎの制御数列をそれぞれＣａ，ｎ，Ｃｂ，ｎとすると
Ｃａ，ｎ＝Ｃｂ，ｎ−１＆（Ｑｎ−１）＊Ｃａ，ｎ−１
Ｃｂ，ｎ＝Ｃａ，ｎ＆Ｃａ，ｎ−１
即ち、式（２−１１）、（２−１２）を得ることができる。ＭＮはＭ０とＭ１との最大公約数であるからｎ＝Ｎの以後はＡＮの繰り返しとなり、式（２−１３）を得る。
【００８９】
＜証明１＞
図２１のように直線Ｌを近似する描画点Ｐｉ〜Ｐｊが、同一水平線上に並ぶ個数をＫ１とする。直線の傾きは整数比Ｍ１／Ｍ０とする。簡単のため格子間隔は１とする。真の点、即ち、直線Ｌと垂直の格子線と交点をＴｉ〜Ｔｊとする。垂直方向でＴｉに最も近い点、即ち描画点をＰｉとする。真の点ＴｉのＹ座標から描画点ＰｉのＹ座標の値を引いたものをＲｉとし、これを点Ｐｉの残差と呼ぶことにする。点ＰｉからＰｊまでが水平格子線Ｈ１の上にあり、点Ｐｉ−１はＨ０上に、点Ｐｊ＋１はＨ２上にあるとする。真の点Ｔｉと描画点Ｐｉとの位置の差Ｒｉは、
−１／２≦Ｒｉ＜１／２ （４−１）
である。直線の傾きはＭ１／Ｍ０であるから、ＴｉのＹ座標はＴｉ−１のＹ座標よりＭ１／Ｍ０だけ大きい。Ｔｉ−１は一本下の水平格子線Ｈ０の方に近い。従ってＰｉのＹ座標はＰｉ−１のＹ座標よりも１だけ大きい。このことから（４−１）より更に強い条件を導くことができる。即ち
Ｒｉ＝Ｒｉ−１＋（Ｍ１／Ｍ０）−１ （４−２）
であるから、（４−２）を（４−１）に代入して
１／２−Ｍ１／Ｍ０＜Ｒｉ−１ （４−３）
となる。結局、右隣の描画点が一本上の格子線上に存在する描画点Ｐｉ−１について
１／２−Ｍ１／Ｍ０≦Ｒｉ−１＜１／２ （４−４）
の関係が成立する。このことはＰｊについても成立するから
１／２−Ｍ１／Ｍ０≦Ｒｊ＜１／２ （４−５）
またＰｉ−１からＰｊまでの距離はＫ１であるから
Ｒｊ＝Ｒｉ−１＋Ｋ１（Ｍ１／Ｍ０）−１ （４−６）
であるから、式（４−４）、（４−５）、（４−６）よりＲｉ−１、Ｒｊを消去すると
Ｍ０／Ｍ１−１＜Ｋ１＜Ｍ０／Ｍ１＋１ （４−７）
となる。ここでＭ０＝Ｑ１Ｍ１＋Ｍ２であるから
Ｑ１＋（Ｍ２／Ｍ１）−１＜Ｋ１＜Ｑ１＋（Ｍ２／Ｍ１）＋１ （４−８）
である。Ｋ１は整数であり、０＜Ｍ２／Ｍ１＜１であるから
Ｋ１＝Ｑ１
または
Ｋ１＝Ｑ１＋１
である。証明終わり。
【００９０】
＜証明２＞
図２２のように、Ｂ１タイプのブロックの左端の描画点の更に左の描画点ＰＢ１Ｌの残差（以下、Ｂ１の左残差と呼ぶ）をＲＢ１Ｌとする。また、Ｂ１の右端の描画点ＰＢ１Ｒの残差をＲＢ１Ｒとする。ＰＢ１Ｌ、ＰＢ１Ｒの両方ともその右隣の描画点は一本上の水平格子線上に存在する。従って式（４−４）から
１／２−Ｍ１／Ｍ０≦ＲＢ１Ｌ＜１／２ （５−１）
１／２−Ｍ１／Ｍ０≦ＲＢ１Ｒ＜１／２ （５−２）
また、
△Ｂ１＝ＲＢ１Ｒ−ＲＢ１Ｌ （５−３）
とすると、△Ｂ１はタイプＢ１のブロックが引き起こす残差の変化分である。タイプＢ１のブロックは、Ｑ１＋１個の水平描画点を持つから１点につきＭ１／Ｍ０だけ残差は増加する。また、ＰＢ１ＲはＰＢ１Ｌより１本上の格子線上にあるから、残差は１だけ減じられる。従って
△Ｂ１＝（Ｑ１＋１）Ｍ１／Ｍ０−１＝（Ｍ１−Ｍ２）／Ｍ０ （５−４）
となる。
【００９１】
また、同様に、Ａ１タイプの左残差をＲＡ１Ｒ、このブロックの右に隣接するブロックの左残差をＲＡ１Ｒ、Ａ１タイプのブロックが引き起こす残差の変化分を△Ａ１とすると
１／２−Ｍ１／Ｍ０≦ＲＡ１Ｌ＜１／２ （５−５）
１／２−Ｍ１／Ｍ０≦ＲＡ１Ｒ＜１／２ （５−６）
△Ａ１＝ＲＡ１Ｒ−ＲＡ１Ｌ （５−７）
△Ａ１＝Ｑ１Ｍ１／Ｍ０−１＝−Ｍ２／Ｍ０ （５−８）
となる。式（５−１）、（５−２）、（５−３）、（５−４）からＲＢ１Ｒ、△Ｂ１を消去すると
１／２−Ｍ１／Ｍ０≦ＲＢ１Ｌ＜１／２−（Ｍ１−Ｍ２）／Ｍ０ （５−９）
また、式（５−５）、（５−６）、（５−７）、（５−８）からＲＡ１Ｒ、△Ａ１を消去すると
１／２−（Ｍ１−Ｍ２）／Ｍ０≦ＲＡ１Ｌ＜１／２ （５−１０）
となる。
【００９２】
図２４の第１番目のＢ１タイプのブロック２４１から、次のＢ１タイプのブロック２４４の直前までのブロック数をＫ２とする。ブロック２４１はＢ１タイプであるからその左残差は
１／２−Ｍ１／Ｍ０≦ＲＢ１Ｌ＜１／２−（Ｍ１−Ｍ２）／Ｍ０ （５−１１）
である。ブロック２４４もタイプＢ１であるから、このブロックの左残差をＲＢ１Ｎとすると
１／２−Ｍ１／Ｍ０≦ＲＢ１Ｎ＜１／２−（Ｍ１−Ｍ２）／Ｍ０」 （５−１２）
である。Ａ１タイプの並ぶ個数はＫ２−１個であるから
ＲＢ１Ｎ＝ＲＢ１Ｌ＋△Ｂ１＋（Ｋ２−１）△Ａ１ （５−１３）
となる。式（５−４）、（５−８）、（５−１３）より
ＲＢ１Ｎ＝ＲＢ１Ｌ＋（Ｍ１−Ｍ２）／Ｍ０−（Ｋ２−１）Ｍ２／Ｍ０ （５−１４）
であるから、（５−１１）、（５−１２）、（５−１４）より
（Ｍ１／Ｍ２）−１＜Ｋ２＜（Ｍ１／Ｍ２）＋１ （５−１５）
である。式（２−４）に従って
Ｍ１＝Ｑ２Ｍ２＋Ｍ３
だから
Ｑ２＋（Ｍ３／Ｍ２）−１＜Ｋ２＜Ｑ２＋（Ｍ３／Ｍ２）＋１ （５−１６）
となる。ここで０＜Ｍ３／Ｍ２＜１でＫ２は整数だから
Ｋ２＝Ｑ２
または
Ｋ２＝Ｑ２＋１
である。証明終り。
【００９３】
＜証明３＞
図２５の２５１及び２５４のように、Ｂ１タイプのブロックの次にＡ１タイプのブロックがＱ２個連続するものをＢ２タイプのブロック、Ｑ２−１個連続するものをＡ２タイプのブロックとする。任意のＢ２タイプのブロックからその右方に存在するＢ２タイプのブロックの直前までのブロック数をＫ３個とする。Ｂ２タイプのブロック２５１の左残差をＲＢ２Ｌ、Ａ２タイプのブロック２５２の左残差をＲＡ２Ｌとする。これらはそれぞれ左端にＢ１タイプのブロックが在るからＢ１タイプの左残差を持ち、式（５−９）より
１／２−Ｍ１／Ｍ０≦ＲＢ２Ｌ＜１／２−（Ｍ１−Ｍ２）／Ｍ０ （６−１）
１／２−Ｍ１／Ｍ０≦ＲＡ２Ｌ＜１／２−（Ｍ１−Ｍ２）／Ｍ０ （６−２）
となる。ブロック２５１にはＢ１タイプのブロックが１個、Ａ１タイプのブロックがＱ２個並んでいるから
△Ｂ２＝ＲＡ２Ｌ−ＲＢ２Ｌ＝△Ｂ１＋Ｑ２△Ａ１ （６−３）
となる。ブロック２５３の左残差をＲＡ２Ｎとすると
△Ａ２＝ＲＡ２Ｎ−ＲＡ２Ｌ＝△Ｂ１＋（Ｑ２−１）△Ａ１ （６−４）
となる。式（６−３）、（６−４）の△Ａ１、△Ｂ１に（５−４）、（５−８）を代入すると
△Ａ２＝Ｍ３／Ｍ０ （６−５）
△Ｂ２＝−（Ｍ２−Ｍ３）／Ｍ０ （６−６）
となる。式（６−１）、（６−２）、（６−３）、（６−６）より
１／２−（Ｍ１−Ｍ２＋Ｍ３）／Ｍ０≦ＲＢ２Ｌ＜１／２−（Ｍ１−Ｍ２）／Ｍ０ （６−７）
を得る。ブロック２５４の左残差をＲＢ２Ｎとすると、ＲＢ２Ｎも式（６−７）を満足しなければならないから
１／２−（Ｍ１−Ｍ２＋Ｍ３）／Ｍ０≦ＲＢ２Ｎ＜１／２−（Ｍ１−Ｍ２）／Ｍ０ （６−８）
となる。ブロック２５１から次のＢ２タイプのブロック２５４までには、Ａ２タイプのブロックがＫ３−１個存在するから
ＲＢ２Ｎ＝ＲＢ２Ｌ＋△Ｂ２＋（Ｋ３−１）△Ａ２ （６−９）
であり、式（６−７）、（６−８）、（６−９）より
−Ｍ３／Ｍ０＜△Ｂ２＋（Ｋ３−１）△Ａ２＜Ｍ３／Ｍ０ （６−１０）
を得る。△Ａ２＞０、△Ｂ２＜０であることを考慮して、式（６−５）、（６−６）、（６−１０）から△Ａ２、△Ｂ２を消去すると
Ｑ３＋Ｍ４／Ｍ３−１＜Ｋ３＜Ｑ３＋Ｍ４／Ｍ３＋１ （６−１１）
０＜Ｍ４／Ｍ３＜１で、Ｋ３は整数だから
Ｋ３＝Ｑ３
または
Ｋ３＝Ｑ３＋１
である。証明終り。
【００９４】
＜証明４＞
一般式を数学的帰納法によって証明する。即ち、式（７−１）〜（７−６）が成立しているものとして、式（７−７）〜（７−１２）を導出する。
【００９５】
Ａｎ＝Ｂｎ−１＆（Ｑｎ−１）＊Ａｎ−１ （７−１）
Ｂｎ＝Ｂｎ−１＆Ｑｎ＊Ａｎ−１ （７−２）
Ｗａ，ｎ−１＜Ｒａ，ｎ−１＜Ｕａ，ｎ−１ （７−３）
Ｗｂ，ｎ−１＜Ｒｂ，ｎ−１＜Ｕｂ，ｎ−１ （７−４）
△Ａｎ−１＝（Ｓｎ−１−Ｓｎ）／Ｍ０ （７−５）
△Ｂｎ−１＝（Ｓｎ−２−Ｓｎ）／Ｍ０ （７−６）
Ａｎ＋１＝Ｂｎ＆（Ｑｎ＋１−１）＊Ａ （７−７）
Ｂｎ＋１＝Ｂｎ＆Ｑｎ＋１＊Ａｎ （７−８）
Ｗａ，ｎ＜Ｒａ，ｎ＜Ｕａ，ｎ （７−９）
Ｗｂ，ｎ＜Ｒｂ，ｎ＜Ｕｂ，ｎ （７−１０）
△Ａｎ＝（Ｓｎ−Ｓｎ＋１）／Ｍ０ （７−１１）
△Ｂｎ＝（Ｓｎ−１−Ｓｎ＋１）／Ｍ０ （７−１２）
但し、Ｕａ，ｎ、Ｕｂ，ｎ、Ｗａ，ｎ、Ｗｂ，ｎはｎが奇数の場合と偶数の場合とで、それぞれ以下の値を取る。即ち、
ｎが奇数の場合
Ｕａ，ｎ＝−１／２＋Ｓｎ−１／Ｍ０ （７−１３）
Ｕｂ，ｎ＝Ｗａ，ｎ＝−１／２＋Ｓｎ＋１／Ｍ０ （７−１４）
Ｗｂ，ｎ＝−１／２＋Ｓｎ／Ｍ０ （７−１５）
ｎが偶数の場合
Ｕａ，ｎ＝Ｗｂ，ｎ＝−１／２＋Ｓｎ＋１／Ｍ０ （７−１６）
Ｕｂ，ｎ＝−１／２＋Ｓｎ／Ｍ０ （７−１７）
Ｗａ，ｎ＝−１／２＋Ｓｎ−１／Ｍ０ （７−１８）
である。また、
Ｓｎ＝Ｍ０−Ｍ１＋Ｍ２＋…＋（−１）ｎＭｎ （７−１９）
である。また、式（７−１９）におけるＭ１，Ｍ２，‥，Ｍｎは式（２−８）の除数列の要素である。
【００９６】
式（７−３）におけるＲａ，ｎ−１は図２６のタイプＡｎ−１のブロック２６０２の最左端の描画点の左残差である。また、式（７−４）におけるＲｂ，ｎ−１はタイプＢｎ−１の最左端の描画点の左残差である。また、△Ａｎ−１はタイプＡｎ−１のブロックの残差の増分である。即ち、ブロック２６０３の最左端の描画点の左残差からブロック２６０２の最左端の描画点の左残差を差し引いた値である。△Ｂｎ−１はタイプＢｎの残差の増分である。即ち、ブロック２６０２の最左端の描画点の左残差Ｒａ，ｎ−１から、ブロック２６０１の最左端の描画点の左残差Ｒｂ，ｎ−１を差し引いた値である。
【００９７】
式（７−１）、（７−２）は、次のことを意味している。即ち、
（１）垂直方向で最も直線に近い描画点群は、図２６のようにタイプＡｎ−１とタイプＢｎ−１の２種類の形状のブロックに分けることができる。
（２）これらのブロックの連鎖はタイプＢｎ−１の右にＱｎ−１個のタイプＡｎ−１のブロックが接続する場合と、タイプＢｎ−１の右にＱｎ個のタイプＡｎ−１のブロックが接続する場合とが存在する。また、この場合だけが存在する。前者をタイプＡｎ、後者をタイプＢｎとする。
【００９８】
上記（１）と（２）及び式（７−３）〜（７−６）を前提として、式（７−７）〜（７−１２）を導出する。まず（１）、（２）より
△Ａｎ＝△Ｂｎ−１＋（Ｑｎ−１）△Ａｎ−１ （７−２０）
△Ｂｎ＝△Ｂｎ−１＋Ｑｎ△Ａｎ−１＝△Ａｎ＋△Ａｎ−１ （７−２１）
である。これに（７−５）、（７−６）を代入すると
以上から（７−１１）、（７−１２）が導出された。
【００９９】
図２６において、ブロック２６０５の左残差をＲｂ，ｎ、ブロック２６０７のそれをＲａ，ｎとする。Ｒｂ，ｎはブロック２６０１の左残差の条件を満たさなければならないから、
Ｗｂ，ｎ−１＜Ｒｂ，ｎ＜Ｕｂ，ｎ−１ （７−２２）
更にＲｂ，ｎ＋△Ｂｎはブロック２６０６の左残差を満たさなければならないから、
Ｗｂ，ｎ−１＜Ｒｂ，ｎ＋△Ｂｎ＜Ｕｂ，ｎ−１ （７−２３）
また、Ｒａ，ｎはブロック２６０６の左残差を満たさねばならないから
Ｗｂ，ｎ−１＜Ｒａ，ｎ＜Ｕｂ，ｎ−１ （７−２４）
また、Ｒａ，ｎ＋△Ａｎはブロック２６１１の左残差の条件を満たさねばならないから、
Ｗｂ，ｎ−１＜Ｒａ，ｎ＋△Ａｎ＜Ｕｂ，ｎ−１ （７−２５）
である。
【０１００】
以上をもとに（７−２２）〜（７−２５）より（７−９）〜（７−１０）を導出するが、ｎが奇数の場合と偶数の場合に分けて導出する。まず、ｎが奇数の場合、（７−１１）、（７−１２）、（７−１９）より
である。従って（２−４）から
△Ａｎ＜０
△Ｂｎ＜０
である。従って（７−２２）、（７−２３）、（７−２４）、（７−２５）より
Ｗｂ，ｎ−１＜Ｒｂ，ｎ＜Ｕｂ，ｎ−１−△Ｂｎ （７−２６）
Ｗｂ，ｎ−１−△Ａｎ＜Ｒａ，ｎ＜Ｕｂ，ｎ−１ （７−２７）
を得る。ｎは奇数だから、ｎ−１は偶数である、（７−１６）、（７−１７）、（７−１８）より
従って
−１／２＋Ｓｎ／Ｍ０＜Ｒｂ，ｎ＜−１／２＋Ｓｎ＋１／Ｍ０ （７−２８）
また、（７−１６）、（７−１７）より
Ｗｂ，ｎ−１−△Ａｎ＝−１／２＋Ｓｎ／Ｍ０−（Ｓｎ−Ｓｎ＋１）／Ｍ０
＝−１／２＋Ｓｎ＋１／Ｍ０
Ｕｂ，ｎ−１＝−１／２＋Ｓｎ−１／Ｍ０
従って
−１／２＋Ｓｎ＋１／Ｍ０＜Ｒａ，ｎ＜−１／２＋Ｓｎ−１／Ｍ０ （７−２９）
以上から
Ｕｂ，ｎ＝−１／２＋Ｓｎ＋１／Ｍ０
Ｗｂ，ｎ＝−１／２＋Ｓｎ／Ｍ０
Ｕａ，ｎ＝−１／２＋Ｓｎ−１／Ｍ０
Ｗａ，ｎ＝−１／２＋Ｓｎ＋１／Ｍ０
よって（７−１３）、（７−１４）、（７−１５）が導出された。
【０１０１】
次にｎが偶数の場合は
である。ｎは偶数だから
△Ａｎ＞０
△Ｂｎ＜０
である。従って（７−２２）、（７−２３）、（７−２４）、（７−２５）より
Ｗｂ，ｎ−１−△Ｂｎ＜Ｒｂ，ｎ＜Ｕｂ，ｎ−１
Ｗｂ，ｎ−１＜Ｒａ，ｎ＜Ｕｂ，ｎ−１−△Ａｎ
を得る。ｎは偶数だからｎ−１は奇数であり、（７−１４）、（７−１５）より
従って
−１／２＋Ｓｎ＋１／Ｍ０＜Ｒｂ，ｎ＜−１／２＋Ｓｎ／Ｍ０
または（７−１３）、（７−１４）より
従って
−１／２＋Ｓｎ＋１／Ｍ０＜Ｒａ，ｎ＜−１／２＋Ｓｎ−１／Ｍ０
以上から
Ｕｂ，ｎ＝−１／２＋Ｓｎ／Ｍ０
Ｗｂ，ｎ＝−１／２＋Ｓｎ＋１／Ｍ０
Ｕａ，ｎ＝−１／２＋Ｓｎ＋１／Ｍ０
Ｗａ，ｎ＝−１／２＋Ｓｎ−１／Ｍ０
よって（７−１６）、（７−１７）、（７−１８）が導出された。
【０１０２】
以上から、ｎが奇数の場合、偶数の場合とも式（７−９）、（７−１０）が導出されたことになる。
【０１０３】
次に式（７−７）、（７−８）を導出する。図２６のようにタイプＡｎのブロックとタイプＢｎのブロックとに描画点群は分けられると仮定して、２つのタイプＢｎのブロック２６０５と２６１０との間にＫｎ＋１−１個のタイプＡｎのブロックが存在したとする。ブロック２６０５と２６１０とは両方ともタイプＢｎであるから、
Ｗｂ，ｎ＜Ｒｂ，ｎ＜Ｕｂ，ｎ （７−１０）
Ｗｂ，ｎ＜Ｒｂ，ｎ＋△Ｂｎ＋（Ｋｎ＋１−１）△Ａｎ＜Ｕｂ，ｎ （７−３０）
を満たす。
【０１０４】
−Ｕｂ，ｎ＜−Ｒｂ，ｎ＜−Ｗｂ，ｎ （７−３１）
であるから、式（７−３０）、（７−３１）の両辺を加算しＲｂ，ｎを消去すると
−（Ｕｂ，ｎ−Ｗｂ，ｎ）＜△Ｂｎ＋（Ｋｎ＋１−１）△Ａｎ＜Ｕｂ，ｎ−Ｗｂ，ｎ （７−３２）
を得る。（７−１１）、（７−１２）より
△Ｂｎ−△Ａｎ＝−（−１）ｎＭｎ／Ｍ０ （７−３３）
また、式（７−１３）、（７−１４）、（７−１７）、（７−１８）より、ｎが奇数の場合も偶数の場合も
Ｕｂ，ｎ−Ｗｂ，ｎ＝Ｍｎ＋１／Ｍ０ （７−３４）
である。（７−３２）、（７−３３）、（７−３４）より
−｛Ｍｎ＋１−（−１）ｎＭｎ｝／Ｍ０＜Ｋｎ＋１×△Ａｎ＜｛Ｍｎ＋１＋（−１）ｎＭｎ｝／Ｍ０ （７−３５）
ｎが奇数の場合も偶数の場合も
Ｍｎ／Ｍｎ＋１−１＜Ｋｎ＋１＜Ｍｎ／Ｍｎ＋１＋１ （７−３６）
となる。（２−４）より
Ｑｎ＋１＋Ｍｎ＋２／Ｍｎ＋１−１＜Ｋｎ＋１＜Ｑｎ＋１＋Ｍｎ＋２／Ｍｎ＋１＋１
０＜Ｍｎ＋２／Ｍｎ＋１＜１でかつＫｎ＋１は整数だから
Ｋｎ＋１＝Ｑｎ＋１
または
Ｋｎ＋１＝Ｑｎ＋１＋１
である。
【０１０５】
以上から、Ｂｎの右にＡｎがＱｎ＋１−１個接続される場合と、Ｂｎの右にＡｎがＱｎ＋１個接続される場合とが存在することが分かる。前者をＡｎ＋１、後者をＢｎ＋１とすれば、式（７−７）、（７−８）が導出されたことになる。従って、タイプＡｎ−１のブロックとタイプＢｎ−１のブロックとが接続されてできる連鎖は、次の２つのブロックの連鎖に分けることができる。即ち、
タイプＡｎのブロック：１個のタイプＢｎ−１のブロックにＱｎ−１個のタイプＡｎ−１のブロックが接続されたブロック
タイプＢｎのブロック：１個のタイプＢｎ−１のブロックにＱｎ個のタイプＡｎ−１のブロックが接続されたブロック
の２つである。ｎ＝１及びｎ＝２の場合は、それぞれ＜証明１＞及び＜証明２＞によって成立している。従って、数学的帰納法により１からＮまでのすべてのｎについて、（７−７）〜（７−１９）が成立する。証明終り。
【０１０６】
本発明の直線描画装置は、描画点の座標を高速に計算できる。直線の傾きを整数比、即ちＭ１／Ｍ０とすると、以下の作業で描画点の座標を計算できる。
【０１０７】
（ア）Ｍ１とＭ０とから商数列を計算する。
【０１０８】
（イ）商数列から制御数列を計算する。
【０１０９】
（ウ）制御数列をもとに一描画点あたり、２回の加算で座標を生成する。
【０１１０】
上記（ア）（イ）の演算操作は、描画点の数に比例しない。直線の傾きＭ１／Ｍ０だけから少数回の演算で実行できる。従って描画点の個数が多くなればなるほど効果がある。また、（ア）（イ）の演算操作は、描画の開始前に実行を済ませておくことができる。従って描画中には（ウ）の演算操作だけを行なえばよく、高速な描画が可能である。（ウ）の演算は“１”または“０”を加算する演算であるから、この部分を簡単なハードウエアで実現することも可能である。これに対して従来の方法、例えば図３のような例では描画と同時に座標計算のための数値演算と条件判定とを行なわなければならなかった。本発明はこのような欠点を克服するものである。
【０１１１】
更に（イ）で生成される制御数列は最小周期の情報であるから、描画点の数が多くても繰り返し利用することができる。加えて、Ｂｒｅｓｅｎｈａｍのアルゴリズム同様、丸め誤差が積算することはなく、描画点数によらず正確な描画が出来る。即ち、本発明の装置によって生成される描画点はＢｒｅｓｅｎｈａｍのアルゴリズムによって生成されるものと同一になる。
【０１１２】
また、本装置の描画方法では、水平に並ぶ描画点の数を簡単な計算で予め算出することが出来る。従って、描画中に次に描画すべき点の座標を算出する必要はなく、描画以前にすべての点を算出するデータを得ることができる。もちろん描画と並列して描画点を算出することも可能である。描画中に判定操作も減算操作も不要である。従って、従来の方式に比べて大幅に描画時間を短縮できる。
【０１１３】
（実施の形態２）
第２の実施形態の直線描画装置は、図２７に示すように、除算の代わりに減算を行なって制御数列を生成する統合計算装置２７１を備えており、座標計算装置２７２は、この統合計算装置２７１の生成した制御数列に基づいて直線を描画する。
【０１１４】
この装置の利点は
（１）除算器を必要としない。
（２）商数列記憶装置を必要としない。
の２点にある。
【０１１５】
この統合計算装置２７１は、２８図に示すように、Ｍ１の値を保持するレジスタ１０２と、Ｍ０の値を保持するレジスタ１０１と、入力する３つの値の１つを選択して出力するセレクタ２８１７と、セレクタ２８１７の出力を保持する減数レジスタ２８０６と、入力する値から減数レジスタ２８０６の値を減算する減算器２８０７と、減算器２８０７、減数レジスタ２８０６またはレジスタ１０１の出力値の内の１つを選択して出力するセレクタ２８０８と、セレクタ２８０８の出力を保持する残余レジスタ２８０５と、減数レジスタ２８０６の内容が“１”であるか否かを検出する１検出器２８１６と、残余レジスタ２８０５の内容がゼロであることを検出するゼロ検出器２８１４と、生成された制御数列を記憶する制御数列記憶装置２８０１と、制御数列記憶装置２８０１に対するアドレスポインタ２８０２、２８０３と、統合計算装置２７１の各部を制御する統合制御装置２８０４とを備えている。
【０１１６】
この装置では、減算器２８０７が、残余レジスタ２８０５の値から減数レジスタ２８０６の値を減算し、この減算を一回行なう毎に、統合制御装置２８０４が制御数列記憶装置２８０１の内容を一部変更する。そして、この繰り返しにより、最終的に制御数列が制御数列記憶装置２８０１の内部に生成される。
【０１１７】
この装置の動作を図２９のフローチャートを用いて説明する。図２９のフローチャートは、ステップ２９０１による初期状態設定の後に、ステップ２９０２を起点として次の４つのルートを持つ。即ち、
ルート１：ステップ２９０２、ステップ２９０３、ステップ２９０４、ステップ２９０５、ステップ２９０６、ステップ２９０７を通過してステップ２９０２へ戻るルート
ルート２：ステップ２９０２、ステップ２９０３、ステップ２９１０、ステップ２９１１を通過してステップ２９０２へ戻るルート
ルート３：ステップ２９０２、ステップ２９０３、ステップ２９０４、ステップ２９０５、ステップ２９０８、ステップ２９０９を通過してステップ２９０２へ戻るルート
ルート４：ステップ２９０２、ステップ２９１２、ステップ２９１３を通過してステップ２９０２へ戻るルート
の４つである。
【０１１８】
以下、初期状態の設定（ステップ２９０１）及び上記４つのルートにおける動作を順に説明する。なお、このフローチャートでは、（Ａ）は装置Ａの内容を表すものとする。従って（Ａ）→Ｂは、装置ＡまたはＡ番地の内容を装置Ｂに転送することを意味する。
【０１１９】
このフローチャートは、ルート１をＱ１回実行した後、ルート２を１回実行する。この後、ルート３をＱｍ回実行した後、ルート２を１回実行するということをｍ＝２〜Ｎまで実行し、最後にルート４を１回実行する。
【０１２０】
＜初期状態設定＞
ステップ２９０１：まず、統合制御装置２８０４は、セレクタ２８１７に対して一番左の入力信号を選択するための信号２７１８を、また、セレクタ２８０８に対して一番右の入力信号を選択するための信号を出力し、また、減数レジスタ２８０６及び残余レジスタ２８０５に対して入力データの格納を指示する信号２８１５を出力する。これを受けて減数レジスタ２８０６はセレクタ２８１７から出力されたＭ１の値を格納し、また、残余レジスタ２８０５はセレクタ２８０８から出力されたＭ０の値を格納する。また、統合制御装置２８０４は、ポインタ（Ｐａ）２８０２及びポインタ（Ｐｂ）２８０３に、制御数列記憶装置２８０１の０番地を指示するようにゼロを格納し、制御数列記憶装置２８０１のＰｂ２８０３の指示する番地に信号線２８１１を通じて“１”を格納する（（Ｐｂ）←“１”）。従って、制御数列記憶装置２８０１の０番地にデータ１が格納される。
【０１２１】
＜ルート１＞
初期状態の設定の後、
ステップ２９０２：統合制御装置２８０４は、ゼロ検出器２８１４の出力を調べ、残余レジスタ２８０５の内容がゼロでないときは、
ステップ２９０３：減算器２８０９から出力される、減算結果の負を表す信号２８１０がＯＮかどうかを調べる。減算器２８０７は、これに先立って、残余レジスタ２８０５から読出した値から減数レジスタ２８０６に保持されている値を減算する演算を行なう。統合制御装置２８０４は、この信号２８１０によって、減数レジスタ２８０６の値と残余レジスタ２８０５の値との大小関係を識別し、減数レジスタ２８０６の値の方が残余レジスタ２８０５の値より小さければ、
ステップ２９０４：統合制御装置２８０４は、制御信号により、セレクタ２８０８に最も左の入力を選択するように指示し、また、残余レジスタ２８０５に信号２８１５を出力して、入力データの格納を指示する。その結果、残余レジスタ２８０５には、セレクタ２８０８の選択した減算器２８０７の出力、即ち、残余レジスタ２８０５の内容から減数レジスタ２８０６に保持されている内容を減じた値が格納される。
【０１２２】
ステップ２９０５：Ｐａ２８０２の内容が０のときは、
ステップ２９０６：統合制御装置２８０４は、制御数列記憶装置２８０１のＰｂ２８０３の値に１を加算したアドレスに“０”を格納し、
ステップ２９０７：Ｐｂ２８０３に、今まで保持している値に１を加算した値を新たに保持させる。次いで、ステップ２９０２に戻る。
【０１２３】
このルートがＱ１回実行される。なぜなら、Ｍ０からＭ１を減ずることを、結果が負になる直前まで実行するからである。このＱ１は式（２−７）におけるＱ１と同じである。Ｑ１回実行後の制御数列記憶装置２８０１の内容は図１２と同一となる（但し、Ｐａはアドレス０を指している）。
【０１２４】
Ｑ１回の上記減算の実行の後では、残余レジスタ２８０５の内容の方が減数レジスタ２８０６の内容より小さくなっている。従って、減算器２８０７の出力２８１０はＯＮとなり減算結果が負になることが表示される。統合制御装置２８０４は、この信号を検出しステップ２９０３から分岐しルート２を辿る。
【０１２５】
＜ルート２＞
ステップ２９１０：減算器２８０７の出力２８１０がＯＮとなると、セレクタ２８０８は中側の入力、即ち、減数レジスタ２８０６の内容を通過させる。従って、残余レジスタ２８０５には、それまで減数レジスタ２８０６に保持されていた内容Ｍ１が格納される。また、統合制御装置２８０４は、これ以上減算をすると結果が負になるという場合に、セレクタ２８１７に対して最も右の入力を選択するように指示し、その結果、減数レジスタ２８０６には、それまでの残余レジスタ２８０５の内容が格納される。従って減数レジスタ２８０６にはＭ０−Ｑ１Ｍ１、即ち、Ｍ２が格納される。
【０１２６】
ステップ２９１１：信号２８１０がＯＮになると、統合制御装置２８０４はＰａ２８０２及びＰｂ２８０３の値を読み出し、Ｐｂ−Ｐａ−１の演算を行ない、その結果をＰａ２８０２に格納する。これによりＰａ２８０２は図１２の位置を指示する状態に移る。
【０１２７】
＜ルート３＞
ルート２を通過した後、ルート３を通過する。このルートでは、ステップ２９０２、ステップ２９０３、ステップ２９０４はルート１と同一であり、残余レジスタ２８０５の内容から減数レジスタ２８０６に保持された値Ｍ２が減算され、減算値が残余レジスタ２８０５に格納される。
【０１２８】
ステップ２９０５：Ｐａ２８０２がゼロではないので、ステップ２９０８に移行し、
ステップ２９０８：統合制御装置２８０４は、制御数列記憶装置２８０１とデータの送受を行ないながら、制御数列記憶装置２８０１の０番地からＰａ２８０２の指示する番地までの内容を、Ｐｂ２８０３の指示する番地の次の番地から始まる領域にコピーする。
【０１２９】
ステップ２９０９：次いで、このコピー操作の格納最終番地をＰｂ２８０３が指示するように設定する。
【０１３０】
この後、ステップ２９０２に戻り、同じ手順を繰り返す。この繰り返しをＱ２回行ない、残余レジスタ２８０５の値が減数レジスタ２８０６の値Ｍ２より小さくなると、ルート２を通過し、減数レジスタ２８０６に保持されていた値Ｍ２を残余レジスタ２８０５に格納し、それまでの残余レジスタ２８０５の格納値Ｍ１−Ｑ２・Ｍ２、即ちＭ３を減数レジスタ２８０６に格納する。その後、さらにルート３を繰り返す。
【０１３１】
第２回目以降のルート２の通過により、残余レジスタ２８０５にはＭｍが格納され、減数レジスタ２８０６にはＭｍ＋１が格納される。従って、その後のルート３は、残余レジスタ２８０５、減数レジスタ２８０６にそれぞれＭｍ、Ｍｍ＋１が格納されている状態で始まり、残余レジスタ２８０５の内容が減数レジスタ２８０６の値で減算され、減算値が負になる直前まで繰り返され、残余レジスタ２８０５にＭｍ−Ｑｍ＋１・Ｍｍ＋１が、減数レジスタ２８０６にＭｍ＋１が格納された状態で終える。その後のルート２の通過により、残余レジスタ２８０５にＭｍ＋１が、減数レジスタ２８０６にＭｍ−Ｑｍ＋１・Ｍｍ＋１、即ちＭｍ＋２が格納される。
【０１３２】
このルートをＱｍ回繰り返して実行すると、ステップ１１０２〜１１０３を実行した場合と同一の結果（図１３の状態）が得られる。
【０１３３】
＜ルート４＞
ルート２、ルート３の実行を繰り返した後に、残余レジスタ２８０５の内容が減数レジスタ２８０６の内容で割り切れるようになると、残余レジスタ２８０５の内容はゼロになるので、ステップ２９０２から分岐し、ルート４の操作が実行される。このルート４は式（２−１３）の計算を行なうための準備をするものである。
【０１３４】
ステップ２９１２：統合制御装置２８０４は、１検出器２８１６から出力される信号を調べることによって、減数レジスタ２８０６の内容が“１”であるか否かを識別する。減数レジスタ２８０６の内容が１である場合は、制御数列記憶装置２８０１に記憶された数列が既に制御数列であるため、式（２−１３）の計算は実際には不要になる。そこで、すべての操作を終了して良い。
【０１３５】
ステップ２９１３：減数レジスタ２８０６の内容が１でないということは、ＭＮ≠１で且つＭＮ＋１＝０であるということであるから、式（２−１３）の計算を行なう。そのためには、ルート３をＭＮ回通過すれば良い。そこで、残余レジスタ２８０５には減数レジスタ２８０６の内容、即ち、ＭＮを、また、減数レジスタ２８０６には“１”を設定する。
【０１３６】
次いで、ルート３の通過を繰り返す。ルート３を１回通過するごとに、ＭＮから１が減算され、ＭＮ回の通過が終了した時点で残余レジスタ２８０５の値がゼロになり、それをゼロ検出器２８１４が統合制御装置２８０４に伝えて、制御数列生成の操作が終了する。
【０１３７】
このように、第２の実施形態の装置は、除算器を必要とせず、簡単な構造で直線の描画を行なうことができる。
【０１３８】
【発明の効果】
以上の説明から明らかなように、本発明の直線描画装置は、描画点を得るための操作回数を従来に比べて大幅に減らすことができ、高速での描画作業が可能になる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態における直線描画装置の構成を示すブロック図、
【図２】直線を格子点で近似する描画の例、
【図３】直線と格子点との関係を説明する図、
【図４】従来の直線描画方式の一例、
【図５】第１の実施形態の直線描画装置における商数列計算装置の構成を示すブロック図、
【図６】第１の実施形態の直線描画装置における制御数列計算装置の構成を示すブロック図、
【図７】第１の実施形態の直線描画装置における座標計算装置の構成を示すブロック図、
【図８】前記商数列計算装置の動作を説明するフローチャート、
【図９】前記制御数列計算装置における制御数列記憶装置の内容を説明する図、
【図１０】前記制御数列計算装置の動作を説明するフローチャート、
【図１１】前記制御数列計算装置の動作を説明するフローチャートの続き、
【図１２】前記制御数列記憶装置の内容と２つのアドレスポインタとの関係を示す図、
【図１３】前記制御数列記憶装置の内容の変化を説明する図、
【図１４】前記座標計算装置の動作を説明するフローチャート、
【図１５】前記商数列記憶装置の内容の具体例、
【図１６】前記制御数列記憶装置の内容の変化の具体例（その１）、
【図１７】前記制御数列記憶装置の内容の変化の具体例（その２）、
【図１８】前記制御数列記憶装置の内容の変化の具体例（その３）、
【図１９】前記制御数列記憶装置の内容の変化の具体例（その４）、
【図２０】前記具体例における描画点を示す図、
【図２１】本発明の基礎となる数学的事実を証明するための図（その１）、
【図２２】本発明の基礎となる数学的事実を証明するための図（その２）、
【図２３】本発明の基礎となる数学的事実を証明するための図（その３）、
【図２４】本発明の基礎となる数学的事実を証明するための図（その４）、
【図２５】本発明の基礎となる数学的事実を証明するための図（その５）、
【図２６】本発明の基礎となる数学的事実を証明するための図（その６）、
【図２７】本発明の第２の実施形態における直線描画装置の構成を示すブロック図、
【図２８】第２の実施形態の直線描画装置における統合計算装置の構成を示すブロック図、
【図２９】前記統合計算装置の動作を説明するフローチャートである。
【符号の説明】
１０１、１０２ レジスタ
１０３ 商数列計算装置
１０４ 制御数列計算装置
１０５、２７２ 座標計算装置
２７１ 統合計算装置
５０１ 被除数レジスタ
５０２ 除数レジスタ
５０３ 商数列記憶装置
５０４ 剰余レジスタ
５０５ 除算器
５０６ ゼロ検出器
５０７、６０２、６０３、６０４、７０１、２８０２、２８０３ アドレスポインタ
５０８、５０９、５１６、２８０８、２８１７ セレクタ
５１０ 商数列制御装置
６０１ 制御数列記憶装置
６０５ 制御数列制御装置
７０２ バッファ
７０３ 加算器
７０４ Ｒｘレジスタ
７０５ Ｒｙレジスタ
７０６ 座標計算制御装置
２８０１ 制御数列記憶装置
２８０４ 統合制御装置
２８０５ 残余レジスタ
２８０６ 減数レジスタ
２８０７ 減算器
２８１４ ゼロ検出器
２８１６ １検出器
【発明の属する技術分野】
本発明は、紙の上に直線を描画するＸ−Ｙプロッタや、表示装置の画面に直線を表示する装置、記憶装置の内部に直線を描く作業をする計算装置などに利用することができる直線描画装置に関し、特に、高速な直線描画を可能にするものである。
【０００２】
【従来の技術】
格子状に配置された記憶素子に直線を描画する場合、図２のように、データを書き込むべき格子点として、描画すべき直線に最も近いものが選ばれる。しかし、水平に並ぶ描画点の数は、一般に一定ではない。図２は、直線Ｌの傾きが３／８の例であるが、描画点が水平に３個と２個並ぶ場合が出現する。
【０００３】
従来、このような点、即ち、垂直格子線上で直線に最も近い点を算出する方法としてＤＤＡ（Ｄｉｇｉｔａｌ Ｄｉｆｆｅｒｅｎｃｉａｌ Ａｎａｌｙｓｉｓ）及びＢｒｅｓｅｎｈａｍのアルゴリズムがよく知られている。後者は前者における積算誤差を取り除く方式である。これらについての説明は、例えばＷ．Ｍ．Ｎｅｗｍａｎ ＆ Ｒ．Ｆ．Ｓｐｒａｕｌｌ著“Ｐｒｉｎｃｉｐｌｅ ｏｆ Ｉｎｔｅｒａｃｔｉｖｅ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ” ＰＰ２５−２７，１９８１に詳しく述べられている。
【０００４】
これらの方式は描画点のＸ座標とＹ座標とを逐次的に算出するものである。そのアルゴリズムをプログラムの形にした一例を図３に示す。図３では従来一般的に利用されているＤＤＡに従って描画点の座標Ｘ，Ｙを計算する。図中のｐｌｏｔ（Ｘ，Ｙ）は座標（Ｘ，Ｙ）に一点を描画する関数であり、描画する直線の傾きはＭ１／Ｍ０であるものとする。これから分かるように、描画点１個につき２回の加算（第４行、第５行）と１回の判定（第６行）、更に数点につき１回の減算（第８行）が必要である。
【０００５】
図３のアルゴリズムを図４を用いて更に詳しく説明する。図４は図２の中の一つの描画点の付近を拡大した図である。点Ｔｎは真の点、即ち、直線Ｌと垂直格子線との交点である。描画点Ｐｎは真の点Ｔｎに最も近い格子点である。従って点ＴｎからＰｎまでのＹ座標の差をＲｎとすると、
−１／２≦Ｒｎ＜１／２ （１−１）
である。但し、説明の簡単のため、格子間隔は縦、横とも１とする。Ｔｎ＋１とＴｎとのＹ座標の差はＭ１／Ｍ０であるから
Ｒｎ＋１＝Ｒｎ＋Ｍ１／Ｍ０， （Ｒｎ＋Ｍ１／Ｍ０＜１／２のとき） （１−２）
Ｒｎ＋１＝Ｒｎ＋Ｍ１／Ｍ０−１，（Ｒｎ＋Ｍ１／Ｍ０≧１／２のとき） （１−３）
という関係が成立する。以上の事実に基づき、描画点のＸ，Ｙ座標を計算する手法の一つが図３に掲げたＤＤＡのアルゴリズムである。
【０００６】
図３の第１行は、変数Ｒｎの初期値を設定するものである。第２行と第１０行は対になっており、ｉを１から１ずつ増加させながら第３行から第９行までをＭ０回繰り返すことを意味している。第３行は、点Ｐｉ、即ち座標（Ｘｉ，Ｙｉ）に点を描画すること、即ちデータを書き込むことを意味する。第４行は、次の描画点のＸ座標を計算する、即ちＸ座標を１だけ増加することを意味する。つまり、第３行で描画した点の次の点、即ちＰｉ＋１のＸ座標が求められる。第５行は残差ＲｍをＭ１／Ｍ０だけ増加することを意味する。格子間隔は１と仮定しているのでＸが１だけ増加するとＹ座標はＭ１／Ｍ０だけ増加する。Ｒｍは直線Ｌと格子線との交わる真の点のＹ座標の少数部分である。従って、第６行で残差が１／２より大きくなったか否かを調べ、もし１／２より大きければ、第７行で座標を１だけ増加し、第８行で残差から１を減ずる。
【０００７】
実際にはこれを改良したＢｒｅｓｅｎｈａｍのアルゴリズムが多く利用されている。図３のプログラムを実際の計算機で実行する場合には図３の第５行で加算されるＭ１／Ｍ０は有限の長さのレジスタに保持される。従ってこの値には丸め誤差が入り込む場合がある。Ｂｒｅｓｅｎｈａｍのアルゴリズムは、この誤差が発生しないようにしたものである。
【０００８】
【発明が解決しようとする課題】
図３のようなアルゴリズムで直線を描画する場合、座標計算には以下の４つの操作が必要であった。即ち、
（１）一描画点当りＸ座標計算のための加算１回
（２）一描画点当りＹ座標計算のための加算１回
（３）一描画点当りＹ座標の残差の大きさの判定１回
（４）数個の描画点につき１回の減算
が必要であった。従って、描画すべき点の数の２倍の加算操作、描画点と同数の判定操作、及び描画点数よりは少ないが描画点数に比例した回数の減算操作が必要であった。そのため、計算に多くの時間を要し、描画作業の高速化には限界があった。
【０００９】
本発明は、こうした従来の問題点を解決するものであり、高速で直線を描画することができる直線描画装置を提供することを目的としている。
【００１０】
【課題を解決するための手段】
そこで、本発明の直線描画装置では、直線の傾きを整数比Ｍ１／Ｍ０で表現した場合に、Ｍ１とＭ０とをそれぞれ保持する第１及び第２の整数保持手段と、Ｍ１とＭ０とから商数列（即ち、Ｍ０をＭ１で除算したときの商がＱ１、余りがＭ２であるとき、次にＭ１をＭ２で除算して、その商Ｑ２と、余りＭ３とを求め、これを順次繰り返して得られるＱ１，Ｑ２，Ｑ３，‥の数列）を計算する商数列計算手段と、この商数列から、隣接する描画点間の格子点上の差異を表す制御数列（即ち、右隣の描画点のＹ座標と１だけずれている場合に“１”、ずれが無い場合に“０”と表した数列）を計算する制御数列計算手段と、この制御数列から描画点の座標を計算する座標計算手段とを設けている。図２の下部に制御数列の例を示す。
【００１１】
この装置では、この制御数列を簡単に求めることによって、従来に比べて少ない操作で描画点の座標を求めることができ、高速での直線描画が可能となる。
【００１２】
【発明の実施の形態】
本発明の請求項１に記載の発明は、格子点上に直線の近似点を描画する直線描画装置において、直線の傾きを定める第１及び第２の整数をそれぞれ保持する第１及び第２の整数保持手段と、第１及び第２の整数保持手段に保持された２つの整数による除算で商と余りとを求め、次に、先行する除算の除数を被除数とし、余りを除数とする除算を繰り返して各除算の商から成る商数列を計算する商数列計算手段と、この商数列から、隣接する描画点間の格子点上の差異を表す制御数列を計算する制御数列計算手段と、この制御数列から描画点の座標を計算する座標計算手段とを設け、前記商数列計算手段は、前記商数列を求める際、除算の結果の余りが生じた場合、除算の余りが０になるまで計算を繰り返すようにしたものであり、商数列の計算、制御数列の計算、及び、制御数列を基に１描画点当たり２回の加算、によって描画点の座標を求めることができる。
【００１３】
請求項２に記載の発明は、前記商数列計算手段が、被除数を保持する被除数保持手段と、除数を保持する除数保持手段と、被除数保持手段に保持された被除数を除数保持手段に保持された除数で除算する除算手段と、この除算における商を保持する商数列保持手段と、この除算における余りを保持する余り保持手段と、余り保持手段の内容がゼロであることを検出するゼロ検出手段とを具備し、被除数保持手段及び除数保持手段が最初にそれぞれ第１の整数及び第２の整数を保持し、除算手段の除算が行なわれた後、除数保持手段の内容を被除数保持手段に転送し、余り保持手段の内容を除数手段に転送して、除算手段の次の除算を行ない、これを余り保持手段の内容がゼロとなるまで繰り返すようにしたものであり、これにより、制御数列の計算の基礎となる商数列を生成することができる。
【００１４】
請求項３に記載の発明は、前記制御数列計算手段が、生成された制御数列を記憶する制御数列記憶手段と、制御数列記憶手段の第１のアドレスを保持する第１のポインタと、制御数列記憶手段の第２のアドレスを保持する第２のポインタと、商数列を記憶する商数列記憶手段とを具備し、制御数列記憶手段の０番地から第１のポインタの指示する番地までの内容を複製の単位として、商数列記憶手段から読出した商数列要素の値の回数だけ複製して、制御数列記憶手段の第２のポインタが指示する番地の次の番地から始まる領域に格納し、第２のポインタの保持するアドレスを格納後の最終番地に変更し、第１のポインタの保持するアドレスを、次の複製の単位となる番地に変更し、この動作を、商数列記憶手段に記憶された商数列要素について１回ずつ繰り返すようにしたものであり、これにより、商数列を用いて制御数列を生成することができる。
【００１７】
以下、本発明の実施の形態について、図面を用いて説明する。
【００１８】
本発明の直線描画方法は、新しく発明された数学的理論に基づいているので、次のような順で説明を行なう。即ち、
第１節 本発明の直線描画装置で使用される数学的概念の説明
第２節 本発明の直線描画装置の実施の形態とその動作説明
第３節 数学的証明
の３節に分けて説明する。
【００１９】
第１節 本発明の直線描画装置で使用される数学的概念の説明
本発明の描画装置は、図２に示すように、直線を描画するための制御数列Ｃｎを簡単な操作で生成することによって、高速な描画を達成するものである。この制御数列は、一つの描画点の左に隣接する描画点が水平方向に存在するときに０、また、左に隣接する描画点が斜め方向に存在するときに１と表現した数列である。図４の直線Ｌの近似点ＰｎのＸ座標とＹ座標とは、制御数列Ｃｎから次のようにして算出することが出来る。即ち、
Ｘｎ＝Ｘｎ−１＋１ （２−１）
Ｙｎ＝Ｙｎ−１＋Ｃｎ−１ （２−２）
上記の式（２−１），（２−２）はＣｎがゼロであればＰｎはＰｎ−１の右隣り、Ｃｎが１であればＰｎはＰｎ−１の右上となることを示している。
【００２０】
式（２−１）と（２−２）から明らかなように、予め制御数列が知れていれば、一点を描画するのに２回の加算だけが必要で、判定は不要である。しかも、これらの加算は１または０を加えるという単純な整数演算である。この制御数列Ｃｎは、以下に述べる商数列から生成することができる。
【００２１】
１．１ 商数数列の定義
制御数列は、別の新たな数列（以下、商数列と呼ぶ）から生成することができる。商数列とは次のようにして求められる数列である。即ち直線Ｌの傾きをＭ１／Ｍ０とする。但しＭ１，Ｍ０は整数とする。このときまず、
Ｍ０＝Ｑ１Ｍ１＋Ｍ２， Ｍ１＞Ｍ２＞０ （２−３）
を満足する整数Ｑ１、Ｍ２を求める。以下
Ｍｎ−１＝ＱｎＭｎ＋Ｍｎ＋１， Ｍｎ＞Ｍｎ＋１＞０ （２−４）
を満足する整数Ｑｎ、Ｍｎを式（２−５）が成立するまで次々と求める。即ち
ＭＮ−１＝ＱＮＭＮ （２−５）
となるまで、言い換えれば
ＭＮ＋１＝０ （２−６）
となるまで繰り返す。
【００２２】
以上の計算は、Ｍｎ−１をＭｎで割ったときの商と余りをそれぞれＱｎとＭｎ＋１とするものである。以下、このようにして求めた数列Ｑ１，Ｑ２，・・・，ＱＮを商数列Ｑ、数列Ｍ０，Ｍ１，Ｍ２，・・・，ＭＮを除数列Ｍと呼ぶことにする。即ち、
Ｑ＝｛Ｑ１，Ｑ２，・・・ＱＮ｝ （２−７）
Ｍ＝｛Ｍ０，Ｍ１，Ｍ２，・・・ＭＮ｝ （２−８）
である。
【００２３】
なお、ＭＮ＋１＝０となるようなＮは必ず存在する。即ち、Ｍ０、Ｍ１から出発して（２−４）の除算を繰り返すと、最後には余りがゼロになる。なぜならば、Ｍｎは正の整数でありＭｎ＞Ｍｎ＋１であるから、ｎが増加するとともにＭｎはＭｎ−１に比べて小さくなる。従って、最後には次のどちらかの場合に到達する。即ち、
（ア） ＭＮ＝１となり、ＭＮ＋１＝０となる。
【００２４】
（イ） ＭＮ＋１≠１で且つ、ＭＮがＭＮ＋１で割り切れ、従ってＭＮ＋１＝０となる。のどちらかである。従ってＭＮ＋１＝０となるＮが必ず存在する。ＭＮはＭ０とＭ１との最大公約数であることは、ユークリッドのアルゴリズムから明らかである。
【００２５】
１．２ 制御数列の定義
１．１で定義した商数列Ｑから、図２の制御数列Ｃは次のようにして生成することができる。即ちまず、中間の長さの数列Ｃａ，ｎとＣｂ，ｎとを以下のような漸化式で定義する。即ち、
Ｃａ，０＝｛０｝ （２−９）
Ｃｂ，０＝｛１｝ （２−１０）
Ｃａ，ｎ＝｛Ｃｂ，ｎ−１＆（Ｑｎ−１）＊Ｃａ，ｎ−１｝ （２−１１）
Ｃｂ，ｎ＝｛Ｃａ，ｎ＆Ｃａ，ｎ−１｝ （２−１２）
但し、記号＆及び＊は以下のような意味を持つものとする。即ち、有限の長さの数列α、βに対して
α＆βは、数列αの右側に数列βを接続して出来る数列
γ＊βは、数列βをγ個繰り返して出来る数列
を意味するものとする。
【００２６】
このような数列Ｃａ，ｎから式（２−９）〜（２−１２）によって制御数列Ｃを求めることができる。即ち、ＭＮ＋１＝０であるとき
Ｃ＝ＭＮ＊Ｃａ，Ｎ （２−１３）
である。式（２−９）〜（２−１３）が正しいことは「第３節 数学的証明」の項で後述する。
【００２７】
第２節 本発明の直線描画装置の実施の形態とその動作説明
以上の説明から分かるように、制御数列Ｃｎは、商数列、除数列を求める少数回の除算と、（２−９）〜（２−１３）に従って１と０とのビット列をコピーする作業とによって求めることができ、本発明の直線描画装置は、こうして得た制御数列から描画点の座標を計算し、格子点上に直線の近似点を描画する。この具体的方法とそれを実施する装置とについて以下に述べる。但し、直線Ｌの傾きは整数比Ｍ１／Ｍ０であるものとする。
【００２８】
実施形態の直線描画装置は、図１に示すように、直線の傾きを表す２つの整数Ｍ０とＭ１とをそれぞれ保持するレジスタ１０１、１０２と、Ｍ０とＭ１とから商数列を計算する商数列計算装置１０３と、商数列から制御数列を生成する制御数列計算装置１０４と、制御数列から描画点の座標Ｘ、Ｙを計算する座標計算装置１０５との５つの部分から構成される。
【００２９】
直線の傾きを表す２つの整数を保持するレジスタ１０１、１０２の必要な大きさは、直線の傾きの表現精度によって決まってくる。この実施形態では、直線の傾きを整数比Ｍ１／Ｍ０で表現することとしているため、Ｍ１及びＭ０の大きさの数字を保持できればよい。例えば２０００×２０００の画素数を持つ表示装置に適用する場合では、これら２つのレジスタ１０１、１０２は１２ビットあれば十分である。なぜならＭ１及びＭ０の最大値は２０００であるからである。
【００３０】
商数列計算装置１０３は、図５に示すように、被除数を記憶する被除数レジスタ５０１と、除数を記憶する除数レジスタ５０２と、被除数レジスタ５０１から読出した値を除数レジスタ５０２で読出した値で除算する除算器５０５と、除算器５０５で行なわれた除算の剰余を記憶する剰余レジスタ５０４と、剰余レジスタ５０４がゼロであるときにそれを検出して検出信号５１１を出力するゼロ検出装置５０６と、商数列を記憶する商数列記憶装置５０３と、商数列記憶装置５０３のアドレスを指示するアドレスポインタ５０７と、入力する二つの信号の一方を選択して出力するセレクタ５０８、５０９、５１６と、この商数列計算装置１０３の各部の動作を制御する商数列制御装置５１０とを備えている。
【００３１】
この商数列計算装置１０３は、数値Ｍ０とＭ１とから、図８に示すフローチャートに従って商数列を計算し、商数列記憶装置５０３に格納する。
【００３２】
まず、初期状態では、アドレスポインタ５０７はゼロを指定する。また、商数列制御装置５１０は、セレクタ５０８及び５０９の入力信号の選択を指示するセレクタ制御信号５１４としてゼロを設定し、それに応じて、セレクタ５０８及び５０９は両方とも左側の入力、即ち、Ｍ０とＭ１とをそれぞれ選択し通過させる。このことを前提に、商数列計算装置は次のように動作する。
【００３３】
ステップ８０１：商数列制御装置５１０は、信号５１５によりアドレスポインタ５０７の内容をゼロに設定し、また、被除数レジスタ５０１及び除数レジスタ５０２に対してデータの格納を指示する制御信号５１２をＯＮにする。それにより、数値Ｍ０とＭ１とが、それぞれ、セレクタ５０８及び５０９を経由して、被除数レジスタ５０１と除数レジスタ５０２とに格納される。
【００３４】
ステップ８０２：被除数レジスタ５０１に格納された数値Ｍ０と除数レジスタ５０２に格納された数値Ｍ１とは除算器５０５に入力し、除算器５０５はＭ０／Ｍ１を計算し、その商、即ちＱ１を信号５１９によりセレクタ５１６に出力し、余りＭ２を信号５２０により剰余レジスタ５０４に出力する。
この余りＭ２の出力は剰余レジスタ５０４に格納される。ゼロ検出器５０６は、剰余レジスタ５０４に格納されたＭ２の内容がゼロであるか否かを調べ、ゼロである場合には検出信号５１１をＯＮに、ゼロでなければＯＦＦにする。セレクタ５１６は、検出信号５１１がＯＦＦのときは、除算器５０５から出力されたＱ１信号５１９を選択して商数列記憶装置５０３に出力する。一方、商数列制御装置５１０は、商数列記憶装置５０３に対してデータ格納を指示する制御信号５１３をＯＮにする。それにより、商数列記憶装置５０３のアドレスポインタ５０７の指示するアドレスには、除算器５０５の商出力が格納される。
【００３５】
ステップ８０３：ゼロ検出器５０６の出力する検出信号５１１がＯＦＦのとき、つまり、剰余レジスタ５０４の内容がゼロでないときには、
ステップ８０４：商数列制御装置５１０は、アドレスポインタ５０７の内容を１だけ増やすことを指示する信号５１５を出力し、アドレスポインタ５０７は、アドレスを１だけ増加させる。
【００３６】
ステップ８０５：商数列制御装置５１０は、セレクタ５０８と５０９とが両方とも右側の入力をそれぞれ選択するようにセレクタ制御信号５１４を１に設定し、また、制御信号５１２をＯＮにする。その結果、除数レジスタ５０２の内容が被除数レジスタ５０１に転送され、また、剰余レジスタ５０４の内容が除数レジスタ５０２に転送される。
【００３７】
この後、ステップ８０２に移り、剰余レジスタ５０４の内容がゼロになるまで、ステップ８０２、８０３、８０４、８０５の手順を繰り返す。
ステップ８０３において、剰余レジスタ５０４の内容がゼロになり、ゼロ検出器５０６の検出信号５１１がＯＮになると、
ステップ８０６：セレクタ５１６は、左側の入力を選択する。これにより除数レジスタ５０２の内容が、セレクタ５１６を経て、商数列記憶装置５０３に格納され、動作を終了する。
【００３８】
以上の動作により、商数列記憶装置５０３には、図９に示すように、商数列全部が格納され、その後に最後の除算に使用された除数が格納される。
【００３９】
商数列から制御数列を生成する制御数列計算装置１０４は、図６に示すように、生成された制御数列を格納する制御数列記憶装置６０１と、制御数列記憶装置６０１のアドレスを指示するアドレスポインタ６０２、６０３と、商数列記憶装置５０３のアドレスを指示するポインタ６０４と、制御数列計算装置１０４の各部を制御して制御数列記憶装置６０１の中に制御数列を生成する制御数列制御装置６０５とを備えている。なお、商数列記憶装置５０３とそのアドレスを指示するアドレスポインタ５０７とは、図５の５０３及び５０７そのものであり、アドレスポインタ５０７は、商数列記憶装置５０３に格納されたデータの最後のアドレス位置をポイントしている。
【００４０】
この制御数列計算装置１０４の動作を説明する前に、制御数列と商数列との関係を具体例を用いて説明する。
【００４１】
後述するように、直線が７／１８の傾きを有する場合、即ち、Ｍ０の値が１８、Ｍ１の値が７である場合には、描画点は図２０に示すように描かれる。この制御数列は｛１００１０１００１００１０１００１０｝であり、直線に沿ってこの数列の単位が繰返される。水平格子線上に並ぶ描画点の個数は３の場合と２の場合とがあり、制御数列をこの二種類のブロックの組合せとして、「１００」「１０」「１００」「１００」「１０」「１００」「１０」と表すことができる。この「１００」のブロックをＢ１タイプ、「１０」のブロックをＡ１タイプとすると、Ａ１タイプは水平格子線上にＱ１（Ｑ１＝２）個の描画点が並び、Ｂ１タイプはＱ１＋１個の描画点が並んでいる。つまり、商数列の最初のＱ１の値により、Ａ１タイプ及びＢ１タイプのブロックに含まれる描画点の数が決まってくる。
【００４２】
また、制御数列は、このＡ１及びＢ１を用いて、Ｂ１，Ａ１，Ｂ１，Ｂ１，Ａ１，Ｂ１，Ａ１のブロックの連結として表すことができるが、これはＢ１の後に続くＡ１の数が１のブロックと、Ｂ１の後に続くＡ１の数が０のブロックとの組合せ、即ち、「Ｂ１Ａ１」「Ｂ１」「Ｂ１Ａ１」「Ｂ１Ａ１」と表すことができる。この「Ｂ１Ａ１」をＢ２タイプ、「Ｂ１」をＡ２タイプとすると、Ａ２タイプはＱ２（Ｑ２＝１）個のブロックを含み、Ｂ２タイプはＱ２＋１個のブロックを含んでいる。つまり、商数列の次のＱ２の値により、Ａ２タイプ及びＢ２タイプに含まれるブロック数が決まってくる。
【００４３】
また、制御数列は、このＡ２及びＢ２を用いて、Ｂ２，Ａ２，Ｂ２，Ｂ２のブロックの連結として表すことができるが、これはＢ２の後に続くＡ２の数が１のブロックと、Ｂ２の後に続くＡ２の数が０のブロックとの組合せ、即ち、「Ｂ２Ａ２」「Ｂ２」「Ｂ２」と表すことができる。この「Ｂ２Ａ２」をＢ３タイプ、「Ｂ２」をＡ３タイプとすると、Ａ３タイプはＱ３（Ｑ３＝１）個のブロックを含み、Ｂ３タイプはＱ３＋１個のブロックを含んでいる。つまり、商数列のその次のＱ３の値により、Ａ３タイプ及びＢ３タイプに含まれるブロック数が決まってくる。
【００４４】
また、制御数列は、このＡ３及びＢ３を用いて、Ｂ３，Ａ３，Ａ３のブロックの連結として表すことができるが、これはＢ３の後にＡ３が２つ続く１つのブロックである。これをＡ４タイプとすると、Ａ４タイプはＱ４（Ｑ４＝３）個のブロックを含んでいる。つまり、商数列のその次のＱ４の値により、Ａ４タイプに含まれるブロック数が決まってくる。
【００４５】
この段階のＡ４のように、Ｂ４に対応するブロックが存在しない状態は、商数列の算出において剰余が０の状態に相当している。このときＡ４×Ｍ（Ｍは除数レジスタ５０２の内容。この具体例の場合Ｍ＝１）が制御数列となる。
【００４６】
さて、制御数列計算装置１０４の制御数列制御装置６０５は、商数列とこのような関係にある制御数列を、商数列記憶装置５０３に格納されている商数列を用いて、制御数列記憶装置６０１の中に生成する。その手順を図１０及び図１１に示すフローチャートを用いて説明する。
【００４７】
ステップ１００１：制御数列制御装置６０５は、制御数列記憶装置６０１の第１ワード（即ちアドレス０）に“１”を書き込む。更に商数列ポインタ６０４の内容を０に設定する。これによりアドレスポインタ６０４は、商数列記憶装置５０３の第１番地、即ちＱ１が格納されている番地を指示する。
【００４８】
ステップ１００２：制御数列制御装置６０５は、アドレスポインタ６０４の指示するアドレスを読み出し（この場合はアドレス０を読むことになるのでＱ１が読み出される）、制御数列記憶装置６０１の第２ワード（即ちアドレス１）から、今読み出された値の個数だけ、即ち、Ｑ１個だけの語にデータ“０”を書き込む。
【００４９】
ステップ１００３：次いで、制御数列制御装置６０５は、アドレスポインタ６０２に数値Ｑ１−１を、アドレスポインタ６０３に数値Ｑ１を書込み、
ステップ１００４：アドレスポインタ６０４の内容を１だけ増加する。
【００５０】
このときの制御数列記憶装置６０１の内容とアドレスポインタ６０２及びアドレスポインタ６０３のポイント位置とを図１２に示している（アドレス０からポインタ６０２の指し示すアドレスＱ１−１までのデータが、先の具体例のＡ１タイプのデータであり、アドレス０からポインタ６０３の指し示すアドレスＱ１までのデータがＢ１タイプのデータとなる）。
【００５１】
次に、制御数列制御装置６０５は、図１１に示す手順に従って、
ステップ１１０１：商数列記憶装置５０３からポインタ６０４の指示する番地を読出す。この時読み出される値は、これまでに読み出された商数列の次の要素である。この値をＱｎとする。
【００５２】
ステップ１１０２：制御数列記憶装置６０１の先頭番地、即ち、０番地からアドレスポインタ６０２が指示する番地までの内容をＱｎ回繰り返して、アドレスポインタ６０３の指示する番地の次の番地から始まる領域にコピーする（この操作は、先の具体例において、ブロックＢｎ−１の後にブロックＡｎ−１をＱｎ回繋げてブロックＢｎを生成することに相当している）。この動作を図示したものが図１３である。即ち、ゼロ番地からポインタ６０２が指示する番地までの内容をＣａ，ｎとすると、Ｃａ，ｎをＱｎ繰り返してアドレスポインタ６０３の指示する番地の次から始まる領域へコピーする。
【００５３】
ステップ１１０３：アドレスポインタ６０３には格納最終番地を格納する。即ち、アドレスポインタ６０３は破線で示した番地を指示することになる（アドレス０からアドレスポインタ６０３のポイントする番地までのデータが先の具体例におけるブロックＢｎのデータとなる）。更に、アドレスポインタ６０３から以前のアドレスポインタ６０２の内容を減じた値に更に１を減じた値をアドレスポインタ６０２に格納する。即ち、アドレスポインタ６０２は図１３の破線で示した番地を指示するようになる（アドレス０からアドレスポインタ６０２のポイントする番地までのデータが先の具体例におけるブロックＡｎのデータとなる）。この段階で０番地からアドレスポインタ６０２の指示する番地までの内容がＣａ，ｎ＋１、０番地からアドレスポインタ６０３の指示する番地までの内容がＣｂ，ｎ＋１となっている。この後、アドレスポインタ６０４の内容を１だけ増加する。
【００５４】
ステップ１１０４：ポインタ６０４の内容とポインタ５０７の内容とを比較し、不一致であればステップ１１０１へ移行する。一致した場合は、
ステップ１１０５：既に商数列のすべての要素についてステップ１１０１〜ステップ１１０３を実行したことになる。従って、式（２−１３）を計算する過程に移行する。ポインタ６０４が指示している番地を読み出す。即ち、ＭＮが読み出される。
【００５５】
ステップ１１０６：制御数列記憶装置６０１の０番地からアドレスポインタ６０２の指示する番地にはＣａ，Ｎが格納されている。従って、これをＭＮ−１回繰り返してアドレスポインタ６０２の指示する番地の次の番地から始まる領域に格納する。これにより、ＭＮ＊Ｃａになる。
【００５６】
ステップ１１０７：最終格納番地をアドレスポインタ６０２に格納する。これにより、０番地からアドレスポインタ６０２の指示する番地までの内容が制御数列Ｃとなる。
【００５７】
こうして生成された制御数列記憶装置６０１の内容の内、０番地からポインタ６０２の指示する番地までに格納されたデータが求める制御数列となる。
【００５８】
制御数列から描画点の座標Ｘ、Ｙを計算する座標計算装置１０５は、図７に示すように、制御数列記憶装置６０１のアドレスを指示するポインタ７０１と、制御数列記憶装置６０１から読みだされたデータを格納するバッファ７０２と、描画点のＸ座標を保持するレジスタ７０４と、描画点のＹ座標を保持するレジスタ７０５と、バッファ７０２から出力された値とレジスタ７０５から出力された値とを加算する加算器７０３と、座標計算装置の各部を制御する座標計算制御装置７０６とを備えている。なお、制御数列記憶装置６０１及びアドレスポインタ６０２は、図６の６０１及び６０２そのものであり、アドレスポインタ６０２は制御数列記憶装置６０１の最終格納番地を指し示している。
【００５９】
座標計算制御装置７０６は、制御数列記憶装置６０１から制御数列の要素を最初から一つずつ読み出し、これを基に描画点の座標（Ｘ，Ｙ）を出力する。その動作をフローチャートにしたものが図１４である。以下、図１４に沿って動作を説明する。但しレジスタ７０４と７０５には、それぞれ（Ｘ，Ｙ）の初期値、即ち最初の描画点の座標が格納されているものとする。
【００６０】
ステップ１４０１：ポインタ７０１をゼロに設定する。これによりポインタ７０１は制御数列記憶装置６０１の先頭番地を指示することになる。
【００６１】
ステップ１４０２：座標計算制御装置７０６は、ポインタ７０１の指示する番地を読み出すための制御信号７１０をＯＮにして、その読み出されたデータをバッファ７０２に格納する。
【００６２】
ステップ１４０３：座標計算制御装置７０６は、信号７１１をＯＮにする。これによりレジスタ７０４は格納している値を１だけ増加する。同時にレジスタ７０５は、加算器７０３から出力された値、即ち、レジスタ７０５がそれまで保持していた値にバッファ７０２の内容を加えた値を格納する。バッファ７０２の内容は０または１であるので、レジスタ７０５の内容は元のままの値かあるいは１だけ増加した値となる。
【００６３】
ステップ１４０４：レジスタ７０４と７０５の出力を描画点の座標（Ｘ，Ｙ）として描画する。
【００６４】
ステップ１４０５：座標計算制御装置７０６は、ポインタ７０１とポインタ６０２の保持する値同志を比較する。両者の内容が一致していればステップ１４０１へ移る。内容が一致するということは制御数列の最終要素を使ってステップ１４０２〜ステップ１４０３を実行したことを意味する。
【００６５】
ポインタ７０１とポインタ６０２の内容が不一致である場合は、
ステップ１４０６：ポインタ７０１の内容を１だけ増加し、制御数列の次の要素を読み出す準備をする。この後、ステップ１４０２へ移行する。
【００６６】
以上の動作により、描画点の座標（Ｘ，Ｙ）が次々と生成され出力７１３と出力７１４とに出力される。
【００６７】
以上の動作を具体的数値例を用いて再度説明する。Ｍ０とＭ１の値をそれぞれ１８と７であるとして説明する。この場合、商数列Ｑは以下の計算より式（２−１５）のようになる。この商数列は、４回の除算で生成することができる。
【００６８】
１８＝２×７＋４ より Ｑ１＝２，Ｍ１＝７，Ｍ２＝４
７＝１×４＋３ より Ｑ２＝１， Ｍ３＝３
４＝１×３＋１ より Ｑ３＝１， Ｍ４＝１
３＝３×１＋０ より Ｑ４＝３， Ｍ５＝０
Ｑ＝｛２，１，１，３｝ （２−１５）
図１のレジスタ１０１と１０２とにそれぞれ数値１８と７とが格納されている状態から説明を始める。まず、商数列制御装置５１０は、ステップ８０１とステップ８０２とを実行すると、商数列記憶装置５０３の０番地に数値２が、レジスタ５０４に数値４が格納される。次に、ステップ８０３を実行し、剰余レジスタ５０４の内容がゼロでないのでステップ８０４の実行へ移る。これによりポインタ５０７の内容は１となる。次にステップ８０５を実行すると、レジスタ５０１とレジスタ５０２にはそれぞれ数値７と４が格納される。再度ステップ８０２の実行により、商数列記憶装置５０３の１番地とレジスタ５０４にそれぞれ数値１と３とがそれぞれ格納される。この後、ステップ８０３、８０４、８０５を実行した後、第３回のステップ８０２の実行で商数列記憶装置５０３の２番地に１が、レジスタ５０４に１が格納される。
【００６９】
更にステップ８０３、８０４、８０５を実行した後、第４回目のステップ８０２の実行により、商数列記憶装置５０３の３番地に数値３が、レジスタ５０４に数値０が格納される。この後ステップ８０３を実行すると、剰余レジスタ５０４の値がゼロであるので、ステップ８０６により、レジスタ５０２の内容、即ち数値１が商数列記憶装置５０３に格納される。この後、動作は終了する。この結果、商数列記憶装置５０３には、商数列
Ｑ＝｛２，１，１，３｝
と、その後にＭ４、即ち数値１が記憶され、商数列記憶装置５０３の内容は図１５のようになり、ポインタ５０７は最終要素格納番地、即ち４番地を指示した状態になる。以上の過程をまとめると表１のようになる。
【００７０】
次に、制御数列計算過程の説明に移る。図１５のように、商数列Ｑと除数列Ｍの最終要素ＭＮとが商数列記憶装置５０３に記憶された状態で制御数列制御装置６０５がステップ１００１〜ステップ１００４を実行する。即ち、制御数列制御装置６０５は、商数列記憶装置５０３の先頭アドレスを読み出す。この結果、数値“２”が読み出されるので、制御数列記憶装置６０１は図１６のような状態になる。即ち、０番地に数値１が書き込まれ、その次から２語に数値０が書き込まれた状態になる。ポインタ６０２と６０３にはそれぞれ数値“１”と“２”が保持される。
【００７２】
次に、制御数列制御装置６０５が、再度ステップ１１０１〜ステップ１１０４を実行すると、制御数列記憶装置６０１の内容は図１７のようになる。即ち、ステップ１１０１において商数列記憶装置５０３から読み出される値は“１”であるから、図１７の０番地からポインタ６０２の指示する番地の内容、即ち｛１，０｝が１回だけ３番地から始まる領域にコピーされる。この後、ポインタ６０３には数値４が、ポインタ６０２には数値４−１−１、即ち数値２が格納される。
【００７３】
この後、ポインタ６０４とポインタ５０７の内容が比較される。それぞれには数値１と４が格納されているので、再度ステップ１１０１〜ステップ１１０３が実行される。この結果、制御数列記憶装置６０１の内容は図１８のようになる。
【００７４】
この後、ポインタ６０４の内容は２であるから、第３回目のステップ１１０１〜ステップ１１０３が実行され、制御数列記憶装置６０１の内容は図１９のようになる。この後、ステップ１１０４を実行すると、ポインタ６０４の内容はポインタ５０７と一致する。従って、ステップ１１０５〜ステップ１１０７が実行されるが、Ｍ４の値は１であるのでステップ１１０６は０回繰り返される。従って、制御数列記憶装置６０１の０番地からポインタ６０２の指示する１７番地までの内容が求める制御数列となり、ここで終了する。以上の過程をまとめると表２のようになる。
【００７５】
次に、この結果に基づいて、座標計算装置１０５の動作を説明する。説明を簡単にするため（Ｘ，Ｙ）の初期値は（０，０）とする。一般には最初の描画点Ｐｎ（Ｘ０，Ｙ０）である場合には初期値を（Ｘ０−１，Ｙ０−１）にすれば良い。
【００７７】
まず、座標計算制御装置７０６がステップ１４０１〜ステップ１４０３を実行すると、信号線７１３と７１４とには１と１とが出力される。レジスタ７０４は１だけ増加するから“１”となる。レジスタ７０５にも１が加算されるから“１”となる。これは制御数列記憶装置６０１の先頭番地の内容、即ち１が読み出されるからである。第２回目のステップ１４０１〜ステップ１４０３を実行すると、出力７１３と７１４とにはそれぞれ“２”と“１”が出力される。これは、出力７１３の出力は毎回１だけ増加するが、出力７１４、即ちＹ出力は今回は増加しない。これは制御数列記憶装置６０１の第２ワード、即ち１番地には“０”が書かれているからである。
【００７８】
このようにしてステップ１４０２〜ステップ１４０６のループが繰り返されると、出力７１３と７１４は表３のように変化していく。これを描画点にしたものが、図２０である。
【００７９】
【００８０】
第３節 数学的証明
以上のように、式（２−３）〜（２−１３）によって制御数列を求め、式（２−１）、（２−２）によって描画点の座標を算出する描画方法は、従来の方法（例えば図３の方法）で得られる、直線Ｌの最も良い近似点を表す座標と同一の座標を生成する。このことの数学的説明を以下に述べる。
【００８１】
本発明の描画方法は、式（２−１１）及び（２−１２）の関係が成立することに基盤を置いている。この関係におけるｎ＝１，ｎ＝２，ｎ＝３及びｎが一般の値を取る場合について説明する。
【００８２】
直線Ｌの傾きをＭ１／Ｍ０（Ｍ１、Ｍ０は整数）とする。そしてＭ１、Ｍ０に対して、式（２−３）〜（２−６）が成立しているものとする。図２１のように、直線Ｌを近似する描画点Ｐｉが同一水平格子線上に並ぶ個数をＫ１とすると
Ｋ１＝Ｑ１ （３−１）
または
Ｋ１＝Ｑ１＋１ （３−２）
である。式（３−１）及び（３−２）の証明は後の＜証明１＞に述べる。図２２のように、描画点が水平にＱ１＋１個並んだものをまとめてＢ１タイプのブロックとし、図２３のように、描画点が水平にＱ１個並んだものをまとめてＡ１タイプのブロックと呼ぶことにする。すると、直線Ｌを近似する描画点の集合は、図２４のようにＡ１とＢ１の２種類のブロックを連結したものになる。このようにＫ１が１だけ異なる２つの値を取り得るのは、式（２−４）において、
Ｍ２≠０
の場合である。言い換えれば、Ｍ０がＭ１で割り切れれば、Ｋ１はＱ１の値だけを取る。
【００８３】
図２４のように、Ｂ１タイプのブロックから数えて次のＢ１タイプのブロックが出現するまでのブロックの個数をＫ２とする。言い換えればＡ１タイプのブロックが連続する個数をＫ２−１とすると
Ｋ２＝Ｑ２ （３−３）
または
Ｋ２＝Ｑ２＋１ （３−４）
である。式（３−３）及び（３−４）の証明は＜証明２＞に示す。
【００８４】
従って、タイプＢ１のブロックの次にタイプＡ１のブロックがＱ２個続く場合と、Ｑ２−１個続く場合とが存在する。図２５のように前者をブロックＢ２、後者をブロックＡ２と呼ぶことにする。更に、タイプＢ２のブロックから数えて次のタイプＢ２のブロックが出現するまでのブロック数をＫ３とすると、同様に
Ｋ３＝Ｑ３ （３−５）
または
Ｋ３＝Ｑ３＋１ （３−６）
である。このことの証明は＜証明３＞に述べる。
【００８５】
一般に図２６のように、ブロックＢｍから次のブロックＢｍまでのブロック数をＫｍ＋１とすると、
Ｋｍ＋１＝Ｑｍ＋１ （３−７）
または
Ｋｍ＋１＝Ｑｍ＋１＋１ （３−８）
である。このことを更に厳密に表現すると以下のようになる。即ち、一般に、ある直線Ｌに対して垂直格子線上で最も近い格子点列を次の条件を満たす２つの集合ＡｍとＢｍとに分けることができる。そして、これらのＡｍとＢｍとは、式（２−４）の集合Ｑの要素である整数Ｑｍに対して次の関係を持つ。
【００８６】
Ａｍ＝Ｂｍ−１＆（Ｑｍ−１）＊Ａｍ−１ （３−９）
Ｂｍ＝Ｂｍ−１＆Ｑｍ＊Ａｍ−１ （３−１０）
但し、Ｘ＆Ｙは集合Ｘの右に集合Ｙを接続したものを意味し、α＊Ｙは集合Ｙをα個接続したものを意味する。このことの証明は＜証明４＞に述べる。
【００８７】
このようにＫｍが１だけ異なる２つの値を取るのは、式（２−４）のＭｍ＋１≠０であるからである。このようなプロセスをｎ＝Ｎとなるまで続けることができる。ｎ＝Ｎとなると式（２−４）の余りはゼロ、即ち
ＭＮ＋１＝０
であるから以後、描画点はブロックＡＮだけの繰り返しとなる。
【００８８】
図２６から分かるように、ブロックＡｎはブロックＢｎ−１のうしろにＱｎ−１個のブロックＡｎ−１を接続したものであり、ブロックＢｎはこれにもう一つブロックＡｎ−１を接続したものである。従って、ブロックＡｎとＢｎの制御数列をそれぞれＣａ，ｎ，Ｃｂ，ｎとすると
Ｃａ，ｎ＝Ｃｂ，ｎ−１＆（Ｑｎ−１）＊Ｃａ，ｎ−１
Ｃｂ，ｎ＝Ｃａ，ｎ＆Ｃａ，ｎ−１
即ち、式（２−１１）、（２−１２）を得ることができる。ＭＮはＭ０とＭ１との最大公約数であるからｎ＝Ｎの以後はＡＮの繰り返しとなり、式（２−１３）を得る。
【００８９】
＜証明１＞
図２１のように直線Ｌを近似する描画点Ｐｉ〜Ｐｊが、同一水平線上に並ぶ個数をＫ１とする。直線の傾きは整数比Ｍ１／Ｍ０とする。簡単のため格子間隔は１とする。真の点、即ち、直線Ｌと垂直の格子線と交点をＴｉ〜Ｔｊとする。垂直方向でＴｉに最も近い点、即ち描画点をＰｉとする。真の点ＴｉのＹ座標から描画点ＰｉのＹ座標の値を引いたものをＲｉとし、これを点Ｐｉの残差と呼ぶことにする。点ＰｉからＰｊまでが水平格子線Ｈ１の上にあり、点Ｐｉ−１はＨ０上に、点Ｐｊ＋１はＨ２上にあるとする。真の点Ｔｉと描画点Ｐｉとの位置の差Ｒｉは、
−１／２≦Ｒｉ＜１／２ （４−１）
である。直線の傾きはＭ１／Ｍ０であるから、ＴｉのＹ座標はＴｉ−１のＹ座標よりＭ１／Ｍ０だけ大きい。Ｔｉ−１は一本下の水平格子線Ｈ０の方に近い。従ってＰｉのＹ座標はＰｉ−１のＹ座標よりも１だけ大きい。このことから（４−１）より更に強い条件を導くことができる。即ち
Ｒｉ＝Ｒｉ−１＋（Ｍ１／Ｍ０）−１ （４−２）
であるから、（４−２）を（４−１）に代入して
１／２−Ｍ１／Ｍ０＜Ｒｉ−１ （４−３）
となる。結局、右隣の描画点が一本上の格子線上に存在する描画点Ｐｉ−１について
１／２−Ｍ１／Ｍ０≦Ｒｉ−１＜１／２ （４−４）
の関係が成立する。このことはＰｊについても成立するから
１／２−Ｍ１／Ｍ０≦Ｒｊ＜１／２ （４−５）
またＰｉ−１からＰｊまでの距離はＫ１であるから
Ｒｊ＝Ｒｉ−１＋Ｋ１（Ｍ１／Ｍ０）−１ （４−６）
であるから、式（４−４）、（４−５）、（４−６）よりＲｉ−１、Ｒｊを消去すると
Ｍ０／Ｍ１−１＜Ｋ１＜Ｍ０／Ｍ１＋１ （４−７）
となる。ここでＭ０＝Ｑ１Ｍ１＋Ｍ２であるから
Ｑ１＋（Ｍ２／Ｍ１）−１＜Ｋ１＜Ｑ１＋（Ｍ２／Ｍ１）＋１ （４−８）
である。Ｋ１は整数であり、０＜Ｍ２／Ｍ１＜１であるから
Ｋ１＝Ｑ１
または
Ｋ１＝Ｑ１＋１
である。証明終わり。
【００９０】
＜証明２＞
図２２のように、Ｂ１タイプのブロックの左端の描画点の更に左の描画点ＰＢ１Ｌの残差（以下、Ｂ１の左残差と呼ぶ）をＲＢ１Ｌとする。また、Ｂ１の右端の描画点ＰＢ１Ｒの残差をＲＢ１Ｒとする。ＰＢ１Ｌ、ＰＢ１Ｒの両方ともその右隣の描画点は一本上の水平格子線上に存在する。従って式（４−４）から
１／２−Ｍ１／Ｍ０≦ＲＢ１Ｌ＜１／２ （５−１）
１／２−Ｍ１／Ｍ０≦ＲＢ１Ｒ＜１／２ （５−２）
また、
△Ｂ１＝ＲＢ１Ｒ−ＲＢ１Ｌ （５−３）
とすると、△Ｂ１はタイプＢ１のブロックが引き起こす残差の変化分である。タイプＢ１のブロックは、Ｑ１＋１個の水平描画点を持つから１点につきＭ１／Ｍ０だけ残差は増加する。また、ＰＢ１ＲはＰＢ１Ｌより１本上の格子線上にあるから、残差は１だけ減じられる。従って
△Ｂ１＝（Ｑ１＋１）Ｍ１／Ｍ０−１＝（Ｍ１−Ｍ２）／Ｍ０ （５−４）
となる。
【００９１】
また、同様に、Ａ１タイプの左残差をＲＡ１Ｒ、このブロックの右に隣接するブロックの左残差をＲＡ１Ｒ、Ａ１タイプのブロックが引き起こす残差の変化分を△Ａ１とすると
１／２−Ｍ１／Ｍ０≦ＲＡ１Ｌ＜１／２ （５−５）
１／２−Ｍ１／Ｍ０≦ＲＡ１Ｒ＜１／２ （５−６）
△Ａ１＝ＲＡ１Ｒ−ＲＡ１Ｌ （５−７）
△Ａ１＝Ｑ１Ｍ１／Ｍ０−１＝−Ｍ２／Ｍ０ （５−８）
となる。式（５−１）、（５−２）、（５−３）、（５−４）からＲＢ１Ｒ、△Ｂ１を消去すると
１／２−Ｍ１／Ｍ０≦ＲＢ１Ｌ＜１／２−（Ｍ１−Ｍ２）／Ｍ０ （５−９）
また、式（５−５）、（５−６）、（５−７）、（５−８）からＲＡ１Ｒ、△Ａ１を消去すると
１／２−（Ｍ１−Ｍ２）／Ｍ０≦ＲＡ１Ｌ＜１／２ （５−１０）
となる。
【００９２】
図２４の第１番目のＢ１タイプのブロック２４１から、次のＢ１タイプのブロック２４４の直前までのブロック数をＫ２とする。ブロック２４１はＢ１タイプであるからその左残差は
１／２−Ｍ１／Ｍ０≦ＲＢ１Ｌ＜１／２−（Ｍ１−Ｍ２）／Ｍ０ （５−１１）
である。ブロック２４４もタイプＢ１であるから、このブロックの左残差をＲＢ１Ｎとすると
１／２−Ｍ１／Ｍ０≦ＲＢ１Ｎ＜１／２−（Ｍ１−Ｍ２）／Ｍ０」 （５−１２）
である。Ａ１タイプの並ぶ個数はＫ２−１個であるから
ＲＢ１Ｎ＝ＲＢ１Ｌ＋△Ｂ１＋（Ｋ２−１）△Ａ１ （５−１３）
となる。式（５−４）、（５−８）、（５−１３）より
ＲＢ１Ｎ＝ＲＢ１Ｌ＋（Ｍ１−Ｍ２）／Ｍ０−（Ｋ２−１）Ｍ２／Ｍ０ （５−１４）
であるから、（５−１１）、（５−１２）、（５−１４）より
（Ｍ１／Ｍ２）−１＜Ｋ２＜（Ｍ１／Ｍ２）＋１ （５−１５）
である。式（２−４）に従って
Ｍ１＝Ｑ２Ｍ２＋Ｍ３
だから
Ｑ２＋（Ｍ３／Ｍ２）−１＜Ｋ２＜Ｑ２＋（Ｍ３／Ｍ２）＋１ （５−１６）
となる。ここで０＜Ｍ３／Ｍ２＜１でＫ２は整数だから
Ｋ２＝Ｑ２
または
Ｋ２＝Ｑ２＋１
である。証明終り。
【００９３】
＜証明３＞
図２５の２５１及び２５４のように、Ｂ１タイプのブロックの次にＡ１タイプのブロックがＱ２個連続するものをＢ２タイプのブロック、Ｑ２−１個連続するものをＡ２タイプのブロックとする。任意のＢ２タイプのブロックからその右方に存在するＢ２タイプのブロックの直前までのブロック数をＫ３個とする。Ｂ２タイプのブロック２５１の左残差をＲＢ２Ｌ、Ａ２タイプのブロック２５２の左残差をＲＡ２Ｌとする。これらはそれぞれ左端にＢ１タイプのブロックが在るからＢ１タイプの左残差を持ち、式（５−９）より
１／２−Ｍ１／Ｍ０≦ＲＢ２Ｌ＜１／２−（Ｍ１−Ｍ２）／Ｍ０ （６−１）
１／２−Ｍ１／Ｍ０≦ＲＡ２Ｌ＜１／２−（Ｍ１−Ｍ２）／Ｍ０ （６−２）
となる。ブロック２５１にはＢ１タイプのブロックが１個、Ａ１タイプのブロックがＱ２個並んでいるから
△Ｂ２＝ＲＡ２Ｌ−ＲＢ２Ｌ＝△Ｂ１＋Ｑ２△Ａ１ （６−３）
となる。ブロック２５３の左残差をＲＡ２Ｎとすると
△Ａ２＝ＲＡ２Ｎ−ＲＡ２Ｌ＝△Ｂ１＋（Ｑ２−１）△Ａ１ （６−４）
となる。式（６−３）、（６−４）の△Ａ１、△Ｂ１に（５−４）、（５−８）を代入すると
△Ａ２＝Ｍ３／Ｍ０ （６−５）
△Ｂ２＝−（Ｍ２−Ｍ３）／Ｍ０ （６−６）
となる。式（６−１）、（６−２）、（６−３）、（６−６）より
１／２−（Ｍ１−Ｍ２＋Ｍ３）／Ｍ０≦ＲＢ２Ｌ＜１／２−（Ｍ１−Ｍ２）／Ｍ０ （６−７）
を得る。ブロック２５４の左残差をＲＢ２Ｎとすると、ＲＢ２Ｎも式（６−７）を満足しなければならないから
１／２−（Ｍ１−Ｍ２＋Ｍ３）／Ｍ０≦ＲＢ２Ｎ＜１／２−（Ｍ１−Ｍ２）／Ｍ０ （６−８）
となる。ブロック２５１から次のＢ２タイプのブロック２５４までには、Ａ２タイプのブロックがＫ３−１個存在するから
ＲＢ２Ｎ＝ＲＢ２Ｌ＋△Ｂ２＋（Ｋ３−１）△Ａ２ （６−９）
であり、式（６−７）、（６−８）、（６−９）より
−Ｍ３／Ｍ０＜△Ｂ２＋（Ｋ３−１）△Ａ２＜Ｍ３／Ｍ０ （６−１０）
を得る。△Ａ２＞０、△Ｂ２＜０であることを考慮して、式（６−５）、（６−６）、（６−１０）から△Ａ２、△Ｂ２を消去すると
Ｑ３＋Ｍ４／Ｍ３−１＜Ｋ３＜Ｑ３＋Ｍ４／Ｍ３＋１ （６−１１）
０＜Ｍ４／Ｍ３＜１で、Ｋ３は整数だから
Ｋ３＝Ｑ３
または
Ｋ３＝Ｑ３＋１
である。証明終り。
【００９４】
＜証明４＞
一般式を数学的帰納法によって証明する。即ち、式（７−１）〜（７−６）が成立しているものとして、式（７−７）〜（７−１２）を導出する。
【００９５】
Ａｎ＝Ｂｎ−１＆（Ｑｎ−１）＊Ａｎ−１ （７−１）
Ｂｎ＝Ｂｎ−１＆Ｑｎ＊Ａｎ−１ （７−２）
Ｗａ，ｎ−１＜Ｒａ，ｎ−１＜Ｕａ，ｎ−１ （７−３）
Ｗｂ，ｎ−１＜Ｒｂ，ｎ−１＜Ｕｂ，ｎ−１ （７−４）
△Ａｎ−１＝（Ｓｎ−１−Ｓｎ）／Ｍ０ （７−５）
△Ｂｎ−１＝（Ｓｎ−２−Ｓｎ）／Ｍ０ （７−６）
Ａｎ＋１＝Ｂｎ＆（Ｑｎ＋１−１）＊Ａ （７−７）
Ｂｎ＋１＝Ｂｎ＆Ｑｎ＋１＊Ａｎ （７−８）
Ｗａ，ｎ＜Ｒａ，ｎ＜Ｕａ，ｎ （７−９）
Ｗｂ，ｎ＜Ｒｂ，ｎ＜Ｕｂ，ｎ （７−１０）
△Ａｎ＝（Ｓｎ−Ｓｎ＋１）／Ｍ０ （７−１１）
△Ｂｎ＝（Ｓｎ−１−Ｓｎ＋１）／Ｍ０ （７−１２）
但し、Ｕａ，ｎ、Ｕｂ，ｎ、Ｗａ，ｎ、Ｗｂ，ｎはｎが奇数の場合と偶数の場合とで、それぞれ以下の値を取る。即ち、
ｎが奇数の場合
Ｕａ，ｎ＝−１／２＋Ｓｎ−１／Ｍ０ （７−１３）
Ｕｂ，ｎ＝Ｗａ，ｎ＝−１／２＋Ｓｎ＋１／Ｍ０ （７−１４）
Ｗｂ，ｎ＝−１／２＋Ｓｎ／Ｍ０ （７−１５）
ｎが偶数の場合
Ｕａ，ｎ＝Ｗｂ，ｎ＝−１／２＋Ｓｎ＋１／Ｍ０ （７−１６）
Ｕｂ，ｎ＝−１／２＋Ｓｎ／Ｍ０ （７−１７）
Ｗａ，ｎ＝−１／２＋Ｓｎ−１／Ｍ０ （７−１８）
である。また、
Ｓｎ＝Ｍ０−Ｍ１＋Ｍ２＋…＋（−１）ｎＭｎ （７−１９）
である。また、式（７−１９）におけるＭ１，Ｍ２，‥，Ｍｎは式（２−８）の除数列の要素である。
【００９６】
式（７−３）におけるＲａ，ｎ−１は図２６のタイプＡｎ−１のブロック２６０２の最左端の描画点の左残差である。また、式（７−４）におけるＲｂ，ｎ−１はタイプＢｎ−１の最左端の描画点の左残差である。また、△Ａｎ−１はタイプＡｎ−１のブロックの残差の増分である。即ち、ブロック２６０３の最左端の描画点の左残差からブロック２６０２の最左端の描画点の左残差を差し引いた値である。△Ｂｎ−１はタイプＢｎの残差の増分である。即ち、ブロック２６０２の最左端の描画点の左残差Ｒａ，ｎ−１から、ブロック２６０１の最左端の描画点の左残差Ｒｂ，ｎ−１を差し引いた値である。
【００９７】
式（７−１）、（７−２）は、次のことを意味している。即ち、
（１）垂直方向で最も直線に近い描画点群は、図２６のようにタイプＡｎ−１とタイプＢｎ−１の２種類の形状のブロックに分けることができる。
（２）これらのブロックの連鎖はタイプＢｎ−１の右にＱｎ−１個のタイプＡｎ−１のブロックが接続する場合と、タイプＢｎ−１の右にＱｎ個のタイプＡｎ−１のブロックが接続する場合とが存在する。また、この場合だけが存在する。前者をタイプＡｎ、後者をタイプＢｎとする。
【００９８】
上記（１）と（２）及び式（７−３）〜（７−６）を前提として、式（７−７）〜（７−１２）を導出する。まず（１）、（２）より
△Ａｎ＝△Ｂｎ−１＋（Ｑｎ−１）△Ａｎ−１ （７−２０）
△Ｂｎ＝△Ｂｎ−１＋Ｑｎ△Ａｎ−１＝△Ａｎ＋△Ａｎ−１ （７−２１）
である。これに（７−５）、（７−６）を代入すると
【００９９】
図２６において、ブロック２６０５の左残差をＲｂ，ｎ、ブロック２６０７のそれをＲａ，ｎとする。Ｒｂ，ｎはブロック２６０１の左残差の条件を満たさなければならないから、
Ｗｂ，ｎ−１＜Ｒｂ，ｎ＜Ｕｂ，ｎ−１ （７−２２）
更にＲｂ，ｎ＋△Ｂｎはブロック２６０６の左残差を満たさなければならないから、
Ｗｂ，ｎ−１＜Ｒｂ，ｎ＋△Ｂｎ＜Ｕｂ，ｎ−１ （７−２３）
また、Ｒａ，ｎはブロック２６０６の左残差を満たさねばならないから
Ｗｂ，ｎ−１＜Ｒａ，ｎ＜Ｕｂ，ｎ−１ （７−２４）
また、Ｒａ，ｎ＋△Ａｎはブロック２６１１の左残差の条件を満たさねばならないから、
Ｗｂ，ｎ−１＜Ｒａ，ｎ＋△Ａｎ＜Ｕｂ，ｎ−１ （７−２５）
である。
【０１００】
以上をもとに（７−２２）〜（７−２５）より（７−９）〜（７−１０）を導出するが、ｎが奇数の場合と偶数の場合に分けて導出する。まず、ｎが奇数の場合、（７−１１）、（７−１２）、（７−１９）より
△Ａｎ＜０
△Ｂｎ＜０
である。従って（７−２２）、（７−２３）、（７−２４）、（７−２５）より
Ｗｂ，ｎ−１＜Ｒｂ，ｎ＜Ｕｂ，ｎ−１−△Ｂｎ （７−２６）
Ｗｂ，ｎ−１−△Ａｎ＜Ｒａ，ｎ＜Ｕｂ，ｎ−１ （７−２７）
を得る。ｎは奇数だから、ｎ−１は偶数である、（７−１６）、（７−１７）、（７−１８）より
−１／２＋Ｓｎ／Ｍ０＜Ｒｂ，ｎ＜−１／２＋Ｓｎ＋１／Ｍ０ （７−２８）
また、（７−１６）、（７−１７）より
Ｗｂ，ｎ−１−△Ａｎ＝−１／２＋Ｓｎ／Ｍ０−（Ｓｎ−Ｓｎ＋１）／Ｍ０
＝−１／２＋Ｓｎ＋１／Ｍ０
Ｕｂ，ｎ−１＝−１／２＋Ｓｎ−１／Ｍ０
従って
−１／２＋Ｓｎ＋１／Ｍ０＜Ｒａ，ｎ＜−１／２＋Ｓｎ−１／Ｍ０ （７−２９）
以上から
Ｕｂ，ｎ＝−１／２＋Ｓｎ＋１／Ｍ０
Ｗｂ，ｎ＝−１／２＋Ｓｎ／Ｍ０
Ｕａ，ｎ＝−１／２＋Ｓｎ−１／Ｍ０
Ｗａ，ｎ＝−１／２＋Ｓｎ＋１／Ｍ０
よって（７−１３）、（７−１４）、（７−１５）が導出された。
【０１０１】
次にｎが偶数の場合は
△Ａｎ＞０
△Ｂｎ＜０
である。従って（７−２２）、（７−２３）、（７−２４）、（７−２５）より
Ｗｂ，ｎ−１−△Ｂｎ＜Ｒｂ，ｎ＜Ｕｂ，ｎ−１
Ｗｂ，ｎ−１＜Ｒａ，ｎ＜Ｕｂ，ｎ−１−△Ａｎ
を得る。ｎは偶数だからｎ−１は奇数であり、（７−１４）、（７−１５）より
−１／２＋Ｓｎ＋１／Ｍ０＜Ｒｂ，ｎ＜−１／２＋Ｓｎ／Ｍ０
または（７−１３）、（７−１４）より
−１／２＋Ｓｎ＋１／Ｍ０＜Ｒａ，ｎ＜−１／２＋Ｓｎ−１／Ｍ０
以上から
Ｕｂ，ｎ＝−１／２＋Ｓｎ／Ｍ０
Ｗｂ，ｎ＝−１／２＋Ｓｎ＋１／Ｍ０
Ｕａ，ｎ＝−１／２＋Ｓｎ＋１／Ｍ０
Ｗａ，ｎ＝−１／２＋Ｓｎ−１／Ｍ０
よって（７−１６）、（７−１７）、（７−１８）が導出された。
【０１０２】
以上から、ｎが奇数の場合、偶数の場合とも式（７−９）、（７−１０）が導出されたことになる。
【０１０３】
次に式（７−７）、（７−８）を導出する。図２６のようにタイプＡｎのブロックとタイプＢｎのブロックとに描画点群は分けられると仮定して、２つのタイプＢｎのブロック２６０５と２６１０との間にＫｎ＋１−１個のタイプＡｎのブロックが存在したとする。ブロック２６０５と２６１０とは両方ともタイプＢｎであるから、
Ｗｂ，ｎ＜Ｒｂ，ｎ＜Ｕｂ，ｎ （７−１０）
Ｗｂ，ｎ＜Ｒｂ，ｎ＋△Ｂｎ＋（Ｋｎ＋１−１）△Ａｎ＜Ｕｂ，ｎ （７−３０）
を満たす。
【０１０４】
−Ｕｂ，ｎ＜−Ｒｂ，ｎ＜−Ｗｂ，ｎ （７−３１）
であるから、式（７−３０）、（７−３１）の両辺を加算しＲｂ，ｎを消去すると
−（Ｕｂ，ｎ−Ｗｂ，ｎ）＜△Ｂｎ＋（Ｋｎ＋１−１）△Ａｎ＜Ｕｂ，ｎ−Ｗｂ，ｎ （７−３２）
を得る。（７−１１）、（７−１２）より
△Ｂｎ−△Ａｎ＝−（−１）ｎＭｎ／Ｍ０ （７−３３）
また、式（７−１３）、（７−１４）、（７−１７）、（７−１８）より、ｎが奇数の場合も偶数の場合も
Ｕｂ，ｎ−Ｗｂ，ｎ＝Ｍｎ＋１／Ｍ０ （７−３４）
である。（７−３２）、（７−３３）、（７−３４）より
−｛Ｍｎ＋１−（−１）ｎＭｎ｝／Ｍ０＜Ｋｎ＋１×△Ａｎ＜｛Ｍｎ＋１＋（−１）ｎＭｎ｝／Ｍ０ （７−３５）
ｎが奇数の場合も偶数の場合も
Ｍｎ／Ｍｎ＋１−１＜Ｋｎ＋１＜Ｍｎ／Ｍｎ＋１＋１ （７−３６）
となる。（２−４）より
Ｑｎ＋１＋Ｍｎ＋２／Ｍｎ＋１−１＜Ｋｎ＋１＜Ｑｎ＋１＋Ｍｎ＋２／Ｍｎ＋１＋１
０＜Ｍｎ＋２／Ｍｎ＋１＜１でかつＫｎ＋１は整数だから
Ｋｎ＋１＝Ｑｎ＋１
または
Ｋｎ＋１＝Ｑｎ＋１＋１
である。
【０１０５】
以上から、Ｂｎの右にＡｎがＱｎ＋１−１個接続される場合と、Ｂｎの右にＡｎがＱｎ＋１個接続される場合とが存在することが分かる。前者をＡｎ＋１、後者をＢｎ＋１とすれば、式（７−７）、（７−８）が導出されたことになる。従って、タイプＡｎ−１のブロックとタイプＢｎ−１のブロックとが接続されてできる連鎖は、次の２つのブロックの連鎖に分けることができる。即ち、
タイプＡｎのブロック：１個のタイプＢｎ−１のブロックにＱｎ−１個のタイプＡｎ−１のブロックが接続されたブロック
タイプＢｎのブロック：１個のタイプＢｎ−１のブロックにＱｎ個のタイプＡｎ−１のブロックが接続されたブロック
の２つである。ｎ＝１及びｎ＝２の場合は、それぞれ＜証明１＞及び＜証明２＞によって成立している。従って、数学的帰納法により１からＮまでのすべてのｎについて、（７−７）〜（７−１９）が成立する。証明終り。
【０１０６】
本発明の直線描画装置は、描画点の座標を高速に計算できる。直線の傾きを整数比、即ちＭ１／Ｍ０とすると、以下の作業で描画点の座標を計算できる。
【０１０７】
（ア）Ｍ１とＭ０とから商数列を計算する。
【０１０８】
（イ）商数列から制御数列を計算する。
【０１０９】
（ウ）制御数列をもとに一描画点あたり、２回の加算で座標を生成する。
【０１１０】
上記（ア）（イ）の演算操作は、描画点の数に比例しない。直線の傾きＭ１／Ｍ０だけから少数回の演算で実行できる。従って描画点の個数が多くなればなるほど効果がある。また、（ア）（イ）の演算操作は、描画の開始前に実行を済ませておくことができる。従って描画中には（ウ）の演算操作だけを行なえばよく、高速な描画が可能である。（ウ）の演算は“１”または“０”を加算する演算であるから、この部分を簡単なハードウエアで実現することも可能である。これに対して従来の方法、例えば図３のような例では描画と同時に座標計算のための数値演算と条件判定とを行なわなければならなかった。本発明はこのような欠点を克服するものである。
【０１１１】
更に（イ）で生成される制御数列は最小周期の情報であるから、描画点の数が多くても繰り返し利用することができる。加えて、Ｂｒｅｓｅｎｈａｍのアルゴリズム同様、丸め誤差が積算することはなく、描画点数によらず正確な描画が出来る。即ち、本発明の装置によって生成される描画点はＢｒｅｓｅｎｈａｍのアルゴリズムによって生成されるものと同一になる。
【０１１２】
また、本装置の描画方法では、水平に並ぶ描画点の数を簡単な計算で予め算出することが出来る。従って、描画中に次に描画すべき点の座標を算出する必要はなく、描画以前にすべての点を算出するデータを得ることができる。もちろん描画と並列して描画点を算出することも可能である。描画中に判定操作も減算操作も不要である。従って、従来の方式に比べて大幅に描画時間を短縮できる。
【０１１３】
（実施の形態２）
第２の実施形態の直線描画装置は、図２７に示すように、除算の代わりに減算を行なって制御数列を生成する統合計算装置２７１を備えており、座標計算装置２７２は、この統合計算装置２７１の生成した制御数列に基づいて直線を描画する。
【０１１４】
この装置の利点は
（１）除算器を必要としない。
（２）商数列記憶装置を必要としない。
の２点にある。
【０１１５】
この統合計算装置２７１は、２８図に示すように、Ｍ１の値を保持するレジスタ１０２と、Ｍ０の値を保持するレジスタ１０１と、入力する３つの値の１つを選択して出力するセレクタ２８１７と、セレクタ２８１７の出力を保持する減数レジスタ２８０６と、入力する値から減数レジスタ２８０６の値を減算する減算器２８０７と、減算器２８０７、減数レジスタ２８０６またはレジスタ１０１の出力値の内の１つを選択して出力するセレクタ２８０８と、セレクタ２８０８の出力を保持する残余レジスタ２８０５と、減数レジスタ２８０６の内容が“１”であるか否かを検出する１検出器２８１６と、残余レジスタ２８０５の内容がゼロであることを検出するゼロ検出器２８１４と、生成された制御数列を記憶する制御数列記憶装置２８０１と、制御数列記憶装置２８０１に対するアドレスポインタ２８０２、２８０３と、統合計算装置２７１の各部を制御する統合制御装置２８０４とを備えている。
【０１１６】
この装置では、減算器２８０７が、残余レジスタ２８０５の値から減数レジスタ２８０６の値を減算し、この減算を一回行なう毎に、統合制御装置２８０４が制御数列記憶装置２８０１の内容を一部変更する。そして、この繰り返しにより、最終的に制御数列が制御数列記憶装置２８０１の内部に生成される。
【０１１７】
この装置の動作を図２９のフローチャートを用いて説明する。図２９のフローチャートは、ステップ２９０１による初期状態設定の後に、ステップ２９０２を起点として次の４つのルートを持つ。即ち、
ルート１：ステップ２９０２、ステップ２９０３、ステップ２９０４、ステップ２９０５、ステップ２９０６、ステップ２９０７を通過してステップ２９０２へ戻るルート
ルート２：ステップ２９０２、ステップ２９０３、ステップ２９１０、ステップ２９１１を通過してステップ２９０２へ戻るルート
ルート３：ステップ２９０２、ステップ２９０３、ステップ２９０４、ステップ２９０５、ステップ２９０８、ステップ２９０９を通過してステップ２９０２へ戻るルート
ルート４：ステップ２９０２、ステップ２９１２、ステップ２９１３を通過してステップ２９０２へ戻るルート
の４つである。
【０１１８】
以下、初期状態の設定（ステップ２９０１）及び上記４つのルートにおける動作を順に説明する。なお、このフローチャートでは、（Ａ）は装置Ａの内容を表すものとする。従って（Ａ）→Ｂは、装置ＡまたはＡ番地の内容を装置Ｂに転送することを意味する。
【０１１９】
このフローチャートは、ルート１をＱ１回実行した後、ルート２を１回実行する。この後、ルート３をＱｍ回実行した後、ルート２を１回実行するということをｍ＝２〜Ｎまで実行し、最後にルート４を１回実行する。
【０１２０】
＜初期状態設定＞
ステップ２９０１：まず、統合制御装置２８０４は、セレクタ２８１７に対して一番左の入力信号を選択するための信号２７１８を、また、セレクタ２８０８に対して一番右の入力信号を選択するための信号を出力し、また、減数レジスタ２８０６及び残余レジスタ２８０５に対して入力データの格納を指示する信号２８１５を出力する。これを受けて減数レジスタ２８０６はセレクタ２８１７から出力されたＭ１の値を格納し、また、残余レジスタ２８０５はセレクタ２８０８から出力されたＭ０の値を格納する。また、統合制御装置２８０４は、ポインタ（Ｐａ）２８０２及びポインタ（Ｐｂ）２８０３に、制御数列記憶装置２８０１の０番地を指示するようにゼロを格納し、制御数列記憶装置２８０１のＰｂ２８０３の指示する番地に信号線２８１１を通じて“１”を格納する（（Ｐｂ）←“１”）。従って、制御数列記憶装置２８０１の０番地にデータ１が格納される。
【０１２１】
＜ルート１＞
初期状態の設定の後、
ステップ２９０２：統合制御装置２８０４は、ゼロ検出器２８１４の出力を調べ、残余レジスタ２８０５の内容がゼロでないときは、
ステップ２９０３：減算器２８０９から出力される、減算結果の負を表す信号２８１０がＯＮかどうかを調べる。減算器２８０７は、これに先立って、残余レジスタ２８０５から読出した値から減数レジスタ２８０６に保持されている値を減算する演算を行なう。統合制御装置２８０４は、この信号２８１０によって、減数レジスタ２８０６の値と残余レジスタ２８０５の値との大小関係を識別し、減数レジスタ２８０６の値の方が残余レジスタ２８０５の値より小さければ、
ステップ２９０４：統合制御装置２８０４は、制御信号により、セレクタ２８０８に最も左の入力を選択するように指示し、また、残余レジスタ２８０５に信号２８１５を出力して、入力データの格納を指示する。その結果、残余レジスタ２８０５には、セレクタ２８０８の選択した減算器２８０７の出力、即ち、残余レジスタ２８０５の内容から減数レジスタ２８０６に保持されている内容を減じた値が格納される。
【０１２２】
ステップ２９０５：Ｐａ２８０２の内容が０のときは、
ステップ２９０６：統合制御装置２８０４は、制御数列記憶装置２８０１のＰｂ２８０３の値に１を加算したアドレスに“０”を格納し、
ステップ２９０７：Ｐｂ２８０３に、今まで保持している値に１を加算した値を新たに保持させる。次いで、ステップ２９０２に戻る。
【０１２３】
このルートがＱ１回実行される。なぜなら、Ｍ０からＭ１を減ずることを、結果が負になる直前まで実行するからである。このＱ１は式（２−７）におけるＱ１と同じである。Ｑ１回実行後の制御数列記憶装置２８０１の内容は図１２と同一となる（但し、Ｐａはアドレス０を指している）。
【０１２４】
Ｑ１回の上記減算の実行の後では、残余レジスタ２８０５の内容の方が減数レジスタ２８０６の内容より小さくなっている。従って、減算器２８０７の出力２８１０はＯＮとなり減算結果が負になることが表示される。統合制御装置２８０４は、この信号を検出しステップ２９０３から分岐しルート２を辿る。
【０１２５】
＜ルート２＞
ステップ２９１０：減算器２８０７の出力２８１０がＯＮとなると、セレクタ２８０８は中側の入力、即ち、減数レジスタ２８０６の内容を通過させる。従って、残余レジスタ２８０５には、それまで減数レジスタ２８０６に保持されていた内容Ｍ１が格納される。また、統合制御装置２８０４は、これ以上減算をすると結果が負になるという場合に、セレクタ２８１７に対して最も右の入力を選択するように指示し、その結果、減数レジスタ２８０６には、それまでの残余レジスタ２８０５の内容が格納される。従って減数レジスタ２８０６にはＭ０−Ｑ１Ｍ１、即ち、Ｍ２が格納される。
【０１２６】
ステップ２９１１：信号２８１０がＯＮになると、統合制御装置２８０４はＰａ２８０２及びＰｂ２８０３の値を読み出し、Ｐｂ−Ｐａ−１の演算を行ない、その結果をＰａ２８０２に格納する。これによりＰａ２８０２は図１２の位置を指示する状態に移る。
【０１２７】
＜ルート３＞
ルート２を通過した後、ルート３を通過する。このルートでは、ステップ２９０２、ステップ２９０３、ステップ２９０４はルート１と同一であり、残余レジスタ２８０５の内容から減数レジスタ２８０６に保持された値Ｍ２が減算され、減算値が残余レジスタ２８０５に格納される。
【０１２８】
ステップ２９０５：Ｐａ２８０２がゼロではないので、ステップ２９０８に移行し、
ステップ２９０８：統合制御装置２８０４は、制御数列記憶装置２８０１とデータの送受を行ないながら、制御数列記憶装置２８０１の０番地からＰａ２８０２の指示する番地までの内容を、Ｐｂ２８０３の指示する番地の次の番地から始まる領域にコピーする。
【０１２９】
ステップ２９０９：次いで、このコピー操作の格納最終番地をＰｂ２８０３が指示するように設定する。
【０１３０】
この後、ステップ２９０２に戻り、同じ手順を繰り返す。この繰り返しをＱ２回行ない、残余レジスタ２８０５の値が減数レジスタ２８０６の値Ｍ２より小さくなると、ルート２を通過し、減数レジスタ２８０６に保持されていた値Ｍ２を残余レジスタ２８０５に格納し、それまでの残余レジスタ２８０５の格納値Ｍ１−Ｑ２・Ｍ２、即ちＭ３を減数レジスタ２８０６に格納する。その後、さらにルート３を繰り返す。
【０１３１】
第２回目以降のルート２の通過により、残余レジスタ２８０５にはＭｍが格納され、減数レジスタ２８０６にはＭｍ＋１が格納される。従って、その後のルート３は、残余レジスタ２８０５、減数レジスタ２８０６にそれぞれＭｍ、Ｍｍ＋１が格納されている状態で始まり、残余レジスタ２８０５の内容が減数レジスタ２８０６の値で減算され、減算値が負になる直前まで繰り返され、残余レジスタ２８０５にＭｍ−Ｑｍ＋１・Ｍｍ＋１が、減数レジスタ２８０６にＭｍ＋１が格納された状態で終える。その後のルート２の通過により、残余レジスタ２８０５にＭｍ＋１が、減数レジスタ２８０６にＭｍ−Ｑｍ＋１・Ｍｍ＋１、即ちＭｍ＋２が格納される。
【０１３２】
このルートをＱｍ回繰り返して実行すると、ステップ１１０２〜１１０３を実行した場合と同一の結果（図１３の状態）が得られる。
【０１３３】
＜ルート４＞
ルート２、ルート３の実行を繰り返した後に、残余レジスタ２８０５の内容が減数レジスタ２８０６の内容で割り切れるようになると、残余レジスタ２８０５の内容はゼロになるので、ステップ２９０２から分岐し、ルート４の操作が実行される。このルート４は式（２−１３）の計算を行なうための準備をするものである。
【０１３４】
ステップ２９１２：統合制御装置２８０４は、１検出器２８１６から出力される信号を調べることによって、減数レジスタ２８０６の内容が“１”であるか否かを識別する。減数レジスタ２８０６の内容が１である場合は、制御数列記憶装置２８０１に記憶された数列が既に制御数列であるため、式（２−１３）の計算は実際には不要になる。そこで、すべての操作を終了して良い。
【０１３５】
ステップ２９１３：減数レジスタ２８０６の内容が１でないということは、ＭＮ≠１で且つＭＮ＋１＝０であるということであるから、式（２−１３）の計算を行なう。そのためには、ルート３をＭＮ回通過すれば良い。そこで、残余レジスタ２８０５には減数レジスタ２８０６の内容、即ち、ＭＮを、また、減数レジスタ２８０６には“１”を設定する。
【０１３６】
次いで、ルート３の通過を繰り返す。ルート３を１回通過するごとに、ＭＮから１が減算され、ＭＮ回の通過が終了した時点で残余レジスタ２８０５の値がゼロになり、それをゼロ検出器２８１４が統合制御装置２８０４に伝えて、制御数列生成の操作が終了する。
【０１３７】
このように、第２の実施形態の装置は、除算器を必要とせず、簡単な構造で直線の描画を行なうことができる。
【０１３８】
【発明の効果】
以上の説明から明らかなように、本発明の直線描画装置は、描画点を得るための操作回数を従来に比べて大幅に減らすことができ、高速での描画作業が可能になる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態における直線描画装置の構成を示すブロック図、
【図２】直線を格子点で近似する描画の例、
【図３】直線と格子点との関係を説明する図、
【図４】従来の直線描画方式の一例、
【図５】第１の実施形態の直線描画装置における商数列計算装置の構成を示すブロック図、
【図６】第１の実施形態の直線描画装置における制御数列計算装置の構成を示すブロック図、
【図７】第１の実施形態の直線描画装置における座標計算装置の構成を示すブロック図、
【図８】前記商数列計算装置の動作を説明するフローチャート、
【図９】前記制御数列計算装置における制御数列記憶装置の内容を説明する図、
【図１０】前記制御数列計算装置の動作を説明するフローチャート、
【図１１】前記制御数列計算装置の動作を説明するフローチャートの続き、
【図１２】前記制御数列記憶装置の内容と２つのアドレスポインタとの関係を示す図、
【図１３】前記制御数列記憶装置の内容の変化を説明する図、
【図１４】前記座標計算装置の動作を説明するフローチャート、
【図１５】前記商数列記憶装置の内容の具体例、
【図１６】前記制御数列記憶装置の内容の変化の具体例（その１）、
【図１７】前記制御数列記憶装置の内容の変化の具体例（その２）、
【図１８】前記制御数列記憶装置の内容の変化の具体例（その３）、
【図１９】前記制御数列記憶装置の内容の変化の具体例（その４）、
【図２０】前記具体例における描画点を示す図、
【図２１】本発明の基礎となる数学的事実を証明するための図（その１）、
【図２２】本発明の基礎となる数学的事実を証明するための図（その２）、
【図２３】本発明の基礎となる数学的事実を証明するための図（その３）、
【図２４】本発明の基礎となる数学的事実を証明するための図（その４）、
【図２５】本発明の基礎となる数学的事実を証明するための図（その５）、
【図２６】本発明の基礎となる数学的事実を証明するための図（その６）、
【図２７】本発明の第２の実施形態における直線描画装置の構成を示すブロック図、
【図２８】第２の実施形態の直線描画装置における統合計算装置の構成を示すブロック図、
【図２９】前記統合計算装置の動作を説明するフローチャートである。
【符号の説明】
１０１、１０２ レジスタ
１０３ 商数列計算装置
１０４ 制御数列計算装置
１０５、２７２ 座標計算装置
２７１ 統合計算装置
５０１ 被除数レジスタ
５０２ 除数レジスタ
５０３ 商数列記憶装置
５０４ 剰余レジスタ
５０５ 除算器
５０６ ゼロ検出器
５０７、６０２、６０３、６０４、７０１、２８０２、２８０３ アドレスポインタ
５０８、５０９、５１６、２８０８、２８１７ セレクタ
５１０ 商数列制御装置
６０１ 制御数列記憶装置
６０５ 制御数列制御装置
７０２ バッファ
７０３ 加算器
７０４ Ｒｘレジスタ
７０５ Ｒｙレジスタ
７０６ 座標計算制御装置
２８０１ 制御数列記憶装置
２８０４ 統合制御装置
２８０５ 残余レジスタ
２８０６ 減数レジスタ
２８０７ 減算器
２８１４ ゼロ検出器
２８１６ １検出器
Claims (3)
- 格子点上に直線の近似点を描画する直線描画装置において、
直線の傾きを定める第１及び第２の整数をそれぞれ保持する第１及び第２の整数保持手段と、
前記第１及び第２の整数保持手段に保持された２つの整数による除算で商と余りとを求め、次に、先行する除算の除数を被除数とし、余りを除数とする除算を繰り返して各除算の商から成る商数列を計算する商数列計算手段と、
前記商数列から、隣接する描画点間の格子点上の差異を表す制御数列を計算する制御数列計算手段と、
前記制御数列から描画点の座標を計算する座標計算手段と
を備え、前記商数列計算手段は、前記商数列を求める際、除算の結果の余りが生じた場合、除算の余りが０になるまで計算を繰り返すことを特徴とする直線描画装置。 - 前記商数列計算手段が、被除数を保持する被除数保持手段と、除数を保持する除数保持手段と、前記被除数保持手段に保持された被除数を前記除数保持手段に保持された除数で除算する除算手段と、前記除算における商を保持する商数列保持手段と、前記除算における余りを保持する余り保持手段と、前記余り保持手段の内容がゼロであることを検出するゼロ検出手段とを具備し、前記被除数保持手段及び除数保持手段が最初にそれぞれ前記第１の整数及び第２の整数を保持し、前記除算手段の除算が行なわれた後、前記除数保持手段の内容を前記被除数保持手段に転送し、前記余り保持手段の内容を前記除数手段に転送して、前記除算手段の次の除算を行ない、これを前記余り保持手段の内容がゼロとなるまで繰り返すことを特徴とする請求項１に記載の直線描画装置。
- 前記制御数列計算手段が、生成された制御数列を記憶する制御数列記憶手段と、前記制御数列記憶手段の第１のアドレスを保持する第１のポインタと、前記制御数列記憶手段の第２のアドレスを保持する第２のポインタと、商数列を記憶する商数列記憶手段とを具備し、前記制御数列記憶手段の０番地から前記第１のポインタの指示する番地までの内容を複製の単位として、前記商数列記憶手段から読出した商数列要素の値の回数だけ複製して、前記制御数列記憶手段の前記第２のポインタが指示する番地の次の番地から始まる領域に格納し、前記第２のポインタの保持するアドレスを前記格納後の最終番地に変更し、前記第１のポインタの保持するアドレスを、次の複製の単位となる番地に変更し、この動作を、前記商数列記憶手段に記憶された商数列要素について１回ずつ繰り返すことを特徴とする請求項１に記載の直線描画装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP34472595A JP3552823B2 (ja) | 1995-12-07 | 1995-12-07 | 直線描画装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP34472595A JP3552823B2 (ja) | 1995-12-07 | 1995-12-07 | 直線描画装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH09161082A JPH09161082A (ja) | 1997-06-20 |
| JP3552823B2 true JP3552823B2 (ja) | 2004-08-11 |
Family
ID=18371500
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP34472595A Expired - Fee Related JP3552823B2 (ja) | 1995-12-07 | 1995-12-07 | 直線描画装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3552823B2 (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100435258B1 (ko) * | 1997-09-03 | 2004-07-16 | 삼성전자주식회사 | 컴퓨터 그래픽의 3차원 직선 그리는 방법 |
-
1995
- 1995-12-07 JP JP34472595A patent/JP3552823B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JPH09161082A (ja) | 1997-06-20 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6295072B1 (en) | Method and apparatus for rendering cubic curves | |
| CN111951348A (zh) | 确定框选区域的方法、装置及电子设备 | |
| JP3552823B2 (ja) | 直線描画装置 | |
| US5179647A (en) | Method and apparatus for implementing adaptive forward differencing using integer arithmetic | |
| JP4255467B2 (ja) | デジタルガンマ補正回路およびデジタルガンマ補正方法 | |
| JPH03144782A (ja) | 三次元図形処理装置 | |
| US9286654B2 (en) | Image scaling processor and image scaling processing method | |
| JPH0567216A (ja) | 図形塗りつぶし装置 | |
| JP2008009719A (ja) | 直線描画方法、直線描画プログラム及び直線描画装置 | |
| JPH0785266A (ja) | 画像回転装置 | |
| JP3280160B2 (ja) | 文書処理装置および文書処理方法 | |
| JP5072558B2 (ja) | データ処理装置 | |
| JP2802646B2 (ja) | ベクトルフオントによる文字パターンの変倍処理方法 | |
| US12093691B2 (en) | Loop unrolling processing apparatus, method, and program | |
| JP2748787B2 (ja) | 曲線発生装置 | |
| JPS62219164A (ja) | 高速投影算出回路 | |
| JPH04260982A (ja) | 直線ピクセル生成器及び直線ピクセル生成方法 | |
| JPH01166177A (ja) | 太線描画方法 | |
| JP2713400B2 (ja) | 投影情報生成装置 | |
| JP2541697B2 (ja) | パイプライン演算装置 | |
| JP3181956B2 (ja) | 図形データ格納方法および装置 | |
| JPH0575844A (ja) | 情報生成装置 | |
| CN115687841A (zh) | 一种国土控制面积计算审核系统 | |
| JP2770560B2 (ja) | 図形処理装置 | |
| JPH0248780A (ja) | 直線発生装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20040113 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20040312 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20040427 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20040427 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090514 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100514 Year of fee payment: 6 |
|
| LAPS | Cancellation because of no payment of annual fees |