ビットマップが閉曲線で囲まれている時, その内部を塗り潰したい. PostScriptなら, 閉曲線を描き. strokeの代りにfillとすればよい. ProcessingならFill(色); としておくと, その色で塗り潰してくれるから, 簡単である.
それを自分でやる方法が, filling algorithmである.
TAOCPによると, 正方形ピクセルの2次元配列を, 円錐曲線が正方形の中心のいずれの側を通るかにより, 縦横の線の境界で分離するのは簡単だそうである.
下の図はTAOCPの7.1.3(171)を私が描き直したもので, 黒の曲線で示す, 円錐曲線の代表選手, 長軸20, 短軸10の楕円の長軸の右端の辺りのピクセルの様子である. 右下の黒丸の座標が(20,0)だ.
ピクセルの格子点は, x, yが整数値のところに対応している. 座標の整数値の間にピクセルがあるから, ピクセルの中央の座標には, 1/2が付くわけだが, それはいやらしいから, ピクセルの右上の隅の座標で指定する.
従って, ピクセル(20,0)は, 黒丸の左下のピクセルである.
さて, このピクセルを塗るべきか否かは, ピクセルの中央における, 楕円の式の値の正負で決める. 丁度0のところを楕円が通る. 楕円の式は(x/20)2+(y/10)2-1=0だが, ピクセルの中央の値は, xとyからそれぞれ1/2を引いて計算する.
つまり, ピクセル(x,y)の中央の値は,
((x-1/2)/20)2+((y-1/2)/10)2-1
=(x2-x+1/4)/400+(y2-y+1/4)/100-1
1/4や1/100がついて回って, これもやめたいから整数係数にする
400倍して
x2-x+1/4+4y2-4y+1-400
4倍して
4x2-4x+1+16y2-16y+4-1600
=4x2+16y2-4x-16y+1+4-1600
=4x2+16y2-4x-16y+-1595
これをQ(x,y)とする. このx,yに20,0を入れると, その左下のピクセルの中央の値, Q(20,0)=-75が得られる.
こういう値を, この図のピクセルについて計算した結果が, ピクセルの下の方の数値である. これが分かると, 正と負のピクセルの境界が, 塗る塗らぬの境界になる.
この図には, すべてのピクセルの値が計算してあるが, 曲線が左上へ単調に伸びると分かっていれば, 上隣りのピクセルの値を計算し, 負なら上へ進み, 正なら左へ進めば良い. すなわち, 今黒丸の点にいて, 上のピクセルが-75なので, 赤線のように境界を上に延ばす. その上も-43なので, 上へ延ばす. その上は21だから左へ行く. その上は-131だから上へ. というように進むと, 左上へ単調に進む第1象限の部分の境界が得られる.
ところで, 一般的な円錐曲線の式Q(x,y)=ax2+bxy+cy2+dx+ey+fの順次の計算は, Qx(x,y)=2ax+by+d, Qy(x,y)=bx+2cy+eを保持していると, 簡単に求まるということを見つけた知恵者がいて, これを3レジスタ法という. それを使ったアルゴリズムがTAOCPにあるが, 例によってgoto文だらけなので, Scheme風に書いたプログラムが以下である. 関数定義の後のTと番号のコメントは, TAOCPのアルゴリズムTの番号である.
(define (algorithm713t x x1 y y1 a b c d e f)
(define (q x y) (+ (* a x x) (* b x y)
(* c y y) (* d x) (* e y) f))
(define (qx x y) (+ (* 2 a x) (* b y) d))
(define (qy x y) (+ (* b x) (* 2 c y) e))
(let ((qreg 0) (rreg 0) (sreg 0))
(call-with-current-continuation
(lambda (exit)
(define (left) (display "left\n")
(bit-string-xor!
(list-ref hs (+ y 11)) (- xmax x)))
(define (right) (display "right\n")
(bit-string-xor!
(list-ref hs (+ y 11)) (- xmax (+ x 1))))
(define (up) (display "up\n"))
(define (down) (display "down\n"))
(define (initset x y a c)
(set! qreg (q x y)) (set! rreg (+ (qx x y) a))
(set! sreg (+ (qy x y) c)))
(define (update rs ab bc)
(set! qreg (+ qreg rs)) (set! rreg (+ rreg ab))
(set! sreg (+ sreg bc)))
(define (hfinish) ;T10
(cond ((< x x1) (right) (set! x (+ x 1)) (hfinish))
((> x x1) (left) (set! x (- x 1)) (hfinish))
(else (exit 'ok))))
(define (vfinish) ;T11
(cond ((< y y1) (up) (set! y (+ y 1)) (vfinish))
((> y y1) (down) (set! y (- y 1)) (vfinish))
(else (exit 'ok))))
(define (moveup) (up) (set! y (+ y 1)) ;T6
(if (= y y1) (hfinish) (update sreg b (* 2 c))))
(define (movedown) (down) (set! y (- y 1)) ;T7
(if (= y y1) (hfinish)
(update (- sreg) (- b) (- (* 2 c)))))
(define (moveleft) (left) (set! x (- x 1)) ;T8
(if (= x x1) (vfinish)
(update (- rreg) (- (* 2 a)) (- b))))
(define (moveright) (right) (set! x (+ x 1)) ;T9
(if (= x x1) (vfinish) (update rreg (* 2 a) b)))
(define (rightup) ;T2
(if (< qreg 0) (moveright) (moveup)) (rightup))
(define (downright) ;T3
(if (< qreg 0) (movedown) (moveright)) (downright))
(define (upleft) ;T4
(if (< qreg 0) (moveup) (moveleft)) (upleft))
(define (leftdown) ;T5
(if (< qreg 0) (moveleft) (movedown)) (leftdown))
(if (= x x1) (vfinish))
(if (= y y1) (hfinish))
(if (< x x1)
(if (< y y1)
(begin (initset (+ x 1) (+ y 1) a c) (rightup))
(begin (initset (+ x 1) y a (- c)) (downright)))
(if (< y y1)
(begin (initset x (+ y 1) (- a) c) (upleft))
(begin (initset x y (- a) (- c)) (leftdown))))
))))
こう定義してから, 順次の象限について
(algorithm713t 20 0 0 10 4 0 16 -4 -16 -1595)
(algorithm713t 0 -20 10 0 4 0 16 -4 -16 -1595)
(algorithm713t -20 0 0 -10 4 0 16 -4 -16 -1595)
(algorithm713t 0 20 -10 0 4 0 16 -4 -16 -1595)
のように呼ぶと, 下のような境界が得られる.
しかし, 境界だけでは塗り潰したことにならない. 塗り潰しの実装はこのようにする. 境界の横線の真上のピクセルを1に, それ以外を0のビット列の配列hs[-11..10], bs[-11..10]を用意する. 私流のプログラムでは,
(define hs
(map (lambda (x) (make-bit-string 42 #f)) (a2b -11 11)))
(define bs
(map (lambda (x) (make-bit-string 42 #f)) (a2b -11 11)))
これはMIT Schemeにある長さ42ビットのbit-stringで, 初期値はオール0である. リストの長さは22だ.
上のプログラムの, 下請け関数leftとrightのところは,
(define (left) (display "left\n")
(bit-string-xor! (list-ref hs (+ y 11)) (- xmax x)))
(define (right) (display "right\n")
(bit-string-xor! (list-ref hs (+ y 11)) (- xmax (+ x 1))))
となっていて, 横向きの境界に対応するビットを0から1にしている. その結果, 1周すると, hsとして(最下行がリストの先頭)
#*000000000000000111111111111000000000000000
#*000000000011111000000000000111110000000000
#*000000001100000000000000000000001100000000
#*000000110000000000000000000000000011000000
#*000011000000000000000000000000000000110000
#*000100000000000000000000000000000000001000
#*001000000000000000000000000000000000000100
#*000000000000000000000000000000000000000000
#*010000000000000000000000000000000000000010
#*000000000000000000000000000000000000000000
#*000000000000000000000000000000000000000000
#*000000000000000000000000000000000000000000
#*010000000000000000000000000000000000000010
#*000000000000000000000000000000000000000000
#*001000000000000000000000000000000000000100
#*000100000000000000000000000000000000001000
#*000011000000000000000000000000000000110000
#*000000110000000000000000000000000011000000
#*000000001100000000000000000000001100000000
#*000000000011111000000000000111110000000000
#*000000000000000111111111111000000000000000
#*000000000000000000000000000000000000000000
のようなビット列が得られる. hsが出来たら,
(do ((i 1 (+ i 1))) ((= i 22))
(list-set! bs i (bit-string-xor (list-ref bs (- i 1))
(list-ref hs i))))
のプログラムで, bsが作れる. bsはこういう値である.
#*000000000000000000000000000000000000000000
#*000000000000000111111111111000000000000000
#*000000000011111111111111111111110000000000
#*000000001111111111111111111111111100000000
#*000000111111111111111111111111111111000000
#*000011111111111111111111111111111111110000
#*000111111111111111111111111111111111111000
#*001111111111111111111111111111111111111100
#*001111111111111111111111111111111111111100
#*011111111111111111111111111111111111111110
#*011111111111111111111111111111111111111110
#*011111111111111111111111111111111111111110
#*011111111111111111111111111111111111111110
#*001111111111111111111111111111111111111100
#*001111111111111111111111111111111111111100
#*000111111111111111111111111111111111111000
#*000011111111111111111111111111111111110000
#*000000111111111111111111111111111111000000
#*000000001111111111111111111111111100000000
#*000000000011111111111111111111110000000000
#*000000000000000111111111111000000000000000
#*000000000000000000000000000000000000000000
タイプの文字の縦横比は1:1でなく, これは正しい形ではない. 再びMIT Schemeの機能graphicsを利用すると,
(define mydevice (make-graphics-device 'x))
(graphics-set-coordinate-limits mydevice -24 -24 24 24)
(do ((i 0 (+ i 1))) ((= i 22))
(let ((b (list-ref bs i)))
(do ((j 0 (+ j 1))) ((= j 42))
(if (bit-string-ref b j)
(graphics-operation mydevice 'fill-circle
(- 21 j) (- i 11) 0.5)))))
によって, 次のようなパターンが得られる.
0 件のコメント:
コメントを投稿