15

SOで、塗りつぶされた円を描画するための次の簡単なアルゴリズムを見つけました。

for(int y=-radius; y<=radius; y++)
    for(int x=-radius; x<=radius; x++)
        if(x*x+y*y <= radius*radius)
            setpixel(origin.x+x, origin.y+y);

塗りつぶされた楕円を描画するための同様に単純なアルゴリズムはありますか？

4

4 に答える 4

20

より単純で、double除算がなく、除算もありません（ただし、整数のオーバーフローに注意してください）。

for(int y=-height; y<=height; y++) {
    for(int x=-width; x<=width; x++) {
        if(x*x*height*height+y*y*width*width <= height*height*width*width)
            setpixel(origin.x+x, origin.y+y);
    }
}

これを大幅に最適化するために、2つの事実を利用できます。

  • 楕円には垂直方向と水平方向の対称性があります。
  • 軸から離れるにつれて、楕円の輪郭はますます傾斜します。

最初の事実は、作業の4分の3を（ほぼ）節約します。2番目の事実は、テストの数を大幅に減らします（楕円のエッジに沿ってのみテストし、そこでもすべてのポイントをテストする必要はありません）。

int hh = height * height;
int ww = width * width;
int hhww = hh * ww;
int x0 = width;
int dx = 0;

// do the horizontal diameter
for (int x = -width; x <= width; x++)
    setpixel(origin.x + x, origin.y);

// now do both halves at the same time, away from the diameter
for (int y = 1; y <= height; y++)
{
    int x1 = x0 - (dx - 1);  // try slopes of dx - 1 or more
    for ( ; x1 > 0; x1--)
        if (x1*x1*hh + y*y*ww <= hhww)
            break;
    dx = x0 - x1;  // current approximation of the slope
    x0 = x1;

    for (int x = -x0; x <= x0; x++)
    {
        setpixel(origin.x + x, origin.y - y);
        setpixel(origin.x + x, origin.y + y);
    }
}

これが機能するのは、各スキャンラインが前のスキャンラインよりも短く、少なくとも前のスキャンラインよりも短いためです。整数のピクセル座標に丸められるため、これは完全に正確ではありません。線は、それより1ピクセル短くなる可能性があります。

言い換えると、最長の走査線（水平直径）から開始して、各線が前の線よりも短くなる量（dxコードで示される）は、最大で1つ減少するか、同じままであるか、または増加します。最初の内部forは、現在のスキャンラインが前のスキャンラインよりも短い正確な量を検出します。これdx - 1は、楕円のすぐ内側に到達するまでです。

                       |         x1 dx x0
                       |######    |<-->|
 current scan line --> |###########    |<>|previous dx
previous scan line --> |################  |
two scan lines ago --> |###################
                       |##################### 
                       |###################### 
                       |######################
                       +------------------------

楕円内テストの数を比較するために、各アスタリスクは、ナイーブバージョンでテストされた座標の1つのペアです。

 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************

...そして改善されたバージョンでは：

                        *
                             **
                                  ****
                                       ***
                                          ***
                                            ***
                                             **
                                             **
于 2012-04-25T19:41:04.777 に答える
8

楕円（原点の周り）は、 x軸またはy軸に沿って直線的に引き伸ばされた円です。したがって、次のようにループを変更できます。

for(int y=-height; y<=height; y++) {
    for(int x=-width; x<=width; x++) {
        double dx = (double)x / (double)width;
        double dy = (double)y / (double)height;
        if(dx*dx+dy*dy <= 1)
            setpixel(origin.x+x, origin.y+y);
    }
}

width == height == radiusの場合、これは円を描くためのコードと同等であることがわかります。

于 2012-04-25T19:30:33.927 に答える
8

交換

x*x+y*y <= radius*radius

と

Axx*x*x + 2*Axy*x*y + Ayy*y*y < radius*radius

ここで、Axx、Axy、Ayyの3つの定数があります。Axy = 0の場合、楕円の軸は水平方向と垂直方向にまっすぐになります。Axx = Ayy=1は円を作ります。Axxが大きいほど、幅は狭くなります。Ayyと高さについても同様です。任意の角度で傾斜した任意の楕円の場合、定数を計算するには少し代数が必要です。

数学的には、Axx、Axy、Ayyは「テンソル」ですが、おそらくそのようなものには入りたくないでしょう。

更新-詳細な数学。SOがMathSEのような優れた数学を作成できるとは思わないので、これは大雑把に見えます。 楕円と整列したx'、y'座標を持つ傾斜した楕円、x、y直線水平、垂直 x、y座標の楕円で描画（または何でも）したい。楕円が傾いています。楕円に合わせた代替座標系x'、y'を作成します。明らかに、楕円上の点は

(x'/a)^2 + (y'/b)^2 = 1

いくつかのよく選択されたランダムなポイントを熟考することによって、私たちはそれを見る

x' =  C*x + S*y
y' = -S*x + C*y

ここで、S、Cはsin（θ）とcos（θ）であり、θはx軸に対するx'軸の角度です。これは、プライミングされた場合はx =（x、y）と同様の表記で短縮でき 、RはCとSを含む2x2行列です。

x' = R x

楕円方程式は書くことができます

T（x'）A''x' = 1

ここで、「T」は転置を示し、「^」をドロップしてすべての人の目を突くのを避けるため、「a2」は実際にはa^2を意味します。

A'' =

1/a2     0  
 0     1/b2

x' = R xを使用すると、次の ようになります。

T（R x）A'' R x = 1

T（x）T（R）A'' R x = 1

T（x）A x = 1

ここで、Aは、傾斜した描画スキャンラインアルゴリズムを機能させるために知っておく必要があることです。

A = T（R）A'' R =

C2/a2+S2/b2     SC(1/a2-1/b2)
SC/(1/a2-1/b2)  S2/a2 + C2/b2

T（ x）A xに従って、これらにxとyを掛けると、それが得られます。

于 2012-04-26T16:18:50.827 に答える
5

この論文で提案されているように、高速ブレゼンハム型アルゴリズムは非常にうまく機能します。これが私が同じように書いたOpenGL実装です。

基本的な前提は、1つの象限に曲線をプロットすることです。これは、他の3つの象限にミラーリングできます。これらの頂点は、円の中点円アルゴリズムで使用するものと同様の誤差関数を使用して計算されます。上でリンクした論文には、方程式のかなり気の利いた証拠があり、アルゴリズムは、エラー関数にその値を代入するだけで、特定の頂点が楕円内にあるかどうかをチェックするだけです。アルゴリズムは、第1象限で描画している曲線の接線の傾きも追跡し、傾きの値に応じてxまたはyを増分します。これは、アルゴリズムのパフォーマンスにさらに貢献します。これが何が起こっているかを示す画像です：

ここに画像の説明を入力してください

楕円の塗りつぶしに関しては、各象限の頂点（基本的にx軸とy軸を横切る鏡面反射）がわかれば、計算する頂点ごとに4つの頂点が得られます。これは、四角形を描画するのに十分です（とにかくOpenGLで） 。このようなすべての頂点にクワッドを描画すると、楕円が塗りつぶされます。私が提供した実装では、パフォーマンス上の理由からVBOを採用していますが、厳密には必要ありません。

実装では、四角形を描画する代わりに三角形と線を使用して塗りつぶされた楕円を作成する方法も示しています。ただし、四角形はプリミティブであり、頂点ごとに1つの三角形ではなく、4つの頂点に対して1つの四角形しか描画しないため、明らかに優れています。三角形の実装。

于 2015-01-06T20:25:19.013 に答える