DDA

DDA

DDA(Digital Differential Analyzer)は、整数演算のみで図形を描画するアルゴリズムです。
ロジックの間違いが有れば指摘してくださると有り難いです。

準備

open Graphics

(* Enter待ち *)
let wait () = let dummy = read_line () in ()

(* 10×10で点を描く *)
let pset x y = fill_rect (x * 10) (y * 10) 10 10

let _ = 
  open_graph "";
  pset 20 20;
  wait ()

空白の窓に小さな黒い四角が描かれてるはずです。
ターミナルの方に戻ってEnter押せば終了します。

Graphicsに豊富に用意された描画関数は置いておいて、このpsetだけを使って線や円や、もっと複雑なものを描いていく、という筋書きです。
意義を疑った人は、シミュレーションゲームで直線上に並んだ敵を攻撃する魔法は使用禁止。

注意事項として、Graphicsライブラリでは左下が原点になります。

ocamlopt graphics.cmxa g.ml

直線

...略...

(* 符号 *)
let sign x = if x > 0 then 1 else -1

(* 線を引く *)
let line x1 y1 x2 y2 =
  let w = abs (x2 - x1) in
  let h = abs (y2 - y1) in
  let step_x = sign (x2 - x1) in
  let step_y = sign (y2 - y1) in
  if w >= h then
    let d = ref (w / 2) in
    let x = ref x1 in
    let y = ref y1 in
    while !x <> x2 do
      pset !x !y;
      d := !d + h;
      if !d >= w then (
        y := !y + step_y;
        d := !d - w
      );
      x := !x + step_x
    done;
    pset !x !y
  else
    let d = ref (h / 2) in
    let x = ref x1 in
    let y = ref y1 in
    while !y <> y2 do
      pset !x !y;
      d := !d + w;
      if !d >= h then (
        x := !x + step_x;
        d := !d - h
      );
      y := !y + step_y
    done;
    pset !x !y

let _ = 
  open_graph "";
  line 0 0 10 10;
  line 0 0 25 10;
  line 0 20 30 5;
  line 40 25 30 5;
  wait ()

x, yそれぞれのケースで最後のpsetを取り除けば、WindowsのGDIみたく最後の点は描かない仕様にできます。
分数計算を分母倍して行ってるだけなのですが、ここではdひとつで済ませていますが、変数をふたつ使うバリエーションもあるようです。
dの初期値を幅の半分にしてる(1/2から始めてる)のは、始点と終点付近でバランスを取るためです。
中心から対象に計算して計算量を半分にする方法もありますが、その場合接続点となる真ん中に違和感が生じる場合ありなので、結局この方法が「見慣れた」線が引けるのでは無いでしょうか。

四角

...略...

let rectangle x1 y1 x2 y2 =
  let (xs, xe) = if x1 <= x2 then (x1, x2) else (x2, x1) in
  let (ys, ye) = if y1 <= y2 then (y1, y2) else (y2, y1) in
  for x = xs to xe do pset x y1; pset x y2 done;
  for y = ys + 1 to ye - 1 do pset x1 y; pset x2 y done

let rectangle_fill x1 y1 x2 y2 =
  let (xs, xe) = if x1 <= x2 then (x1, x2) else (x2, x1) in
  let (ys, ye) = if y1 <= y2 then (y1, y2) else (y2, y1) in
  for x = xs to xe do
    for y = ys to ye do
      pset x y
    done
  done

let _ = 
  open_graph "";
  rectangle 25 15 15 25;
  rectangle_fill 10 10 20 20;
  wait ()

ほら、一応書いときたいじゃないですか、ネ。
難しい本はこういうのを飛躍するから難しいという説もあるし。(←ない)

円

http://fussy.web.fc2.com/algo/algo2-2.htmより。

...略...

let ellipse center_x center_y radius_x radius_y = 
  let product_4_b = (4 * radius_x * radius_x) / (radius_y * radius_y) in
  let product_2_b = product_4_b / 2 in
  let product_1_b = product_2_b / 2 in
  let x = ref radius_x in
  let y = ref 0 in
  let f = ref (-2 * radius_x + 1 + product_2_b) in
  let h = ref (-4 * radius_x + 2 + product_1_b) in
  while !x >= 0 do
    pset (center_x + !x) (center_y + !y);
    pset (center_x - !x) (center_y + !y);
    pset (center_x + !x) (center_y - !y);
    pset (center_x - !x) (center_y - !y);
    if !f < 0 then (
      y := !y + 1;
      f := !f + product_4_b * !y + product_2_b;
      h := !h + product_4_b * !y;
    ) else if !h >= 0 then (
      x := !x - 1;
      f := !f - 4 * !x;
      h := !h - 4 * !x - 2;
    ) else (
      x := !x - 1;
      y := !y + 1;
      f := !f + product_4_b * !y - 4 * !x + product_2_b;
      h := !h + product_4_b * !y - 4 * !x + 2;
    )
  done

...略...

BASICのCIRCLE文よろしく半径単位でいいならこれでいいんですよ。
しかし、これですと、直径を1ピクセル単位で指定できないのです。
半径を指定する関係上、直径はどうしても2ピクセル単位に……。

しかしながら、ベジエ曲線等で円を近似するのは(浮動小数点演算を使うとDDAで無くなるとか野暮なことは置いといて)、オーバースペックな気もしますし、何より僕の手に余ります。

……というわけで、セコイ技で。
上記アルゴリズムですと、直径は、半径 * 2 + 1 (+ 1 は、中心から対象に描くから)となってます。
ならば、直径が偶数の時は、適切にずらしてやればOK……うーむ。

...略...

let ellipse x1 y1 x2 y2 = 
  let center_x = (x1 + x2) / 2 in
  let center_y = (y1 + y2) / 2 in
  let radius_x = abs (x1 - x2) / 2 in
  let radius_y = abs (y1 - y2) / 2 in
  let (diff_x1, diff_x2) = if x1 <= x2 
    then (x1 - (center_x - radius_x), x2 - (center_x + radius_x))
    else (x2 - (center_x - radius_x), x1 - (center_x + radius_x)) in
  let (diff_y1, diff_y2) = if y1 <= y2 
    then (y1 - (center_y - radius_y), y2 - (center_y + radius_y))
    else (y2 - (center_y - radius_y), y1 - (center_y + radius_y)) in
  let product_4_b = (4 * radius_x * radius_x) / (radius_y * radius_y) in
  let product_2_b = product_4_b / 2 in
  let product_1_b = product_2_b / 2 in
  let x = ref radius_x in
  let y = ref 0 in
  let f = ref (-2 * radius_x + 1 + product_2_b) in
  let h = ref (-4 * radius_x + 2 + product_1_b) in
  while !x >= 0 do
    pset (center_x - !x - diff_x1) (center_y - !y - diff_y1);
    pset (center_x + !x + diff_x2) (center_y - !y - diff_y1);
    pset (center_x - !x - diff_x1) (center_y + !y + diff_y2);
    pset (center_x + !x + diff_x2) (center_y + !y + diff_y2);
    if !f < 0 then (
      y := !y + 1;
      f := !f + product_4_b * !y + product_2_b;
      h := !h + product_4_b * !y;
    ) else if !h >= 0 then (
      x := !x - 1;
      f := !f - 4 * !x;
      h := !h - 4 * !x - 2;
    ) else (
      x := !x - 1;
      y := !y + 1;
      f := !f + product_4_b * !y - 4 * !x + product_2_b;
      h := !h + product_4_b * !y - 4 * !x + 2;
    )
  done

let _ = 
  open_graph "";
  ellipse 25 15 15 25;
  ellipse 10 10 21 21;
  ellipse 1 10 30 21;
  wait ()

こういうのを力業というのだろうなあ……。