グラフィックの基本２

　パソコン活用研究5番街（Visual Basic、Excel(VBA)、BASIC　プログラミング研究）

グラフィックの基本２　（点で直線を描く＆ＤＤＡ補間）

グラフィックの基本では、psetによる点描で、円やサインカーブを描いてみました。直線や四角形のように
シンプルな図形はlineなどで簡単に描けますが、複雑な曲線の描画ではpsetで点描することが多くなります。
今回は、psetによる点描の基礎としてまず、直線を描いてみたいと思います。

１　直線を描く

直線を描くなら、BASICではlineという命令がありますので、lineを使うのが一番簡単です。
今回は、そこをあえてpsetの点描で直線を描いてみたいと思います。今後、グラフィックを扱うのに、今回
のようなテクニックも必要になってくると思いますので。

2点、(X1, Y1) (X2, Y2)を結んでできる線分の方程式は以下の通りになります。
どうして、そういう方程式になるかは、中学か高校かな？の数学の参考書みて下さい。

では、さっそく2点が与えられた時に点描で直線を描くプログラムを作ってみましょう。
この時に、線分の傾き　Y2-Y1/X2-X1 によって２パターンに条件分岐させる必要があることに
注意して下さい。
線分の傾きが緩やか（すなわち傾きが１より小さい）な場合は、xを基準に描画。傾きが急な場合は
yを基準に描画します。そうしないと、ある条件では間隔のあいた点線になってしまいます。

　　　　例えば、傾きが急（1以上）の線分を
　　　　xを基準に１づつ増分して描くと、左の図
　　　　のようにy方向はとびとびの点線となって
　　　　しまいます。

直線を描くプログラム１

10 cls
20 input "X1,Y1 :";x1,y1
30 input "X2,Y2 :";x2,y2
40 if abs((y2-y1)/(x2-x1))>1 then goto 200
100 for x=x1 to x2 step sgn(x2-x1)
110 y=(y2-y1)*(x-x1)/(x2-x1)+y1
120 pset (x,y)
130 next
140 end
200 for y=y1 to y2 step sgn(y2-y1)
210 x=(x2-x1)*(y-y1)/(y2-y1)+x1
220 pset (x,y)
230 next
240 end

実行例

２　ＤＤＡによる直線補間
BASICで直線を描くなら、上で示した「直線を描くプログラム１」で十分です。
ただし、機械語で直線描画プログラムを作る場合、このアルゴリズムでは、小数点（浮動小数点）
の計算が含まれているため、高速になりません。機械語で直線を引く場合には、
（Ａ）　計算は整数だけ　（スクリーンの座標は整数なので、これでＯ．Ｋ．です）
（Ｂ）　割り算を使わない
アルゴリズムが高速になります。
この条件の下に考え出されたのがＤＤＡ(Degital Differential Analyser デジタル差分解析)補間という
方法です。

今、下の図のように点P1から点P2に直線を引くとします。
この時に、P1の次にドットをうつべき座標の候補は赤色の３点、t1,t2,t3 です。
この中で、真の値に一番近い座標を選んでドットをうつことにします。
座標が決まれば、以下同様の手順で更に次の座標を決めていきます。

では、この手順を式にまとめてみましょう。
まず、点P1(X₁,Y₁) P2(Xz,Yz)　とし、傾きが緩やか（１以下）な場合で考えてみます。
Xに関しては以下の通り
X₂ = X₁ +1
X₃ = X₁+2
...........................
Xn = X₁ + n

さて、傾きをd = (Yz-Y₁)/(Xz-X₁) とすると、２点P1,P2を結ぶ線分の方程式は
y = d(x-X₁)+Y₁ ですから、Yの式は以下の通りになります。
Yn = d(Xn-X₁)+Y₁

さてここで、dは少数ですので、Ynも少数です。このままでは、少数の計算がついてまわってしまいます。
そこで、こいつを整数部と小数部にわけてしまいます。ここからがＤＤＡ補間の本題です。
整数部をYIn, 小数部をYEnとすると
Yn =YIn + YEn
YE_１ =0
YEn= YE_n-1+d
ということになります。

ここで、小数部のYEn>=0.5 ならYInの座標をn-1の時より1個上にあげ、小数部からは１を引いて新たな
YEnとします。　すなわち、YIn =YI_n-1+1 新しいYE_n<== YE_n-1
YEn<0.5 ならn-1の時と同じままで、
YIn =YI_n-1 とします。
（すなわちYInはYnを四捨五入した値になります）

では、ここまでのルールをいったんまとめておきましょう。
Xn=X₁+n
YE_１ =0
YEn= YE_n-1+d
YEn>=0.5 なら　YIn =YI_n-1+1　　 YEn　<== YE_n-1
YEn<0.5なら　　YIn =YI_n-1 　

さて、ここでもまだYEnは少数です。全てを整数の計算にしたいので、YEnも整数にしてしまいます。
YEnのある式の両辺に2*(Xz-X₁)を掛けて整理してみると、以下のようになります。
Xn=X₁+n
YE_１ =0
2*(Xz-X₁)*YEn= (YE_n-1+d)*2*(Xz-X₁)
2*YEn*(Xz-X₁)-(Xz-X₁)>=0 なら　YIn =YI_n-1+1　　　　 2*YEn*(Xz-X₁) <== 2*YEn*(Xz-X₁)-2*(Xz-X₁)
2*YEn*(Xz-X₁)-(Xz-X₁)<0なら　YIn =YI_n-1

なんかごちゃごちゃしてきましたので、2*YEn*(Xz-X₁)-(Xz-X₁) = En　としてみます。
Xn=X₁+n
YE_１ =0
En+(Xz-X₁) = E_n-1+(Xz-X₁)
En>=0 なら　YIn =YI_n-1+1　　　　En+(Xz-X₁) <= En-(Xz-X₁)
En<0 なら　YIn =YI_n-1

もう一息ですね。もう少しまとめてみましょう。
ちなみにE₁= 2*YE1*(Xz-X₁)-(Xz-X₁) =Xz-X₁　ですね。

Xn=X₁+n
E₁ =Xz-X₁
En= E_n-1
En>=0 なら　YIn =YI_n-1+1　En <== En-2*(Xn-X₁)
En<0 なら　YIn =YI_n-1

全て整数になり、割り算もなくなりルールがすっきりしましたね。これで、BASICのプログラムにできそうです。

ＤＤＡ補間の直線描画プログラム

10 cls
20 input "X1,Y1 :";x1,y1
30 input "X2,Y2 :";x2,y2
40 dx=x2-x1:dy=y2-y1:x=x1:y=y1
50 if abs(dy)/abs(dx)>1 then goto 200
100 e=-abs(dx)
110 for i=0 to abs(dx)
120 pset(x,y)
130 x=x+sgn(dx)
140 e=e+2*abs(dy)
150 if e>=0 then y=y+sgn(dy):e=e-2*abs(dx)
160 next
170 end
200 e=-abs(dy)
210 for i=0 to abs(dy)
220 pset (x,y)
230 y=y+sgn(dy)
240 e=e+2*abs(dx)
250 if e>=0 then x=x+sgn(dx):e=e-2*abs(dy)
260 next
270 end

ちなみに、N88互換BASIC For Winで上記の２つのプログラムを実行すると、ＤＤＡ補間の方が、１．５倍
ほど実行時間がかかります（遅い）。
ＤＤＡ補間の方が、ＳＴＥＰが多いし、計算も多くなっているからでしょう。

おそらく、機械語で組みなおしたら、ＤＤＡ補間の方が圧倒的に早くなると思います。
また、BASICのline命令も、機械語レベルではＤＤＡ補間による点描によって、直線を引いています。

2次関数については、「2次関数を描いてみる」をご参照下さい。

ＴＯＰＰＡＧＥ >Ｂａｓｉｃ活用研究目次