JPH0258634B2 - - Google Patents
Info
- Publication number
- JPH0258634B2 JPH0258634B2 JP16712580A JP16712580A JPH0258634B2 JP H0258634 B2 JPH0258634 B2 JP H0258634B2 JP 16712580 A JP16712580 A JP 16712580A JP 16712580 A JP16712580 A JP 16712580A JP H0258634 B2 JPH0258634 B2 JP H0258634B2
- Authority
- JP
- Japan
- Prior art keywords
- dot
- candidate
- dots
- displacement
- point
- 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
Links
Landscapes
- Control Of Indicators Other Than Cathode Ray Tubes (AREA)
Description
本発明は、線図形発生装置、特に円弧、円など
の線図形をドツトの集合として表示する際の、す
なわち例えば電光掲示板のように電球（ドツト）
が格子状に配列されている表示面ないしはこれと
等価な表示面に線図形を描くための線分発生装置
に関するものである。 従来、この種装置はグラヒツクデイスプレイ装
置や電光掲示板に線図形を表示する装置として広
く用いられているが、この種装置に要求される最
も重要な条件は、アルゴリズム（発生手順）が
簡易であること、発生速度が速いこと、発生
しようとする線図形に最も近いドツトを選択する
こと（高精度であること）である。すでに、ブレ
ゼンハム（Bresenham）、メツチガー
（Metzger）、ダニエルソン（Danielsson）らが
各々線図形発生のアルゴリズムを提案している
が、上記要求条件を充分に満足することのできる
アルゴリズムが望まれている。その後、「円弧信
号発生装置」（特公昭53−20809号公報）が提案さ
れ上記要求条件をほぼ満足させる装置の実現が可
能となつたが、この種装置を集積回路で実現する
ときは、さらに装置構成の簡易化と発生速度の高
速化とが望まれている。 本発明は、「円弧信号発生装置」（特公昭53−
20809号公報）がドツトを選択するにあたり、２
つの候補ドツトの変位を求め、該変位の絶対値の
大小を比較し、最適なドツトを選択していたのに
対し、２つの候補ドツトの中間点の変位を１つだ
け求め、該中間点の変位の符号を逆転しようとす
る候補ドツトを最適ドツトとして選択するように
し、線図形発生の高速化と装置構成の簡易化とを
実現しようとするもので、以下図面を用いて詳細
に説明する。 第１図は線図形発生アルゴリズムのうちの線分
発生アルゴリズムの原理を説明する説明図であ
る。本発明の円弧と円との発生のアルゴリズムに
ついては第６図以降で説明する。第１図ａ，ｂは
開始ドツト（以後、始点と呼ぶ）PSと終了ドツト
（以後、終点と呼ぶ）PEとを結ぶ線分を発生する
際に線分をよく近似するドツトの選択方向を説明
している。すなわち、始点PSを相対原点と考えた
とき、終点PEがどの象限に存在するかによつて、
取りうるドツト（候補ドツト）が限定されること
を示している。線図形を発生するために始点PSの
次の候補ドツトとして、上下左右の４方向を考え
える場合（このような手法を４連結という）には
第１図ａの如くなることは容易に理解できよう。
もし、始点PSの次の候補ドツトとして、上下左右
のほかに、斜め方向まで考える場合（このような
手法を８連結と呼ぶ）は、第１図ｂに示すように
終点PEが、どのオクタントに存在するかによつ
て、候補ドツトが限定されるかも容易に理解でき
よう。 第２図は、４連結で線分を発生するアルゴリズ
ムを説明する説明図で、終点PEが第１象限に存
在する場合を示している。このとき、始点PSの次
に選択するドツトの候補はQ1，Q2であることは
第１図ａから容易に理解できる。そして、Q1と
Q2のいずれのドツトが線分PSPEを近似するにふ
さわしいかは、各々のドツトから線分PSPEに至
る距離d1，d2により決まり、距離の小さい方のド
ツトが最適であることも容易に理解できる。しか
し、このd1，d2を計算により求めることは煩雑で
ある。ところが、線分PSPEは第２図のｂのよう
に平面ｆ（ｘ，ｙ）＝ax−byとxy平面（ｆ（ｘ，
ｙ）＝０）との交線であるとも考えられるので、
候補ドツトQ1，Q2から平面ｆ（ｘ，ｙ）＝ax−by
に至る距離｜Z1｜｜Z2｜（Z1，Z2を変位と呼ぶ）
と前記d1，d2とは比例関係にあることは、第２図
ｂから理解できる（前記特公昭53−20809号公報
は、２つの候補ドツトの変位を求めて、その絶対
値を比較してその値が小さい方の候補ドツトを最
適ドツトとして選択している。その結果、計算の
回数が本発明より多いことが後で理解されよう）。
すると、２つの候補ドツトの中間点Q3を第２図
ａで考えた場合、第２図ｂのように該中間点Q3
の変位が負のとき、同じ符号の変位を有す候補点
Q1の変位の絶対値は、他の候補点Q2の変位の絶
対値よりも大きくなる。その場合は候補点Q2が
最適ドツトとなりうる。もし、中間点Q3の変位
が正のときは候補ドツトQ1が最適ドツトという
ことになる。本発明においては、このように候補
ドツトの中間点の変位の正負を調べることによ
り、最適ドツトを選択するアルゴリズムを用いる
ようにしている。これを、より具体的に述べるた
めに、始点の次に取りうる２つの候補ドツトの中
間点の変位ZQ3を求める。始点PSは発生すべき線
分PSPEの線上にあるので、始点PSの変位ZPSは当
然“０”であるから、終点PEが第１象限（ｂ＞
０，ａ＞０）に存在するならば ZQ3＝ｆ（xs＋１／２，ys＋１／２） ＝ZPS＋ａ／２−ｂ／２＝１／２（ａ−ｂ）……(1) となる。すると、終点PEが第１オクタント（ｂ
＞ａ＞０）に存在するならば、中間点Q3の変位
ZQ3は負となり、第２オクタント（ａ＞ｂ＞０）
に存在するならば正となる。また、第２図ａから
明らかなように、終点PEが第１オクタントに存
在するときは、中間点Q3は線分PSPEに対して、
候補ドツトQ1と同じ側にあり、d1＞d2となるの
で、候補ドツトQ2を最適ドツトとして選択する
のが妥当であることが理解できよう。 したがつて、終点が第第１象限にあるとき、中
間点Q3の変位ZQ3が負ならば候補点Q2（xS+1，yS）
を、正ならば候補点Q1（xS，yS+1）を最適ドツト
として選択すれば良いことが理解できよう。そし
て、候補ドツトQ2が最適ドツトとして選択され
たときは、その次の候補ドツトの中間点Q32の変
位ZQ32は、前回の候補ドツトの中間点Q3の座標を
（xQ3，yQ3）と定義すれば ZQ32＝ｆ（xQ3＋１，yQ3） ＝ｆ（xQ3，yQ3）＋ａ＝ZQ3+a ……(2) となり、候補ドツトQ1が最適ドツトとして選択
されたときの中間点Q31の変位ZQ31は ZQ31＝ｆ（xQ3，yQ3＋１） ＝ｆ（xQ3，yQ3）−ｂ＝ZQ3-b ……(3) となる。このようにして変位ZQ32ないしZQ31を求
め、その値が負ならば、次の最適ドツトとして前
回の最適ドツトQ1またはQ2の右隣りのドツトを、
正ならば上隣りのドツトを選択すれば良いことに
なる。 以後、候補ドツトから最適ドツトを選択した際
の選択方向によつて、式(2)ないし(3)を用いて累加
算し、選択した最適ドツトが終点PEに一致した
ら線分の発生を終了する。第２図ａは終点PEが
第１象限に存在する場合を示たが、他の象限に存
在する場合でも、候補ドツトが第１図ａの如く変
化するだけであり、その場合を含めると式(1)〜(3)
はつぎのように表わすことができる。 ZQ3＝ｆ（xS±１／２，yS±１／２）＝ZPS±ａ／２〓
ｂ／２＝ ±ａ／２〓ｂ／２ ……(4) ZQ32＝ｆ（xQ3±１，yQ3）＝ZQ3±ａ ……(5) ZQ3＝ｆ（xQ3，yQ3±１）＝ZQ3〓ｂ ……(6) いままでのことを第１表にまとめて示す。
の線図形をドツトの集合として表示する際の、す
なわち例えば電光掲示板のように電球（ドツト）
が格子状に配列されている表示面ないしはこれと
等価な表示面に線図形を描くための線分発生装置
に関するものである。 従来、この種装置はグラヒツクデイスプレイ装
置や電光掲示板に線図形を表示する装置として広
く用いられているが、この種装置に要求される最
も重要な条件は、アルゴリズム（発生手順）が
簡易であること、発生速度が速いこと、発生
しようとする線図形に最も近いドツトを選択する
こと（高精度であること）である。すでに、ブレ
ゼンハム（Bresenham）、メツチガー
（Metzger）、ダニエルソン（Danielsson）らが
各々線図形発生のアルゴリズムを提案している
が、上記要求条件を充分に満足することのできる
アルゴリズムが望まれている。その後、「円弧信
号発生装置」（特公昭53−20809号公報）が提案さ
れ上記要求条件をほぼ満足させる装置の実現が可
能となつたが、この種装置を集積回路で実現する
ときは、さらに装置構成の簡易化と発生速度の高
速化とが望まれている。 本発明は、「円弧信号発生装置」（特公昭53−
20809号公報）がドツトを選択するにあたり、２
つの候補ドツトの変位を求め、該変位の絶対値の
大小を比較し、最適なドツトを選択していたのに
対し、２つの候補ドツトの中間点の変位を１つだ
け求め、該中間点の変位の符号を逆転しようとす
る候補ドツトを最適ドツトとして選択するように
し、線図形発生の高速化と装置構成の簡易化とを
実現しようとするもので、以下図面を用いて詳細
に説明する。 第１図は線図形発生アルゴリズムのうちの線分
発生アルゴリズムの原理を説明する説明図であ
る。本発明の円弧と円との発生のアルゴリズムに
ついては第６図以降で説明する。第１図ａ，ｂは
開始ドツト（以後、始点と呼ぶ）PSと終了ドツト
（以後、終点と呼ぶ）PEとを結ぶ線分を発生する
際に線分をよく近似するドツトの選択方向を説明
している。すなわち、始点PSを相対原点と考えた
とき、終点PEがどの象限に存在するかによつて、
取りうるドツト（候補ドツト）が限定されること
を示している。線図形を発生するために始点PSの
次の候補ドツトとして、上下左右の４方向を考え
える場合（このような手法を４連結という）には
第１図ａの如くなることは容易に理解できよう。
もし、始点PSの次の候補ドツトとして、上下左右
のほかに、斜め方向まで考える場合（このような
手法を８連結と呼ぶ）は、第１図ｂに示すように
終点PEが、どのオクタントに存在するかによつ
て、候補ドツトが限定されるかも容易に理解でき
よう。 第２図は、４連結で線分を発生するアルゴリズ
ムを説明する説明図で、終点PEが第１象限に存
在する場合を示している。このとき、始点PSの次
に選択するドツトの候補はQ1，Q2であることは
第１図ａから容易に理解できる。そして、Q1と
Q2のいずれのドツトが線分PSPEを近似するにふ
さわしいかは、各々のドツトから線分PSPEに至
る距離d1，d2により決まり、距離の小さい方のド
ツトが最適であることも容易に理解できる。しか
し、このd1，d2を計算により求めることは煩雑で
ある。ところが、線分PSPEは第２図のｂのよう
に平面ｆ（ｘ，ｙ）＝ax−byとxy平面（ｆ（ｘ，
ｙ）＝０）との交線であるとも考えられるので、
候補ドツトQ1，Q2から平面ｆ（ｘ，ｙ）＝ax−by
に至る距離｜Z1｜｜Z2｜（Z1，Z2を変位と呼ぶ）
と前記d1，d2とは比例関係にあることは、第２図
ｂから理解できる（前記特公昭53−20809号公報
は、２つの候補ドツトの変位を求めて、その絶対
値を比較してその値が小さい方の候補ドツトを最
適ドツトとして選択している。その結果、計算の
回数が本発明より多いことが後で理解されよう）。
すると、２つの候補ドツトの中間点Q3を第２図
ａで考えた場合、第２図ｂのように該中間点Q3
の変位が負のとき、同じ符号の変位を有す候補点
Q1の変位の絶対値は、他の候補点Q2の変位の絶
対値よりも大きくなる。その場合は候補点Q2が
最適ドツトとなりうる。もし、中間点Q3の変位
が正のときは候補ドツトQ1が最適ドツトという
ことになる。本発明においては、このように候補
ドツトの中間点の変位の正負を調べることによ
り、最適ドツトを選択するアルゴリズムを用いる
ようにしている。これを、より具体的に述べるた
めに、始点の次に取りうる２つの候補ドツトの中
間点の変位ZQ3を求める。始点PSは発生すべき線
分PSPEの線上にあるので、始点PSの変位ZPSは当
然“０”であるから、終点PEが第１象限（ｂ＞
０，ａ＞０）に存在するならば ZQ3＝ｆ（xs＋１／２，ys＋１／２） ＝ZPS＋ａ／２−ｂ／２＝１／２（ａ−ｂ）……(1) となる。すると、終点PEが第１オクタント（ｂ
＞ａ＞０）に存在するならば、中間点Q3の変位
ZQ3は負となり、第２オクタント（ａ＞ｂ＞０）
に存在するならば正となる。また、第２図ａから
明らかなように、終点PEが第１オクタントに存
在するときは、中間点Q3は線分PSPEに対して、
候補ドツトQ1と同じ側にあり、d1＞d2となるの
で、候補ドツトQ2を最適ドツトとして選択する
のが妥当であることが理解できよう。 したがつて、終点が第第１象限にあるとき、中
間点Q3の変位ZQ3が負ならば候補点Q2（xS+1，yS）
を、正ならば候補点Q1（xS，yS+1）を最適ドツト
として選択すれば良いことが理解できよう。そし
て、候補ドツトQ2が最適ドツトとして選択され
たときは、その次の候補ドツトの中間点Q32の変
位ZQ32は、前回の候補ドツトの中間点Q3の座標を
（xQ3，yQ3）と定義すれば ZQ32＝ｆ（xQ3＋１，yQ3） ＝ｆ（xQ3，yQ3）＋ａ＝ZQ3+a ……(2) となり、候補ドツトQ1が最適ドツトとして選択
されたときの中間点Q31の変位ZQ31は ZQ31＝ｆ（xQ3，yQ3＋１） ＝ｆ（xQ3，yQ3）−ｂ＝ZQ3-b ……(3) となる。このようにして変位ZQ32ないしZQ31を求
め、その値が負ならば、次の最適ドツトとして前
回の最適ドツトQ1またはQ2の右隣りのドツトを、
正ならば上隣りのドツトを選択すれば良いことに
なる。 以後、候補ドツトから最適ドツトを選択した際
の選択方向によつて、式(2)ないし(3)を用いて累加
算し、選択した最適ドツトが終点PEに一致した
ら線分の発生を終了する。第２図ａは終点PEが
第１象限に存在する場合を示たが、他の象限に存
在する場合でも、候補ドツトが第１図ａの如く変
化するだけであり、その場合を含めると式(1)〜(3)
はつぎのように表わすことができる。 ZQ3＝ｆ（xS±１／２，yS±１／２）＝ZPS±ａ／２〓
ｂ／２＝ ±ａ／２〓ｂ／２ ……(4) ZQ32＝ｆ（xQ3±１，yQ3）＝ZQ3±ａ ……(5) ZQ3＝ｆ（xQ3，yQ3±１）＝ZQ3〓ｂ ……(6) いままでのことを第１表にまとめて示す。
【表】
第３図は８連結で線分発生するアルゴリズムに
ついての説明図である。８連結で線分発生する際
の候補ドツトは始点を相対原点としたときの終点
の存在するオクタントによつて決ることは第１図
ｂですでに説明した。第３図は終点が第１オクタ
ントに存在する場合を示しており、候補ドツトと
して、Q1とQ2があり、その中から最適ドツトは
第２ａ，ｂで説明した手順と全く同様にして得る
ことは理解できよう。その際、式(4)〜(6)はつぎの
ようになる。 (1) 終点が第１，４，５，８オクタントに存在す
るとき、 ZQ3＝ｆ（xS±１，yS±１／２）＝ZPS±ａ〓ｂ／２＝ ±ａ〓ｂ／２ ……(7) ZQ32＝ｆ（xQ3±１，yQ3）＝ZQ3±ａ ……(8) ZQ31＝ｆ（xQ3±１，yQ3±１）＝ZQ3±ａ〓ｂ
……(9) (2) 終点が第２，３，６，７オクタントに存在す
るとき ZQ3′＝ｆ（xS±１／２，yS±１）＝ZPS±ａ／２〓ｂ
＝ ±ａ／２〓ｂ ……(10) ZQ32′＝ｆ（xQ3′，yQ3′±１）＝ZQ3′〓ｂ……(11
) ZQ31′＝ｆ（xQ3′±１，yQ3′±１） ＝ZQ3′±ａ〓ｂ ……(12) ８連結の線分発生の論理表を第２表に示す。
ついての説明図である。８連結で線分発生する際
の候補ドツトは始点を相対原点としたときの終点
の存在するオクタントによつて決ることは第１図
ｂですでに説明した。第３図は終点が第１オクタ
ントに存在する場合を示しており、候補ドツトと
して、Q1とQ2があり、その中から最適ドツトは
第２ａ，ｂで説明した手順と全く同様にして得る
ことは理解できよう。その際、式(4)〜(6)はつぎの
ようになる。 (1) 終点が第１，４，５，８オクタントに存在す
るとき、 ZQ3＝ｆ（xS±１，yS±１／２）＝ZPS±ａ〓ｂ／２＝ ±ａ〓ｂ／２ ……(7) ZQ32＝ｆ（xQ3±１，yQ3）＝ZQ3±ａ ……(8) ZQ31＝ｆ（xQ3±１，yQ3±１）＝ZQ3±ａ〓ｂ
……(9) (2) 終点が第２，３，６，７オクタントに存在す
るとき ZQ3′＝ｆ（xS±１／２，yS±１）＝ZPS±ａ／２〓ｂ
＝ ±ａ／２〓ｂ ……(10) ZQ32′＝ｆ（xQ3′，yQ3′±１）＝ZQ3′〓ｂ……(11
) ZQ31′＝ｆ（xQ3′±１，yQ3′±１） ＝ZQ3′±ａ〓ｂ ……(12) ８連結の線分発生の論理表を第２表に示す。
【表】
以上、線分発生の原理を説明したが、さらに具
体的線分発生を行行つて説明する。たとえば始点
PS（０，０）、終点PE（５，２）の線分を発生した
例を第４図に示す。第４図ａは４連結で発生させ
たときのドツト変位、最適ドツトの選択方向（増
分の方向）の各関係を示し、第４図ｂは始点、終
点、選択された最適ドツトを実際にプロツトした
状態を示している。また、第４図ｃ，ｄは８連結
で発生させた場合を示している。なお第４図ａ，
ｃにおいて、Ａは始点、Ｂは選択された最適ドツ
ト、Ｃは終点を表わしている。 第５図は線分を発生する一例を示す。図中１は
終点Ｘレジスタ、２は終点Ｙレジスタ、３は中間
点Ｘカウンタ、４は中間点Ｙカウンタ、５はゲー
ト回路、６は制御部、７は最終中間点Ｘレジス
タ、８は比較器、９は最終中間点Ｙレジスタ、１
０は比較器、１１は変位レジスタ、１２は加算
器、１３は切換部、１４は増分発生部、１５は出
力制御部を表わしており、動作は以下のとおりで
ある。 本例では、始点から終点に至るまでの最適ドツ
トを、始点ないしはすでに発生された最適ドツト
の次に選択すべき最適ドツトを見たとき、その方
向が右方向（Ｘ＋）、左方向（Ｘ−）、上方向（Ｙ
＋）、下方向（Ｙ−）のうちいずれの方向にある
かを増分パルスで示す構成としている。もし、そ
の方向が斜め方向のときは上記４方向を組合せ
（たとえば右斜め上方向のときは、Ｘ＋，Ｙ＋）
で示すようにしている。 まず、始点の絶対アドレスを出力制御部１５に
セツトし、図示していない画面編集用メモリ等に
始点を書込む。そして始点を相対原点としたとき
の終点の相対Ｘアドレスを終点点Ｘレジスタ１
に、相対Ｙアドレスを終点Ｙレジスタ２にセツト
する。すると、制御部６は始点の次の最適ドツト
の中間点を求め、該中間点のＸアドレスを中間点
Ｘカウンタ３に、Ｙアドレスを中間点Ｙカウンタ
４に各々セツトする。また、制御装部６は終点の
次の候補ドツトの中間点のＸアドレスを最終中間
点Ｘレジスタ７に、Ｙアドレスを最終中間点Ｙレ
ジスタ９に各々セツトする。さらに、制御部６は
変位レジスタ１１をクリアする（上記制御部６の
動作を制御部６で行なわずに、あらかじめ外部で
演算し、初期設定するようにしてもよい）。終点
Ｘレジスタ１は初期設定された終点Ｘアドレスを
保持し、終点Ｙレジスタ２は初期設定された終点
Ｙアドレスを保持する。中間点Ｘカウンタ３は候
補ドツトの中間点のＸアドレスを、中間点Ｙカウ
ンタ４は候補ドツトの中間点のＹアドレスをそれ
ぞれ一時的に保持するもので、制御部６からのカ
ウントアツプないしはカウントダウンの信号によ
り増減し、最終中間点Ｘレジスタ７と最終中間点
Ｙレジスタ９との値に近づいていく。ゲート回路
５は外部からのクロツク入力制御を行なうもの
で、線分発生の開始を指示する信号Ａを得てから
比較器８と比較器１０とがともに一致検出するま
でクロツク信号Ｃを制御部６に供給する。制御部
６は前記初期設定のための動作の外に、ゲート回
路５からクロツク信号Ｃが送られてくると、以降
に述べる各部の動作のタイミングを制御するとと
もに、終点Ｘレジスタ１と終点Ｙレジスタ２との
内容から終点の存在する象限またはオクタントを
決定し、候補ドツトの方向を増分発生部１４へ与
える。さらに制御部６は増分パルスが増分発生部
１４から発せられるごとに中間点Ｘカウンタ３と
中間点Ｙカウンタ４の少なくとも一方を更新す
る。最終中間点Ｘレジスタ７は初期設定された終
点の次の即ち向う側の候補ドツトの中間点のＸア
ドレスを保持し、比較器８は最終中間点Ｘレジス
タ７の内容と中間点Ｘカウンタ３の内容とを比較
し、一致を検出したらゲート回路５にゲートを閉
じるよう指示する。最終中間点Ｙレジスタ９は初
期設定された終点の次の即ち向う側の候補ドツト
の中間点のＹアドレスを保持し、比較器１０は最
終中間点Ｙレジスタ９の内容と、中間点Ｙカウン
タ４の内容とを比較し、一致を検出したらゲート
回路５を閉じるようにする。すなわち、中間点Ｘ
カウンタ３、中間点Ｙカウンタ４、最終中間点Ｘ
レジスタ７、比較器８、最終中間点Ｙレジスタ
９、比較器１０は、最適ドツトが順次発生される
に伴い、候補ドツトの中間点もしだいに終点のつ
ぎの候補ドツトの中間点に近づき、ついに一致し
たとき、発生した最適ドツトが終点に一致するの
で、そのタイミングを検出するためのものであ
る。変位レジスタ１１は候補ドツトの中間点の変
位を一時的に保持するもので、始点の次の候補ド
ツトの中間点の変位については初期設定段階で、
前述のとおりセツトされる。加算器１２は式(5)な
いし(6)を実行するもので、式(5)ないし(6)の選択お
よび加減算の切換については切換部１３で行な
う。増分発生部１４は変位レジスタ１１の内容
と、制御部６からの候補ドツトの方向とから、第
１表または第２表の論理により最適ドツトの方向
を決定し、増分パルスを発生する。出力制御部１
５は前述のとおり、始点を図示していない画面編
集用メモリ等に初期段階で書き込むとともに、増
分発生部１４からの増分パルスを始点アドレスに
累加算して最適ドツトの絶対アドレスを求め、図
示していない画面編集用メモリ等に書込みを行な
うとともに、比較器８と比較器１０とにおいてと
もに一致が検出されたとき、その時以後の増分パ
ルスを無視するものである。 以上、直線発生の一例について述べたが、中間
点Ｘカウンタ３と中間点Ｙカウンタ４に始点ない
し選択された最適ドツトのＸアドレスとＹアドレ
スとをそれぞれセツトし、比較器８で終点Ｘレジ
スタ１と中間点Ｘカウンタ３の内容を比較させ、
比較器１０で終点Ｙレジスタ２と中間点Ｙカウン
タ４の内容とを比較させるようにしてもよい。そ
の場合は最終中間点Ｘレジスタ７と最終中間点Ｙ
レジスタ９を削除することができる。しかし、後
述する円弧発生もあわせてできるようにするため
には、第５図の構成の方が共用化が図りやすい。 つぎに本発明である円弧発生の場合について説
明する。 第６図は円弧（以下、特にことわらぬ限り円を
含むものとする）を反時計方向に発生する場合の
候補ドツトの方向を説明する説明図を示す。第６
図ａが４連結発生の場合を、第６図ｂが８連結発
生の場合を示している。発生方向を時計方向にし
た場合の候補ドツトの方向は反時計方向と逆にな
るだけであるので説明は省略する。 第７は円弧発生のアルゴリズムを説明する図
で、考え方は第２図で説明した線分発生のアルゴ
リズムと同様であるが、第６図から理解できるよ
うに、最適ドツトを順次選択していくうちに候補
ドツトの方向が変化することに注意が必要であ
る。第７図ａは４連結で反時計方向に円弧を発生
する場合を示し、始点PSが第１象限に存在し、そ
の次の候補ドツトとして、ドツトQ1とQ2があり、
いずれを最適ドツトとして選択するかは、各ドツ
トから円弧に至る距離d1，d2によつて決定される
べきことも示している。そして、距離d1，d2を求
めることが雑であるので、円弧は回転放物面ｇ
（ｘ，ｙ）＝x2＋y2−r2とxy平面ｇ（ｘ，ｙ）＝０と
の交線であると考え、距離d1，d2を演算する代り
に、候補ドツトの中間点Q3における回転放物面
の変位Z3を求め、変位Z3の符号と逆の方向になら
うとする候補ドツトを最適ドツト（第７図ｂでは
Q1）として発生すればよいことを示している。
しかし、最適ドツトが次から次へと選択されてい
くうちに、４連結発生の場合では、選択された最
適ドツトが第２象限に入ると、次の候補ドツトは
第６図ａのように変えなければならず、したがつ
て、候補ドツトの中間点のとり方も変化すること
に注意が必要となる。第８図は８連結発生の場合
を示しており、候補ドツトはオクタントが変わる
と変化することに注意が必要である。円弧発生の
場合には、円弧の方程式がｇ（ｘ，ｙ）＝x2＋y2−
r2（ｒは半径を示す）と表わせるので、円の内側
の点の変位は当然負となり、外側の点の変位は正
となる。したがつて、４連結で第１象限におい
て、反時計方向に円発生を行なわせるとき、候補
ドツトの中間点の変位が負ならば変位を正の方向
に持つて行こうとする。すなわちｙ座標が増加す
るY+方向の候補ドツトが最適ドツトとなり、変
位が正ならば変位を負に持つて行こうとする。す
なわちＸ座標が減少するX-の方向の候補ドツト
が最適ドツトとなることを示している。これらを
まとめると第３表、第４表で表わすことができ、
第３表は４連結発生を、第４表(A)(B)は８連結発生
を示している。
体的線分発生を行行つて説明する。たとえば始点
PS（０，０）、終点PE（５，２）の線分を発生した
例を第４図に示す。第４図ａは４連結で発生させ
たときのドツト変位、最適ドツトの選択方向（増
分の方向）の各関係を示し、第４図ｂは始点、終
点、選択された最適ドツトを実際にプロツトした
状態を示している。また、第４図ｃ，ｄは８連結
で発生させた場合を示している。なお第４図ａ，
ｃにおいて、Ａは始点、Ｂは選択された最適ドツ
ト、Ｃは終点を表わしている。 第５図は線分を発生する一例を示す。図中１は
終点Ｘレジスタ、２は終点Ｙレジスタ、３は中間
点Ｘカウンタ、４は中間点Ｙカウンタ、５はゲー
ト回路、６は制御部、７は最終中間点Ｘレジス
タ、８は比較器、９は最終中間点Ｙレジスタ、１
０は比較器、１１は変位レジスタ、１２は加算
器、１３は切換部、１４は増分発生部、１５は出
力制御部を表わしており、動作は以下のとおりで
ある。 本例では、始点から終点に至るまでの最適ドツ
トを、始点ないしはすでに発生された最適ドツト
の次に選択すべき最適ドツトを見たとき、その方
向が右方向（Ｘ＋）、左方向（Ｘ−）、上方向（Ｙ
＋）、下方向（Ｙ−）のうちいずれの方向にある
かを増分パルスで示す構成としている。もし、そ
の方向が斜め方向のときは上記４方向を組合せ
（たとえば右斜め上方向のときは、Ｘ＋，Ｙ＋）
で示すようにしている。 まず、始点の絶対アドレスを出力制御部１５に
セツトし、図示していない画面編集用メモリ等に
始点を書込む。そして始点を相対原点としたとき
の終点の相対Ｘアドレスを終点点Ｘレジスタ１
に、相対Ｙアドレスを終点Ｙレジスタ２にセツト
する。すると、制御部６は始点の次の最適ドツト
の中間点を求め、該中間点のＸアドレスを中間点
Ｘカウンタ３に、Ｙアドレスを中間点Ｙカウンタ
４に各々セツトする。また、制御装部６は終点の
次の候補ドツトの中間点のＸアドレスを最終中間
点Ｘレジスタ７に、Ｙアドレスを最終中間点Ｙレ
ジスタ９に各々セツトする。さらに、制御部６は
変位レジスタ１１をクリアする（上記制御部６の
動作を制御部６で行なわずに、あらかじめ外部で
演算し、初期設定するようにしてもよい）。終点
Ｘレジスタ１は初期設定された終点Ｘアドレスを
保持し、終点Ｙレジスタ２は初期設定された終点
Ｙアドレスを保持する。中間点Ｘカウンタ３は候
補ドツトの中間点のＸアドレスを、中間点Ｙカウ
ンタ４は候補ドツトの中間点のＹアドレスをそれ
ぞれ一時的に保持するもので、制御部６からのカ
ウントアツプないしはカウントダウンの信号によ
り増減し、最終中間点Ｘレジスタ７と最終中間点
Ｙレジスタ９との値に近づいていく。ゲート回路
５は外部からのクロツク入力制御を行なうもの
で、線分発生の開始を指示する信号Ａを得てから
比較器８と比較器１０とがともに一致検出するま
でクロツク信号Ｃを制御部６に供給する。制御部
６は前記初期設定のための動作の外に、ゲート回
路５からクロツク信号Ｃが送られてくると、以降
に述べる各部の動作のタイミングを制御するとと
もに、終点Ｘレジスタ１と終点Ｙレジスタ２との
内容から終点の存在する象限またはオクタントを
決定し、候補ドツトの方向を増分発生部１４へ与
える。さらに制御部６は増分パルスが増分発生部
１４から発せられるごとに中間点Ｘカウンタ３と
中間点Ｙカウンタ４の少なくとも一方を更新す
る。最終中間点Ｘレジスタ７は初期設定された終
点の次の即ち向う側の候補ドツトの中間点のＸア
ドレスを保持し、比較器８は最終中間点Ｘレジス
タ７の内容と中間点Ｘカウンタ３の内容とを比較
し、一致を検出したらゲート回路５にゲートを閉
じるよう指示する。最終中間点Ｙレジスタ９は初
期設定された終点の次の即ち向う側の候補ドツト
の中間点のＹアドレスを保持し、比較器１０は最
終中間点Ｙレジスタ９の内容と、中間点Ｙカウン
タ４の内容とを比較し、一致を検出したらゲート
回路５を閉じるようにする。すなわち、中間点Ｘ
カウンタ３、中間点Ｙカウンタ４、最終中間点Ｘ
レジスタ７、比較器８、最終中間点Ｙレジスタ
９、比較器１０は、最適ドツトが順次発生される
に伴い、候補ドツトの中間点もしだいに終点のつ
ぎの候補ドツトの中間点に近づき、ついに一致し
たとき、発生した最適ドツトが終点に一致するの
で、そのタイミングを検出するためのものであ
る。変位レジスタ１１は候補ドツトの中間点の変
位を一時的に保持するもので、始点の次の候補ド
ツトの中間点の変位については初期設定段階で、
前述のとおりセツトされる。加算器１２は式(5)な
いし(6)を実行するもので、式(5)ないし(6)の選択お
よび加減算の切換については切換部１３で行な
う。増分発生部１４は変位レジスタ１１の内容
と、制御部６からの候補ドツトの方向とから、第
１表または第２表の論理により最適ドツトの方向
を決定し、増分パルスを発生する。出力制御部１
５は前述のとおり、始点を図示していない画面編
集用メモリ等に初期段階で書き込むとともに、増
分発生部１４からの増分パルスを始点アドレスに
累加算して最適ドツトの絶対アドレスを求め、図
示していない画面編集用メモリ等に書込みを行な
うとともに、比較器８と比較器１０とにおいてと
もに一致が検出されたとき、その時以後の増分パ
ルスを無視するものである。 以上、直線発生の一例について述べたが、中間
点Ｘカウンタ３と中間点Ｙカウンタ４に始点ない
し選択された最適ドツトのＸアドレスとＹアドレ
スとをそれぞれセツトし、比較器８で終点Ｘレジ
スタ１と中間点Ｘカウンタ３の内容を比較させ、
比較器１０で終点Ｙレジスタ２と中間点Ｙカウン
タ４の内容とを比較させるようにしてもよい。そ
の場合は最終中間点Ｘレジスタ７と最終中間点Ｙ
レジスタ９を削除することができる。しかし、後
述する円弧発生もあわせてできるようにするため
には、第５図の構成の方が共用化が図りやすい。 つぎに本発明である円弧発生の場合について説
明する。 第６図は円弧（以下、特にことわらぬ限り円を
含むものとする）を反時計方向に発生する場合の
候補ドツトの方向を説明する説明図を示す。第６
図ａが４連結発生の場合を、第６図ｂが８連結発
生の場合を示している。発生方向を時計方向にし
た場合の候補ドツトの方向は反時計方向と逆にな
るだけであるので説明は省略する。 第７は円弧発生のアルゴリズムを説明する図
で、考え方は第２図で説明した線分発生のアルゴ
リズムと同様であるが、第６図から理解できるよ
うに、最適ドツトを順次選択していくうちに候補
ドツトの方向が変化することに注意が必要であ
る。第７図ａは４連結で反時計方向に円弧を発生
する場合を示し、始点PSが第１象限に存在し、そ
の次の候補ドツトとして、ドツトQ1とQ2があり、
いずれを最適ドツトとして選択するかは、各ドツ
トから円弧に至る距離d1，d2によつて決定される
べきことも示している。そして、距離d1，d2を求
めることが雑であるので、円弧は回転放物面ｇ
（ｘ，ｙ）＝x2＋y2−r2とxy平面ｇ（ｘ，ｙ）＝０と
の交線であると考え、距離d1，d2を演算する代り
に、候補ドツトの中間点Q3における回転放物面
の変位Z3を求め、変位Z3の符号と逆の方向になら
うとする候補ドツトを最適ドツト（第７図ｂでは
Q1）として発生すればよいことを示している。
しかし、最適ドツトが次から次へと選択されてい
くうちに、４連結発生の場合では、選択された最
適ドツトが第２象限に入ると、次の候補ドツトは
第６図ａのように変えなければならず、したがつ
て、候補ドツトの中間点のとり方も変化すること
に注意が必要となる。第８図は８連結発生の場合
を示しており、候補ドツトはオクタントが変わる
と変化することに注意が必要である。円弧発生の
場合には、円弧の方程式がｇ（ｘ，ｙ）＝x2＋y2−
r2（ｒは半径を示す）と表わせるので、円の内側
の点の変位は当然負となり、外側の点の変位は正
となる。したがつて、４連結で第１象限におい
て、反時計方向に円発生を行なわせるとき、候補
ドツトの中間点の変位が負ならば変位を正の方向
に持つて行こうとする。すなわちｙ座標が増加す
るY+方向の候補ドツトが最適ドツトとなり、変
位が正ならば変位を負に持つて行こうとする。す
なわちＸ座標が減少するX-の方向の候補ドツト
が最適ドツトとなることを示している。これらを
まとめると第３表、第４表で表わすことができ、
第３表は４連結発生を、第４表(A)(B)は８連結発生
を示している。
【表】
【表】
＊：開始時は始点がなる。
【表】
【表】
次に、具体的変位の求め方について以下に述べ
る。まず、４連結で円弧を発生する場合を述べ
る。始点PSの変位ZPSは、始点PSが発生すべき円
弧上にあるので当然“０”となるが、最初の２つ
の候補ドツトの中間点Q3の変位ZQ3は ZQ3＝ｇ（xS±１／２，yS±１／２） ＝ｇ（xS，yS）±xS±yS＋１／２ ＝ｇ（pS）±xS±yS＋１／２＝±xS±yS＋１／２ ……(13) となる。そして、候補ドツトのいずれか一方が最
適ドツトとして選択されると、次の候補ドツトの
中間点の変位は次のいずれかで表わすことができ
る。 (1) 上下方向の候補ドツトを最適ドツトとして選
択したとき ZQ31＝ｇ（xQ3，yQ3±１）＝ｇ（Q3）±2yQ3＋１
……(14) (2) 左右方向の候補ドツトを最適ドツトとして選
択したとき ZQ32＝ｇ（xQ3±１，yQ3）＝ｇ（Q3）±2xQ3＋１
……(15) 従来の円弧発生方法では２つの候補Q1，Q2の
変位の和を計算するため、 ZQ3′＝ｇ（Q1）＋ｇ（Q2） ＝ｇ（Ｓ）±2yS＋１＋ｇ（Ｓ）±2xS＋１ ＝2g（Ｓ）±2yS±2xS＋２ ＝±2yS±2xS＋２ ……（13′） となる。式（13）は式（13′）に比べ２を掛ける
演算が不要であり、演算量が少ない。 次のドツト選択についても本発明では第14式お
よび第15式から候補ドツトの中間点の変位とし
て、ZQ31かZQ32のいずれかを求めればよい。とこ
ろが従来の方法では２つの候補ドツトの変位の和
として ZQ31′＝2g（Q1）±2yQ1±2xQ1＋２……（14′） ZQ32′＝2g（Q2）±2yQ2±2xQ2＋２……（15′） のいずれかを求めることになる。やはり、式
（14）、（15）は式（14′）、（15′）に比べ２を掛け
る演算が一部の項で不要であり、また、演算する
項が少ないため演算量が少ない。 演算において座標を２倍にする必要がないこ
と、あるいは加減算する項が１つ減るということ
は、計算を１回だけ実行する場合は一回の演算時
間が短いためほとんど影響がないが、図形を生成
し表示するような場合、上記ドツト選択を数百か
ら数千回、場合によつては数万回行うことにな
り、演算量の減少効果は著しいのである。 以上述べたように、本発明と従来方法とは結果
として同じドツト選択を与えはするが、計算の手
法は全く異なるものであり、その効果としての演
算量の減少は従来の技術にくらべて著しいのであ
る。 つぎに、８連結で円弧を発生する場合を述べ
る。８連結の場合でも、始点pSの変位ZPSは、や
はり発生すべき円弧上にあるので当然“０”であ
るが、最初の２つの候補ドツトの中間点Q3の変
位ZQ3は、つぎのように表わせる。 (1) 始点PSが第１，４，５，８オクタントにある
とき ZQ3＝ｇ（xS±１／２，yS±１） ＝ｇ（xS，yS）±xS±2yS＋５／４ ＝ZPS±xS±2yS＋５／４＝＋xS±2yS＋５／４……(16
) (2) 始点PSが第２，３，６，７オクタントにある
とき ZQ3＝ｇ（xS±１，yS±１／２ ＝ｇ（xS，yS）±2xS±yS＋５／４ ＝ZPS±2xS±yS＋５／４＝±2xS±yS＋５／４……(17
) そして、候補ドツトのいずれか一方が最適ドツ
トとして発生されると、次の候補ドツトの中間点
の変位は次のいずれかで表わすことができる。 (1) 上下方向の候補ドツトを最適ドツトとして発
生したとき 式（14）に同じ ……(18) (2) 左右方向の候補ドツトを最適ドツトとして発
生したとき 式（15）に同じ ……(19) (3) 斜め方向の候補ドツトを最適ドツトとして発
生したとき ZQ33＝ｇ（xQ3±１，yQ3±１） ＝ｇ（Q3）±2xQ3±2yQ3＋２ ……(20) このようにして得た候補ドツトの中間点の変位
を、４連結発生のときは第３表を、８連結発生の
ときは第４表を適用し、最適ドツトを発生する。
ところで、８連結発生の場合にはオクタントの境
界において、候補ドツトの中間点の移動が、オク
タント内とは少し違うので説明を加える。たとえ
ば、第８オクタントから第１オクタントに移る場
合、第９図に示すように、最適ドツトとして、
Q0，Q2を選択したとき、候補ドツトの中間点は
M1，M2となることは、いままでの説明で明らか
であるが、次の候補ドツトの中間点が第１オクタ
ントに入るので、次の候補ドツトは中間点M21で
なく中間点M22にしなければならない。すなわ
ち、前回の最適ドツトとして、候補ドツトの上下
方向を選択したというだけで式（18）を適用した
のでは、候補ドツトの中間点と、その変位を正し
く得ることはできないが、式（20）を適用すれば
正しい候補ドツトの中間点とその変位を得ること
ができる。他のＸ軸ないしはＹ軸においてオクタ
ントが変るときも同様で、式（20）を適用する必
要がある。また、Ｘ軸ないしＹ軸以外でオクタン
トが変る場合（90゜×ｎ＋45゜，ｎ＝０，１，２，
３の方向の場合）には、たとえば、第１０図の如
く斜め方向の候補ドツトを最適ドツトとして選択
するが、その場合の候補ドツトの中間点の変位
M22は ZM22＝ｆ（XM2±３／２，YM2±１／２） ＝ZM2±3XM2±YM2＋10／４ ……(21) または ZM22＝ｆ（XM2±１／２，YM2±３／２） ＝ZM2±XM2±3YM2±10／４ ……(22) で表わせる。 もし、上下方向ないしは左右方向の候補ドツト
を最適ドツトとして選択した場合は第１１図の如
くなりその場合の候補ドツトの中間点の変位ZM22
は ZM22＝ｆ（XM2±１／２，YM2±１／２） ＝ZM2±XM2±YM2＋１／２ ……(23) となる。 なお、Ｘ軸ないしＹ軸においてオクタントが変
る場合で、しかも斜め方向の候補ドツトを最適ド
ツトとして選択したときは、90゜×ｎ＋45゜（ｎ＝
０，１，２，３）の方向と同じように式（21），
（22）を適用すればよい。 以上で、円弧発生のアルゴリズムについての説
明を終了するが、一般式でまとめて示すとつぎの
ようになる。始点pS（XS，XS）の次の候補ドツト
の中間点M1の変位ZM1は、始点pSの変位は“０”
であるから ZM1＝±2aXS±2βYS＋α2＋β2 ………(24) （ただし、α，βは１／２または１） となり、変位ZM1の値の符号を逆転させようとす
る候補ドツトが最適ドツトになりうる。また、一
般式として次の候補ドツトの中間点M(o+1)と、前
回の中間点Moとの差分を（ｓ，ｔ）としたとき、
中間点M(o+1)の変位ZM(o+1)と中間点ZMoとの関係
は ZM(o+1)＝ZMo±2SXMo±2tYMo＋s2＋t2 ………(25) となる。そして、変位ZM(o+1)の符号を逆転させよ
うとする候補ドツトが最適ドツトとなる。 具体的円弧発生例として、始点（０，６）、終
点（６，０）を時計方向に発生させた図を第１２
図第１３図に示す。第１２図は４連結発生の場合
を示し、第１３図は８連結発生の場合を示してい
る。なお、図中Ａは始点、Ｂは選択された最適ド
ツト、Ｃは終点を示す。 第１４図は円弧を発生する本発明の一実施例を
示す。図中１０３は中間点Ｘカウンタ、１０４は
中間点Ｙカウンタ、１０５はゲート回路、１０６
は制御部、１０７は最終中間点Ｘレジスタ、１０
８は比較器、１０９は最終中間点Ｙレジスタ、１
１０は比較器、１１１は変位レジスタ、１１２は
加算器、１１３は切換部、１１４は増分発生部、
１１５は出力制御部を表わしている。 これらの動作を第５図の線分発生の場合と比較
して相違点を中心に以下に説明する。なお、第１
４図図示の構成における各構成部の機能は、各構
成部の番号から100減じた番号を有す第５図の構
成部の機能と対応している。第１４図においては
第５図の終点Ｘレジスタ１と終点Ｙレジスタ２に
対応する構成部が存在しないが、これは候補ドツ
トの変位を求める演算式（24）（25）が線分の場
合の演算式(5)(6)，(8)(9)(11)(12)と異なることによる
も
のである。すなわち、中間点Ｘカウンタ１０３、
中間点Ｙカウンタ１０４、変位レジスタ１１１、
加算器１１２、切換部１１３は式（24）（25）を
演算する部分で、切換部において中間点Ｘカウン
タ１０３と中間点Ｙカウンタ１０４との切換、２
倍（左側への１ビツトシフト）、および定数加算
を行なうようになされている。制御部１０６は候
補ドツトの方向が最適ドツトを順次選択するにし
たがい第６図のように変化することから、毎回候
補ドツトの方向を始点または前回発生した最適ド
ツトのＸアドレスとＹアドレスの大小関係と符号
および円弧発生の方向とから第３表、第４表の論
理から求める必要があり、このことが線分発生の
場合と異なる。他の構成部の動作は第５図の線分
の場合と同様である。 以上、円弧発生とそのための一実施例を示した
が、円発生の場合は、円発生開始時に比較器１０
８と比較器１１０とにおいて、ともに一致検出信
号を発生するので、円発生開始時にはそれを無視
し、再び一致検出信号を発生した時点で円発生を
終了させる機能を制御部１０６に付与し、その信
号をゲート回路１０５と出力制御部１１５とに付
与するようにすればよい。 以上説明したように、本発明によれば、候補ド
ツトの中間点の変位を求め、該変位の符号を逆転
しようとする候補ドツトを最適ドツトとして発生
するだけで、円弧、円の線図形をよく近似するこ
とができるので、演算が容易となり、線図形発生
の高速化と装置構成の簡易化とを図ることができ
る。
る。まず、４連結で円弧を発生する場合を述べ
る。始点PSの変位ZPSは、始点PSが発生すべき円
弧上にあるので当然“０”となるが、最初の２つ
の候補ドツトの中間点Q3の変位ZQ3は ZQ3＝ｇ（xS±１／２，yS±１／２） ＝ｇ（xS，yS）±xS±yS＋１／２ ＝ｇ（pS）±xS±yS＋１／２＝±xS±yS＋１／２ ……(13) となる。そして、候補ドツトのいずれか一方が最
適ドツトとして選択されると、次の候補ドツトの
中間点の変位は次のいずれかで表わすことができ
る。 (1) 上下方向の候補ドツトを最適ドツトとして選
択したとき ZQ31＝ｇ（xQ3，yQ3±１）＝ｇ（Q3）±2yQ3＋１
……(14) (2) 左右方向の候補ドツトを最適ドツトとして選
択したとき ZQ32＝ｇ（xQ3±１，yQ3）＝ｇ（Q3）±2xQ3＋１
……(15) 従来の円弧発生方法では２つの候補Q1，Q2の
変位の和を計算するため、 ZQ3′＝ｇ（Q1）＋ｇ（Q2） ＝ｇ（Ｓ）±2yS＋１＋ｇ（Ｓ）±2xS＋１ ＝2g（Ｓ）±2yS±2xS＋２ ＝±2yS±2xS＋２ ……（13′） となる。式（13）は式（13′）に比べ２を掛ける
演算が不要であり、演算量が少ない。 次のドツト選択についても本発明では第14式お
よび第15式から候補ドツトの中間点の変位とし
て、ZQ31かZQ32のいずれかを求めればよい。とこ
ろが従来の方法では２つの候補ドツトの変位の和
として ZQ31′＝2g（Q1）±2yQ1±2xQ1＋２……（14′） ZQ32′＝2g（Q2）±2yQ2±2xQ2＋２……（15′） のいずれかを求めることになる。やはり、式
（14）、（15）は式（14′）、（15′）に比べ２を掛け
る演算が一部の項で不要であり、また、演算する
項が少ないため演算量が少ない。 演算において座標を２倍にする必要がないこ
と、あるいは加減算する項が１つ減るということ
は、計算を１回だけ実行する場合は一回の演算時
間が短いためほとんど影響がないが、図形を生成
し表示するような場合、上記ドツト選択を数百か
ら数千回、場合によつては数万回行うことにな
り、演算量の減少効果は著しいのである。 以上述べたように、本発明と従来方法とは結果
として同じドツト選択を与えはするが、計算の手
法は全く異なるものであり、その効果としての演
算量の減少は従来の技術にくらべて著しいのであ
る。 つぎに、８連結で円弧を発生する場合を述べ
る。８連結の場合でも、始点pSの変位ZPSは、や
はり発生すべき円弧上にあるので当然“０”であ
るが、最初の２つの候補ドツトの中間点Q3の変
位ZQ3は、つぎのように表わせる。 (1) 始点PSが第１，４，５，８オクタントにある
とき ZQ3＝ｇ（xS±１／２，yS±１） ＝ｇ（xS，yS）±xS±2yS＋５／４ ＝ZPS±xS±2yS＋５／４＝＋xS±2yS＋５／４……(16
) (2) 始点PSが第２，３，６，７オクタントにある
とき ZQ3＝ｇ（xS±１，yS±１／２ ＝ｇ（xS，yS）±2xS±yS＋５／４ ＝ZPS±2xS±yS＋５／４＝±2xS±yS＋５／４……(17
) そして、候補ドツトのいずれか一方が最適ドツ
トとして発生されると、次の候補ドツトの中間点
の変位は次のいずれかで表わすことができる。 (1) 上下方向の候補ドツトを最適ドツトとして発
生したとき 式（14）に同じ ……(18) (2) 左右方向の候補ドツトを最適ドツトとして発
生したとき 式（15）に同じ ……(19) (3) 斜め方向の候補ドツトを最適ドツトとして発
生したとき ZQ33＝ｇ（xQ3±１，yQ3±１） ＝ｇ（Q3）±2xQ3±2yQ3＋２ ……(20) このようにして得た候補ドツトの中間点の変位
を、４連結発生のときは第３表を、８連結発生の
ときは第４表を適用し、最適ドツトを発生する。
ところで、８連結発生の場合にはオクタントの境
界において、候補ドツトの中間点の移動が、オク
タント内とは少し違うので説明を加える。たとえ
ば、第８オクタントから第１オクタントに移る場
合、第９図に示すように、最適ドツトとして、
Q0，Q2を選択したとき、候補ドツトの中間点は
M1，M2となることは、いままでの説明で明らか
であるが、次の候補ドツトの中間点が第１オクタ
ントに入るので、次の候補ドツトは中間点M21で
なく中間点M22にしなければならない。すなわ
ち、前回の最適ドツトとして、候補ドツトの上下
方向を選択したというだけで式（18）を適用した
のでは、候補ドツトの中間点と、その変位を正し
く得ることはできないが、式（20）を適用すれば
正しい候補ドツトの中間点とその変位を得ること
ができる。他のＸ軸ないしはＹ軸においてオクタ
ントが変るときも同様で、式（20）を適用する必
要がある。また、Ｘ軸ないしＹ軸以外でオクタン
トが変る場合（90゜×ｎ＋45゜，ｎ＝０，１，２，
３の方向の場合）には、たとえば、第１０図の如
く斜め方向の候補ドツトを最適ドツトとして選択
するが、その場合の候補ドツトの中間点の変位
M22は ZM22＝ｆ（XM2±３／２，YM2±１／２） ＝ZM2±3XM2±YM2＋10／４ ……(21) または ZM22＝ｆ（XM2±１／２，YM2±３／２） ＝ZM2±XM2±3YM2±10／４ ……(22) で表わせる。 もし、上下方向ないしは左右方向の候補ドツト
を最適ドツトとして選択した場合は第１１図の如
くなりその場合の候補ドツトの中間点の変位ZM22
は ZM22＝ｆ（XM2±１／２，YM2±１／２） ＝ZM2±XM2±YM2＋１／２ ……(23) となる。 なお、Ｘ軸ないしＹ軸においてオクタントが変
る場合で、しかも斜め方向の候補ドツトを最適ド
ツトとして選択したときは、90゜×ｎ＋45゜（ｎ＝
０，１，２，３）の方向と同じように式（21），
（22）を適用すればよい。 以上で、円弧発生のアルゴリズムについての説
明を終了するが、一般式でまとめて示すとつぎの
ようになる。始点pS（XS，XS）の次の候補ドツト
の中間点M1の変位ZM1は、始点pSの変位は“０”
であるから ZM1＝±2aXS±2βYS＋α2＋β2 ………(24) （ただし、α，βは１／２または１） となり、変位ZM1の値の符号を逆転させようとす
る候補ドツトが最適ドツトになりうる。また、一
般式として次の候補ドツトの中間点M(o+1)と、前
回の中間点Moとの差分を（ｓ，ｔ）としたとき、
中間点M(o+1)の変位ZM(o+1)と中間点ZMoとの関係
は ZM(o+1)＝ZMo±2SXMo±2tYMo＋s2＋t2 ………(25) となる。そして、変位ZM(o+1)の符号を逆転させよ
うとする候補ドツトが最適ドツトとなる。 具体的円弧発生例として、始点（０，６）、終
点（６，０）を時計方向に発生させた図を第１２
図第１３図に示す。第１２図は４連結発生の場合
を示し、第１３図は８連結発生の場合を示してい
る。なお、図中Ａは始点、Ｂは選択された最適ド
ツト、Ｃは終点を示す。 第１４図は円弧を発生する本発明の一実施例を
示す。図中１０３は中間点Ｘカウンタ、１０４は
中間点Ｙカウンタ、１０５はゲート回路、１０６
は制御部、１０７は最終中間点Ｘレジスタ、１０
８は比較器、１０９は最終中間点Ｙレジスタ、１
１０は比較器、１１１は変位レジスタ、１１２は
加算器、１１３は切換部、１１４は増分発生部、
１１５は出力制御部を表わしている。 これらの動作を第５図の線分発生の場合と比較
して相違点を中心に以下に説明する。なお、第１
４図図示の構成における各構成部の機能は、各構
成部の番号から100減じた番号を有す第５図の構
成部の機能と対応している。第１４図においては
第５図の終点Ｘレジスタ１と終点Ｙレジスタ２に
対応する構成部が存在しないが、これは候補ドツ
トの変位を求める演算式（24）（25）が線分の場
合の演算式(5)(6)，(8)(9)(11)(12)と異なることによる
も
のである。すなわち、中間点Ｘカウンタ１０３、
中間点Ｙカウンタ１０４、変位レジスタ１１１、
加算器１１２、切換部１１３は式（24）（25）を
演算する部分で、切換部において中間点Ｘカウン
タ１０３と中間点Ｙカウンタ１０４との切換、２
倍（左側への１ビツトシフト）、および定数加算
を行なうようになされている。制御部１０６は候
補ドツトの方向が最適ドツトを順次選択するにし
たがい第６図のように変化することから、毎回候
補ドツトの方向を始点または前回発生した最適ド
ツトのＸアドレスとＹアドレスの大小関係と符号
および円弧発生の方向とから第３表、第４表の論
理から求める必要があり、このことが線分発生の
場合と異なる。他の構成部の動作は第５図の線分
の場合と同様である。 以上、円弧発生とそのための一実施例を示した
が、円発生の場合は、円発生開始時に比較器１０
８と比較器１１０とにおいて、ともに一致検出信
号を発生するので、円発生開始時にはそれを無視
し、再び一致検出信号を発生した時点で円発生を
終了させる機能を制御部１０６に付与し、その信
号をゲート回路１０５と出力制御部１１５とに付
与するようにすればよい。 以上説明したように、本発明によれば、候補ド
ツトの中間点の変位を求め、該変位の符号を逆転
しようとする候補ドツトを最適ドツトとして発生
するだけで、円弧、円の線図形をよく近似するこ
とができるので、演算が容易となり、線図形発生
の高速化と装置構成の簡易化とを図ることができ
る。
第１図ａ，ｂは夫々線分発生のための候補ドツ
トの方向を説明する説明図、第２図は４連結で線
分発生する原理を説明する説明図、第３図は８連
結で線分発生する原理を説明する説明図、第４図
は具体例によつて線分の発生を説明する説明図、
第５図は線分発生装置の一例、第６図ａ，ｂは
夫々反時計方向に円弧を発生するための候補ドツ
トの方向を説明する説明図、第７図は４連結で円
弧発生する原理を説明する説明図、第８図は８連
結で円弧発生する原理を説明する説明図、第９図
は８連結円弧発生するときのＸ軸における候補ド
ツトの中間点の移動を説明する説明図、第１０図
は８連結円弧発生するときの45゜における候補ド
ツトの中間点の斜め方向からの移動を説明する説
明図、第１１図は８連結円弧発生するときの45゜
における候補ドツトの中間点の下方からの移動を
説明する説明図、第１２図は具体例によつて４連
結でで円弧の発生を説明する説明図、第１３図は
具体例によつて８連結で円弧の発生を説明する説
明図、第１４図は本発明における円弧発生装置の
一実施例を示す。 図中、１は終点Ｘレジスタ、２は終点Ｙレジス
タ、３は中間点Ｘカウンタ、４は中間点Ｙカウン
タ、５はゲート回路、６は制御部、７は最終中間
点Ｘレジスタ、８は比較器、９は最終中間点Ｙレ
ジスタ、１０は比較器、１１は変位レジスタ、１
２は加算器、１３は切換部、１４は増分発生部、
１５は出力制御部、１０３は中間点Ｘカウンタ、
１０４は中間点Ｙカウンタ、１０５はゲート回
路、１０６は制御部、１０７は最終中間点Ｘレジ
スタ、１０８は比較器、１０９は最終中間点Ｙレ
ジスタ、１１０は比較器、１１１は変位レジス
タ、１１２は加算器、１１３は切換部、１１４は
増分発生部、１１５は出力制御部を表わす。
トの方向を説明する説明図、第２図は４連結で線
分発生する原理を説明する説明図、第３図は８連
結で線分発生する原理を説明する説明図、第４図
は具体例によつて線分の発生を説明する説明図、
第５図は線分発生装置の一例、第６図ａ，ｂは
夫々反時計方向に円弧を発生するための候補ドツ
トの方向を説明する説明図、第７図は４連結で円
弧発生する原理を説明する説明図、第８図は８連
結で円弧発生する原理を説明する説明図、第９図
は８連結円弧発生するときのＸ軸における候補ド
ツトの中間点の移動を説明する説明図、第１０図
は８連結円弧発生するときの45゜における候補ド
ツトの中間点の斜め方向からの移動を説明する説
明図、第１１図は８連結円弧発生するときの45゜
における候補ドツトの中間点の下方からの移動を
説明する説明図、第１２図は具体例によつて４連
結でで円弧の発生を説明する説明図、第１３図は
具体例によつて８連結で円弧の発生を説明する説
明図、第１４図は本発明における円弧発生装置の
一実施例を示す。 図中、１は終点Ｘレジスタ、２は終点Ｙレジス
タ、３は中間点Ｘカウンタ、４は中間点Ｙカウン
タ、５はゲート回路、６は制御部、７は最終中間
点Ｘレジスタ、８は比較器、９は最終中間点Ｙレ
ジスタ、１０は比較器、１１は変位レジスタ、１
２は加算器、１３は切換部、１４は増分発生部、
１５は出力制御部、１０３は中間点Ｘカウンタ、
１０４は中間点Ｙカウンタ、１０５はゲート回
路、１０６は制御部、１０７は最終中間点Ｘレジ
スタ、１０８は比較器、１０９は最終中間点Ｙレ
ジスタ、１１０は比較器、１１１は変位レジス
タ、１１２は加算器、１１３は切換部、１１４は
増分発生部、１１５は出力制御部を表わす。
Claims (1)
- 【特許請求の範囲】 １ ドツトが格子状に配列された表示面またはこ
れと等価な表示面に対して線図形を表示するため
に線図形を近似するドツトを選択する線図形発生
装置において、 線図形の発生開始時における開始ドツトPS
（XS，YS）を含む前回選択したドツトQ0（X0，
Y0）の次に選択する可能性のある隣接ドツトの
うち少なくとも２つの候補ドツトQ1（X1，Y1）
とQ2（X2，Y2）との位置を発生すべき円弧の中
心を相対原点としたときに前回選択した最適ドツ
トQ0の存在する象限またはオクタントと円弧の
発生方向とから求める第１の手段と、 第１の手段により得た２つの候補ドツトの中間
点Ｍ（XM，YM）の変位を発生すべき線図形の方
程式をｆ（Ｘ，Ｙ）＝０としたときにZM＝ｆ（XM，
YMにより求める第２の手段と、 該中間点の変位ZMの符号が正ならば該変位ZM
を減じる方向に作用する１つの候補ドツトを、負
ならば増加する方向に作用する他の１つの候補ド
ツトを最適ドツトとして位置選択する第３の手段
と、 開始ドツトと選択した最適ドツトの位置に対応
する表示面上のドツトを他のドツトと区別できる
よう明るさ・色等を変えて表示する第４の手段
と、選択した最適ドツトが終了ドツトPEに一致
するまで最適ドツトを順次選択・表示するよう第
１の手段から第４の手段を順次制御する第５の手
段とからなり、 円弧ないし円に対応するドツトを順次選択する
ようにしたことを特徴とする線図形発生装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP16712580A JPS5790690A (en) | 1980-11-27 | 1980-11-27 | Diagram generator |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP16712580A JPS5790690A (en) | 1980-11-27 | 1980-11-27 | Diagram generator |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS5790690A JPS5790690A (en) | 1982-06-05 |
| JPH0258634B2 true JPH0258634B2 (ja) | 1990-12-10 |
Family
ID=15843894
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP16712580A Granted JPS5790690A (en) | 1980-11-27 | 1980-11-27 | Diagram generator |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS5790690A (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP6617463B2 (ja) * | 2015-07-31 | 2019-12-11 | 大日本印刷株式会社 | パターン編集プログラム、パターン編集装置、パターン編集方法 |
-
1980
- 1980-11-27 JP JP16712580A patent/JPS5790690A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS5790690A (en) | 1982-06-05 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPS62192878A (ja) | 多角形の塗りつぶし方法 | |
| JPH0214714B2 (ja) | ||
| US4484189A (en) | Memoryless artificial horizon generator | |
| JPH07225849A (ja) | グラフィックスコンピュータと直線描画装置 | |
| JPH03144782A (ja) | 三次元図形処理装置 | |
| JP2674287B2 (ja) | グラフィックマイクロコンピュータ | |
| JPS6232519B2 (ja) | ||
| JPS61249088A (ja) | 図形塗りつぶし方法 | |
| CA2126505A1 (en) | Straight line coordinate generator | |
| JP2751114B2 (ja) | 文字処理方法 | |
| JPS6228829A (ja) | 情報処理方法 | |
| JP2615091B2 (ja) | 回路ブロックパターン入力装置 | |
| JPS61138375A (ja) | 図形情報処理装置 | |
| JP3139805B2 (ja) | 画像処理方法及びその装置 | |
| JPS595905B2 (ja) | ディスプレイ装置における面輝度発生方式 | |
| JPS62189580A (ja) | カ−ソル表示装置 | |
| JP2762768B2 (ja) | アウトラインデータ描画装置 | |
| JPS6117189A (ja) | 図形処理装置 | |
| JPH07282118A (ja) | タイムチャート作成装置 | |
| JPH01137320A (ja) | タッチ形座標入力装置 | |
| JPH0573256A (ja) | クロスヘアカーソル発生装置 | |
| JPS6389926A (ja) | 表示装置 | |
| JPS63184881A (ja) | 平行四辺形の面塗り処理方式 | |
| JPS61256483A (ja) | 扇形図形のぬりつぶし回路 | |
| JPH10188005A (ja) | 破線円の描画方法 |