傾いた楕円の描画方法

ＰＣでの楕円の描画は、ライブラリに組み込まれていますが、水平（または垂直）の楕円については、関数1行で描画することができます。
ところが、傾いている楕円については、描画することができません。
そこで、ミッチェナーのアルゴリズムで円を描くプログラムを変形して、上下（左右）のプロット位置をずらせば、一応、楕円は描画できるので、さらにプロットする部分に回転をかければ回転した楕円を描画できると考えて、プログラムを作成してみました。
しかし、あまり綺麗な楕円を描画できません。
ミッチェナーのアルゴリズムを上下に圧縮した時点で、左右の部分が少し密になり（これは許容できる範囲ですが）それを回転させるとき、実数計算になるため、最終的な位置は、ドットのどちらかになってしまうので、あまりうまくいきません。
ミッチェナーのあるごりずむの原理を使って、傾いた楕円の式から、直接プロットしなければ綺麗な楕円を描画することができないと考えます。
最終的に欲しい関数は、傾いた楕円の外接する4点の座標を与えて、描画する関数です。

No.3 ベストアンサー 回答者： stomachman 回答日時： 2004/03/09 12:08

No.1を具体化してみました。

楕円の方程式が
f(x,y)=0
ここに
f(x,y)=(c(x-x0)-s(y-y0))^2/a^2+(s(x-x0)+c(y-y0))^2/b^2-1
c=cosθ, s=sinθ
で与えられているとします。
g(x,y,α,β)=f(x+α,y+β)-f(x,y)
とおくと、
g(x,y,α,β)=((cα-sβ)^2+2(c(x-x0)-s(y-y0))(cα-sβ))/a^2+((sα+cβ)^2+2(s(x-x0)+c(y-y0))(sα+cβ))/b^2
である。αもβも高々-1,0,1のどれかの値なので、(α,β)の組み合わせそれぞれについて
s,c,(cα-sβ),(sα+cβ),(cα-sβ)^2,(sα+cβ)^2,1/a^2,1/b^2
はあらかじめ計算しておくことができるから、g(x,y,α,β)の計算はたいしたことはない。

でも、もっと計算を減らしましょう。
h(α,β,p,q) = g(x,y,α,β)-g(x-p,y-q,α,β)
とおくと、
h(α,β,p,q) =2(cp-sq)(cα-sβ)/a^2+2(sp+cq)(sα+cβ)/b^2
だから、α,β,p,qの組み合わせについてhをあらかじめ計算しておけます。

以上の準備のもとで、「(m,n)から出発して、上か左か左上に動く」という場合の手順を考えてみましょう。

はじめに
(α,β)∈{(0,1),(-1,0),(-1,1)}
であるから、
(p,q)∈{(0,1),(-1,0),(-1,1)}
として、h(α,β,p,q)をこれらの組み合わせ9通りについて計算しておけば十分です。

(m,n)に点をプロットします。
f(m,n)をマトモに計算し、
g(m,n,α,β)を(α,β)∈{(0,1),(-1,0),(-1,1)}についてマトモに計算し、
f(m+α,n+β)=f(m,n)+g(m,n,α,β)
によって、3通りのf(m+α,n+β)を作り、その絶対値が最小になるα,β（これをp,qとする）を採用します。
mをm+p、nをn+qで置き換えます。

(m,n)に点をプロットします。
次にg(m,n,α,β)を(α,β)∈{(0,1),(-1,0),(-1,1)}について
g(m,n,α,β)=g(m-p,n-q,α,β)+h(α,β,p,q)
によって計算し、
f(m+α,n+β)=f(m,n)+g(m,n,α,β)
によって、3通りのf(m+α,n+β)を作り、その絶対値が最小になるα,β（これをp,qとする）を採用します。
mをm+p、nをn+qで置き換えます。
以下同様です。

なお、動く方向の候補を変えるには、{(0,1),(-1,0),(-1,1)}という集合を変更すれば良いだけです。

No.2 回答者： ryuta_mo 回答日時： 2004/02/29 01:32

前傾いた楕円を各プログラムを作ったときは普通の楕円を傾けました。

図形描写のプログラムを書くコツがあります。
図形を順番に描くのではなく、描写先の座標からその点がどのようになるかを計算します。
たとえば線を描くとき線を端から端まで順番に点を打ちますが、描写先の座標を基準に考えその点を描写するかどうかを計算します。
これは、回転したり線が曲がってたりすると効果がはっきりします。

これでわかってくれるとうれしいな・・・

No.1 回答者： stomachman 回答日時： 2004/02/28 15:55

●「ミッチェナーのアルゴリズム」。

そういう名前だとは知りませんでしたけど、同じ考え方は固定小数点の演算しかできない大昔のマイコンで円を描くには普通に使っていたですね。まずこいつの考え方を少し一般化した形で調べてみましょう。

一辺が1の正方形のピクセルでできた画面に色をつけて、図形を最も近似する形を描く話です。
たとえば円x=R cos t, y=R sin tを t=0～π/2の範囲で描くには：

まず、t=0つまりピクセル(R,0)を塗る。

今ピクセル(m,n)を塗った。そうしたら、
ε=m^2+n^2-R^2
は必ずしも0ではなかったとしましょう。
次に上隣のピクセル(m,n+1)か、左上のピクセル(m-1,n+1)か、あるいは左のピクセル(m-1,n)のどれかを塗る。どれを採用するかは「どれが円に近いか」で決める。つまり、
a=m^2+(n+1)^2-R^2
b=(m-1)^2+(n+1)^2-R^2
ｃ=(m-1)^2+n^2-R^2
のうち絶対値が一番小さいやつを採用すれば良い。a,b,cをまともに計算しなくても
a=ε+2n+1
b=ε+2n+1-2m+1
c=ε-2m+1
と分かります。a,b,cのうち採用したものをεにして、また繰り返します。

そうすると、

●楕円の方程式f(x,y)=0と、これに外接する、x,y軸と平行な辺を持つ長方形、そしてその接点の座標が与えられているとします。たとえば右の接点から上の接点まで行くには：
まず、右の接点に最寄りのピクセルを塗る。
今ピクセル(m,n)を塗った。そうしたら、
ε=f(m,n)
は必ずしも0ではなかったとしましょう。
次に上隣のピクセル(m,n+1)か、左上のピクセル(m-1,n+1)か、あるいは左のピクセル(m-1,n)のどれかを塗る。どれを採用するかは「どれが楕円に近いか」で決める。つまり、
a=f(m,n+1)
b=f(m-1,n+1)
ｃ=f(m-1,n)
のうち絶対値が一番小さいやつを採用すれば良い。a,b,cをまともに計算しなくても漸化式を使って手抜きできます。
a,b,cのうち採用したものをεにして、また繰り返します。