円弧の描画方法

質問

円（または１／８円弧）の描画アルゴリズムとして
ミッチェナーの円のアルゴリズムが知られています。
しかし、任意の円弧（例えば、長方形に内接するような→MFCのライブラリに
あるような指定方法や３点を指定して円弧を描画する）を高速に描画する
方法はありますか？ミッチェナーの方法の変形（制限）でもいいので
教えてください。

回答No.2

ametsuchi

すいません。質問がでてたんですね。sekinegooさんは、

１）プログラムの簡潔さ
２）処理効率

どちらを優先させようとしているのでしょう？実はsekinegooさんの目的自体イマイチ分かっていません。

私自身は、図形処理自体は職業として20年以上携わっていますが、ベクターデータが殆どです。ラスターデータは、画像データとか、地形標高データ（＝DEM）位のものです。今回の

・ベクター-->ラスター変換

は、昔某テレビ局向けにPolygonデータを放送用の画像データに変換した位で、「ミッチェナーのアルゴリズム」の本の上で知っているに過ぎないのでシロートです。

我々図形処理屋は、ベクターデータが基本ですから、円弧は３点から求めたり、２線に接する半径Rの円弧を求めたり様々です。２D円弧は、
・中心
・半径
・始角（反時計回り）、これを「FROM角」と名付けましょう。
・終角（反時計回り）、これを「TO角」と名付けましょう。
という「標準形」で持つことが多いです。最近流行のNURBSで表現する手もありますが...。

で、効率を無視するなら、

(1)まず円弧を求める。（上の「標準形」で）
(2)円弧を折れ線近似する。（折れ線の精度が問題！！）
(3)折れ線の各線分をＤＤＡ変換

という手もあります。それならプログラムは簡単ですが、精度を上げるには折れ線を細かく分割しなくてはならず、三角関数計算を辺数に比例して行なわなくてはならないので処理効率が落ちます。処理効率を上げようとすると、今度は精度が失われます。しかも、ミッチェナーのアルゴリムとは何の関係もなくなっちゃいます。

一方、処理効率受重視なら、プログラムが多少複雑でも、
「SetPointで点を打つときに判定して打つ、打たない...」とし、「ややこしくなって」しまうのはやむを得ないのではないでしょうか？

先ず、「FROM角」、「TO角」から、８つの内そのセルどういうセルか分かります。

イ）全く描かないセル
ロ）開始側の一部だけ描くセル
ハ）終了側の一部だけ描くセル
ニ）全部描くセル

イ）とニ）は問題ないです。問題はロ）とハ）です。これも「FROM角」、「TO角」から分かります。というより、

■「FROM角」、「TO角」から、８つのセルがイ）～ニ）どれに該当し、ロ）とハ）の場合、各セル毎の範囲が分かる。

わけです。できれば三角関数はコストのかかる計算ですから、避けたいですね。whileループになってますが、forループで、整数の範囲ではじければ理想です。No.1でも言ったように、1/8セル内では、円弧は単調増加（または減少）ですから、工夫次第で、角度範囲をforループインデックスの範囲（＝整数値）に置き換えることができるはずです。

ではご健闘を！ウソがあったらごめんなさい！

補足

わざわざ回答していただき、感謝致します。
三角関数は、使いたくないので、整数計算だけで行いたいと思います。
Ｃマガジンに図形描画の記事があって、バックナンバーをすべて購入して
読みましたが、円はあっても円弧は、ありませんでした。インターネットを
探しても、円はあっても円弧はありません。できれば３点円から描画したい
と思いますが、ミッチェナーのアルゴリズムが高速なので、これの変形（点を打つ／打たないの判定を入れる）として
求めたいのですが、ＭＦＣのように範囲指定になってもかまいません。
虫のいい話ですが、Ｃの関数として、欲しいのです。ですから、簡単に
言えば、ＭＦＣのような引数で、実際のソースがあったらいいなと思って
います。インターネットでもＣマガジンでも円のソースはあっても、円弧の
ソースは、どこにもありません。3点指定の円描画はあきらめるとしても
始点終点指定のプログラムがどこかにないかと探しています。
私が作ると、点描画する／しないの判定が、どうしても冗長になって
しまいます。よろしくお願いします。