円弧の描画方法

質問

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

回答No.3

ametsuchi · ベストアンサー

問題を２つに分けましょう。

（１） ３点から円弧を求める方法：

とりあえず約束として、

P0:円弧始点
P1:円弧通過点
P2:円弧終点
O:求める円弧中心
R:円弧半径

とします。時計回りか、反時計回りかはここでは問いません。
線分P0P1、線分P1P2 にOから下ろした垂線の足は線分の中点ですから、線分長を

L01 = dist(P0, P1)
L12 = dist(P1, P2)
として、

<P1-P0, O> - 0.5*L01^2 = 0
<P2-P1, O> - 0.5*L12^2 = 0

です。ここに、<, >は内積を表わします。

これは、Oの成分、Ox,Oyに関する連立一次方程式になり、

det = (P1x-P0x)*(P2y-P1y) – (P1y-P0y)*(P2x-P1x)

として、

Ox = 0.5* {L01^2*(P2y-P1y) – L12^2*(P1y-P0y)} / det
Oy = 0.5* {-L01^2*(P2x-P1x) + L12^2*(P1x-P0x)} / det……………Equ.1)

が求まります。但し、３点の内２点が重なるとか、３点が一直線上に並ぶ場合はdet=0になるので注意が必要です。「円弧は求まらない」としてエラー処理しなくてはなりません。
半径は以下のように容易に求まります。

R = |P0 - O|…………………………………………………………………Equ.2)

始終角を求めます。先ず、

θ0 = atan2(P0y-Oy, P0x-Ox)
θ1 = atan2(P1y-Oy, P1x-Ox)
θ2 = atan2(P2y-Oy, P2x-Ox)…………………………………………………….Equ.3)

として、円弧中心から見た３点の角度が－π～＋πの範囲で求まります。
これを

θ0’ = 0
θ1’ =θ1 -θ0
θ2’ =θ2 -θ0………………………………………………………………………Equ.4)

と始点基準にします。

これを、０～２πの値に変換して、

・θ2’ < θ1’ なら反時計回り
・θ1’ < θ2’ なら時計回り

なのです。あと処理の都合のため、時計回り回りなら始終点を入れ替わると、必ず反時計回りになります。以下、「円弧」と言うと、

・中心（上のOですが、あなたのプログラムでは、「x0, y0」です）
・半径（上のRですが、あなたのプログラムでは「ｒ」です）
・始角（反時計回り）
・終角（反時計回り）

で表現されるものとします。ただ、Equ.3)で分かるとおり、既に、コストのかかる逆三角関数を３回も用いています。

（２） 円弧ベクター－>ラスター変換：

先ず、「ミッチェナーのアルゴリズム」ですが、ご存知のように、

１） 円を８分割し、対称性を利用して基本１パタン（東->北、0°～45°）を利用。
２） 基本パタンでは、y：必ず１Pixelずつ増加、x:０または１Pixel減少。
３） x: ０または－１を判断するのに、「真円からのx方向差分」を巧妙な計算で求める。
ただし、この差分は、x: ０または－１で異なる。

という非常に巧妙な仕掛けになっている訳です。三角関数は勿論、sqrt()も一度も使われていません。しかも近似計算ではなく、誤差は1/2Pixel以内というか、可能な限りでの正確な計算になっています。

本題に入ると、whileループに入る前に、（１）で求めた始終角から、

0) この1/8セルの処理区分， 開始y, 終了y
1) この1/8セルの処理区分， 開始y, 終了y 時計回り
2) この1/8セルの処理区分， 開始y, 終了y 時計回り
3) この1/8セルの処理区分， 開始y, 終了y
4) この1/8セルの処理区分， 開始x, 終了x 時計回り
5) この1/8セルの処理区分， 開始x, 終了x
6) この1/8セルの処理区分， 開始x, 終了x
7) この1/8セルの処理区分， 開始x, 終了x 時計回り

なる８つの行からなるテーブルを作ったら如何でしょうか？8個固定ですから配列でなくてもいいです。

・ 1/8セルの処理区分：
(1) 全域無効、描かない、
(2) 全域有効、描く。
(3) 一部有効、開始～終了範囲だけ描く。

・開始・終了y(x)：必ず開始<終了になります。
０）～７）何れも、最大で＝ｒ、最小で=0.707＊ｒです。ここは気を付けて下さい。

No.2で「forループにして、forループインデックスの範囲」てなこと言いましたが、whieループでいいと思います。「開始終了ｙ（ｘ）」を角度から求めるには始終点位置の角度に関しては残念ながら、三角関数を一度ずつ使わなくてはいけないでしょう。それ以外の場合は、ｒ0.707＊ｒです。三角関数計算は不要です。